Zero knowledge proof
In cryptography, a zero-knowledge proof is a method for one party to prove to another that they are in possession of some information without revealing anything about that information.
It is common practice to label the two parties in a zero-knowledge proof as Peggy (the prover who wants to prove that she has some information) and Victor (the verifier). Sometimes P and V are known instead as Pat and Vanna.
This can be used in many situation where two communicating parties distrust each other. A common example is in authentication systems where one party wants to be able to prove their identity to a second party via some secret information (such as a password) but doesn't want the second party to then be able to trick a third party into believing that they are the first party by use of that secret information.
An important concept of zero-knowledge proofs is that they are interactive, in that they involve Victor issuing a challenge to Peggy who then responds. A side effect of this is that Victor cannot then take a transcript of the zero-knowledge proof and use it to prove to a third party that Peggy knows the information because the system is no longer interactive.
In practical terms this is because the proof is simulatable, that is that Victor can produce a valid transcript of a zero-knowledge proof without any help from Peggy.
Absent a challenge-response test, a verifier may choose a challenge and thus learn something about the prover's secret. This might even result in the success of a chosen-text attack.
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is a fixed probability p in any zero-knowledge proof that Peggy will be able to provide the correct response to a challenge even if she doesn't know the key. However if the test is repeated n times the probability of Peggy cheating is reduced to <math>p^n<math>, and by increasing the number of tests Victor can reduce the probability of Peggy cheating to an arbitrary level.
Example strategy
Peggy's public key is a large graph, which we will call G.
Peggy generated G at some time in the past, and then published it widely.
Because she manufactured it specially for the purpose, Peggy knows a Hamiltonian cycle in G. Peggy will prove her identity to Victor by proving that she knows a Hamiltonian cycle in G. Even though G is public information, nobody else can do this, because nobody else knows a Hamiltonian cycle of G, and finding Hamiltonian cycles in graphs is a difficult problem (see NP-completeness).
However, Peggy mustn't simply reveal the Hamiltonian cycle to Victor, since then Victor (or an eavesdropper) would be able to impersonate Peggy in the future. Peggy mustn't reveal any information at all about the cycle, because an eavesdropper might gather information on several different occasions and assemble it into enough information to be able to impersonate Peggy.
To prove her identity, Peggy and Victor play several rounds of the following game:
- Peggy labels the vertices of G with random numbers. An edge can then be represented as a pair of these numbers. She lists the edges of G, and encrypts each edge with a different encryption key. She then sends the encrypted edges to Victor.
- Victor flips a coin.
- If the coin comes up heads, Peggy surrenders the encryption keys and the mapping from vertices to random numbers. Victor then decrypts the edges and verifies that the encrypted edges sent in step 1 do in fact make up graph G and not some other graph.
- If the coin comes up tails, Peggy surrenders the encryption keys only for the edges that actually form the Hamiltonian cycle. Victor decrypts these edges and verifies that they do indeed form a cycle of the correct length.
An impostor ('Pamela') can try to impersonate Peggy, and has a 50% chance of successfully fooling Victor in any particular round. There are two possible impersonation strategies. Pamela can send an encryption of Peggy's graph G. In this case, she escapes detection if Victor throws heads; she reveals the encryption, and Victor verifies that the graph is indeed G. But if Victor throws tails, Pamela is caught. She is required to reveal the keys of a set of edges that make up a Hamiltonian cycle of G, and she can't do that, because she doesn't know one.
The other strategy that Pamela can follow is to prepare an encryption of some other graph H for which she does know a Hamiltonian cycle. In this case she is safe if Victor throws tails; she reveals the cycle, and, since Victor never sees the rest of the edges, he never learns that the graph was H and not G. But if Victor throws heads, Pamela is required to reveal the entire graph, and Victor will see that it is not G.
By playing twenty rounds of this game, Victor can reduce the probability of being fooled by Pamela to a mere 2-20. By playing more rounds, Victor can reduce the probability as far as desired.
The information revealed by Peggy does not give Victor any information at all about the Hamiltonian cycle of G. To see this, note that Victor can manufacture a transcript of the game without talking to Peggy at all. He can select a sequence of heads and tails, and then prepare hypothetical replies from Peggy, without ever knowing the Hamiltonian cycle himself, by following the appropriate impostor strategy in each round. The transcript itself, and the information it contains, has no clue about the legitimacy of Peggy's identity.
Peggy proves her identity not because she can give the right answers, but because she can give the right answers without knowing what the questions will be.
See also
