Prove you know it without saying it

A proof usually shows you why something is true, and so hands you the reason. A zero-knowledge proof convinces you that a claim is true while giving you nothing you could not have produced yourself. The trick is to swap one explanation for many short challenges that only someone who knows the secret can keep answering.

A cave with a secret

Quisquater and Guillou tell the idea as a children's story. A cave's entry forks into two dark, winding passages, and each ends in a dead end. Forty thieves on forty days flee into the cave with Ali Baba behind them, and every one escapes. Luck would give that “only one chance in a million million”, so Ali Baba hides at the end of one passage and hears a thief whisper “Open sesame”. The end wall slides open, and the two passages turn out to join behind it.

Centuries later a researcher called Mick Ali knows the words and wants to prove it to a television reporter without saying them. Mick walks alone into one passage. The reporter then goes only as far as the fork and flips a coin: heads means “come out on the right”, tails “come out on the left”. If Mick is already on the called side he walks back; if not, he opens the wall and crosses. Either way he comes out where he was told.

Why it is useful

Barak calls zero-knowledge proofs “proofs that fully convince that a statement is true without yielding any additional knowledge.” His uses include proving your identity so that the checker cannot later impersonate you, and he notes Chaum's suggestion of publishing encrypted votes with a proof that the announced count matches them - asking whether it can be done without opening any vote. He credits the idea to Goldwasser, Micali and Rackoff.

Each round halves the cheater's chance

Someone without the words must commit to a passage before he hears the call, and the call is a coin he cannot predict. Half the time he is on the wrong side, and then he is stuck. In the paper's words, “Each new test divided by two the chances of success for someone without the secret.” Mick never fails, because the wall lets him answer either call.

So after n rounds a guesser survives with chance 1/2ⁿ. The scene was played forty times and Mick passed all forty. For a guesser that is one chance in 2⁴⁰ = 1,099,511,627,776 (our arithmetic), and the paper gives the same figure, rounded, for its forty thieves: one in a million million.

The three properties

Barak states what the cave illustrates. Completeness: if the claim is true, the honest prover makes the verifier accept with probability at least 0.9. Soundness: if it is false, no prover of any power makes the verifier accept with probability above 0.1. Those thresholds are his convention; other texts use others, such as always accepting a true claim. At one half per round, four rounds push a cheater to 1/16 = 0.0625, under his 0.1 (our arithmetic).

Zero knowledge is the unusual one. For every efficient verifier strategy there must be an efficient simulator: a program that never meets the prover, yet whose output no efficient test can tell apart from what that verifier holds after the real conversation. The requirement is computationally indistinguishable, not identical.

The tape that proves nothing

The story acts this out. A jealous reporter from another network films the same show with an actor who looks like Mick but lacks the words. Half the scenes are spoiled, so he keeps only the successful takes until he has forty. In court the judges “could not tell the tapes apart”. The fake was made with no secret, so it holds none, and the real tape looks the same, “so the genuine tape did not convey knowledge of the secret either.”

The live reporter was convinced because he flipped the coins himself, after Mick was inside. But he “could not pass his conviction on to the judges”. A tape cannot prove the order in which things happened; that last step is our reading, not his sentence.

Faster fakes, bigger caves

Researchers the paper places in Israel shortened the film by testing several secrets in parallel, one cave per floor. Some European researchers then saw a quicker fake: reporter and actor agree the forty calls in advance, and the reporter only pretends to choose. The paper answers with a revised cave of many passages, so one test carries more weight, while admitting “It is impossible to build a cave with a million million passages” and pointing to an arithmetic scheme. Prior agreement still fakes any such tape, so the tape still reveals nothing.

Barak adds that repeating a zero-knowledge protocol round after round keeps it zero-knowledge, and that when soundness holds only against efficient provers the system is called an argument, not a proof.

In short

Ask a question the prover cannot predict, many times. The honest prover answers every one; a guesser survives each with chance one half, so n rounds leave him 1/2ⁿ. And because a guesser could fake the whole record by keeping his lucky takes, the record gives away nothing about the secret.