Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition

CHAPTER 5

Advanced Protocols

5.1 ZERO-KNOWLEDGE PROOFS

Here's another story:

ALICE: “I know the password to the Federal Reserve System computer, the ingredients in McDonald's secret sauce, and the contents of Volume 4 of Knuth.”

BOB: “No, you don't.”

ALICE: “Yes, I do.”

BOB: “Do not!”

ALICE: “Do too!”

BOB: “Prove it!”

ALICE: “All right. I'll tell you.” She whispers in Bob's ear.

BOB: “That's interesting. Now I know it, too. I'm going to tell The Washington Post.”

ALICE: “Oops.”

Unfortunately, the usual way for Alice to prove something to Bob is for Alice to tell him. But then he knows it, too. Bob can then tell anyone else he wants to and Alice can do nothing about it. (In the literature, different characters are often used in these protocols. Peggy is usually cast as the prover and Victor is the verifier. These names appear in the upcoming examples, instead of Alice and Bob.)

Using one-way functions, Peggy could perform a zero-knowledge proof [626]. This protocol proves to Victor that Peggy does have a piece of information, but it does not give Victor any way to know what the information is.

These proofs take the form of interactive protocols. Victor asks Peggy a series of questions. If Peggy knows the secret, she can answer all the questions correctly. If she does not, she has some chance—50 percent in the following examples—of answering correctly. After 10 or so questions, Victor will be convinced that Peggy knows the secret. Yet none of the questions or answers gives Victor ...