Zero-knowledge proof
|
|
In cryptography, a zero-knowledge proof is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.
A zero-knowledge proof must satisfy three properties:
- Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
- Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
- Zero-knowledgeness: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proven (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier.
The first two of these are properties of more general interactive proof systems. The third is what makes the proof zero-knowledge.
A common use of a zero-knowledge proof is in authentication systems where one party wants to be able to prove its identity to a second party via some secret information (such as a password) but doesn't want the second party to learn anything about this secret.
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability (called the soundness error) that a cheating prover will be able to convince the verifier of a false statement. However, there are standard techniques to decrease the soundness error to any arbitrarily small value.
| Contents |
Example strategy
It is common practice to label the two parties in a zero-knowledge proof as Peggy (the prover of the statement) and Victor (the verifier of the statement). Sometimes P and V are known instead as Pat and Vanna.
Say that 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 (most easily, she could have created the edges forming the cycle first and then added other edges). 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 (and almost certainly cannot make one because of the NP-completeness of the problem and the large graph size).
The other strategy that Pamela can follow is to prepare an encryption of some other graph H with the same number of edges and vertices, 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.
History and results
Zero-knowledge proofs were first conceived in 1985 by Shafi Goldwasser et al. in a draft of "The knowledge complexity of interactive proof-systems". 1 While this landmark paper did not invent interactive proof systems, it did invent the IP hierarchy of interactive proof systems (see interactive proof system) and conceived the concept of knowledge complexity, a measurement of the amount of knowledge about the proof transferred from the prover to the verifier. They also gave the first zero-knowledge proof for a concrete problem, that of deciding quadratic nonresidues mod m. In their own words:
Of particular interest is the case where this additional knowledge is essentially 0 and we show that [it] is possible to interactively prove that a number is quadratic non residue mod m releasing 0 additional knowledge. This is surprising as no efficient algorithm for deciding quadratic residuosity mod m is known when m’s factorization is not given. Moreover, all known NP proofs for this problem exhibit the prime factorization of m. This indicates that adding interaction to the proving process, may decrease the amount of knowledge that must be communicated in order to prove a theorem.
The quadratic nonresidue problem has both an NP and a co-NP algorithm, and so lies in NP intersect co-NP. This was also true of several other problems for which zero-knowledge proofs were subsequently discovered, such as an unpublished proof system by Oded Goldreich verifying that a two-prime moduli is not a Blum integer.2
Oded Goldreich et al. took this one step further, showing that, assuming the existence of unbreakable encryption, one can create a zero-knowledge proof system for the NP-complete graph coloring problem with three colors. Since every problem in NP can be efficiently reduced to this problem, this means that, under this assumption, all problems in NP have zero-knowledge proofs. 3 The reason for the assumption is that, as in the above example, their protocols require encryption. A commonly cited sufficient condition for the existence of unbreakable encryption is the existence of one-way functions, but it is conceivable that some physical means might also achieve it.
On top of this, they also showed that the graph nonisomorphism problem, the complement of the graph isomorphism problem, has a zero-knowledge proof. This problem is in co-NP, but is not currently known to be in either NP or any practical class. More generally, Goldreich, Goldwasser et al. would go on to show that, also assuming unbreakable encryption, there are zero-knowledge proofs for all problems in IP=PSPACE, or in other words, anything that can be proved by an interactive proof system can be proved with zero-knowledge.4
Not liking to make unnecessary assumptions, many theorists sought a way to eliminate the requirement of unbreakable encryption. One way this was done was with multi prover interactive proof systems (see interactive proof system), which have two independent provers instead of one, allowing the verifier to "cross-examine" the provers to avoid being misled. It can be shown that, without any assumptions, all languages in NP have zero-knowledge proofs in such a system. 5
References
1. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (http://portal.acm.org/citation.cfm?id=63434). Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Draft. Extended abstract (http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf) 2. Oded Goldreich. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript. 1985. 3. Oded Goldreich, Silvio Micali, Avi Wigderson. Proofs that yield nothing but their validity (http://portal.acm.org/citation.cfm?id=116852). Journal of the ACM, volume 38, issue 3, p.690-728. July 1991. 4. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Hastad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. S. Goldwasser, editor. In Advances in Cryptology--CRYPTO '88, volume 403 of Lecture Notes in Computer Science, p.37-56. Springer-Verlag, 1990, 21-25. August 1988. 5. M. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions (http://theory.lcs.mit.edu/~cis/pubs/shafi/1988-stoc-bgkw.pdf). Proceedings of the 20th ACM Symposium on Theory of Computing, p.113-121. 1988.See also
External links
- Applied Kid Cryptography (http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/waldo.html) – A simple explanation of zero-knowledge proofs using Where's Waldo? as an example
- How to construct zero-knowledge proof systems for NP (http://www.wisdom.weizmann.ac.il/~oded/gmw1.html)
- An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products (http://www.cs.ucsd.edu/users/daniele/papers/GMR.html)
- Preliminary zero-knowledge proof (http://www.julienstern.org/files/andos/node11.html)da:Vidensløse beviser