Listenly

What was the mental poker problem that inspired the invention of zero-knowledge proofs?

Answered at 4:03 in How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser) · a16z crypto show

— questions searchable right now

What was the mental poker problem that inspired the invention of zero-knowledge proofs?

The mental poker problem asked how two people sitting in different parts of the world could play cards over the phone without having any physical cards. They needed to deal a deck and play according to the rules while proving they followed those rules without revealing the cards or their encryption. This led Goldwasser and Micali to ask how to prove you're dealing cards properly without revealing everything about what you've encrypted and the randomness used to encrypt.

Shafi Goldwasser on a16z crypto showAll answers from this podcast →
Full answer and detailsRead the whole answer, key facts and every other question from this episode

In short

The mental poker problem asked how two people sitting in different parts of the world could play cards over the phone without having any physical cards.

Shafi Goldwasser, Turing Award-winning cryptographer · How Zero-Knowledge Proofs Were Invented (ft. Co-Inventor and Turing Award Winner Shafi Goldwasser) · a16z crypto show · answer at 4:03

Key takeaways

  • The mental poker problem asked how two people sitting in different parts of the world could play cards over the phone without having any physical cards.

Quote to remember

“The definition of zero knowledge is in some sense that at the end you will believe what I claim, but you will discover nothing else.”

— Shafi Goldwasser

The full answer · about 1 min

The mental poker problem asked how two people sitting in different parts of the world could play cards over the phone without having any physical cards. They needed to deal a deck and play according to the rules while proving they followed those rules without revealing the cards or their encryption. This led Goldwasser and Micali to ask how to prove you're dealing cards properly without revealing everything about what you've encrypted and the randomness used to encrypt.

Key facts

  • Six submissions and rejections before publication of the GMR zero-knowledge interactive proofs paper
  • Two provers used in multi-prover interactive proof systems before reduction to single-prover protocols
  • IP equals PSPACE complexity class result derived from interactive proof techniques

People, companies and topics mentioned

Zero-knowledge proofsMental poker problemInteractive proofsProbabilistically checkable proofs (PCP)SumCheck protocolSNARKsMerkle treesFiat-Shamir transformation

More answers from this episode

 ·  All answers from a16z crypto show →
—
—
0:00
0:00