| Zero-knowledge Proof |
Website Links For Proof |
Information AboutZero-knowledge Proof |
| CATEGORIES ABOUT ZERO-KNOWLEDGE PROOF | |
| cryptographic protocols | |
| theory of cryptography | |
|
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-knowledge: 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 System s. The third is what makes the proof zero-knowledge. Research in zero-knowledge proofs has been motivated by Authentication systems where one party wants 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. This is called a "zero-knowledge proof of knowledge". However, a password is typically too small or insufficiently random to be used in many schemes for zero-knowledge proofs of knowledge. A Zero-knowledge Password Proof is a special kind of zero-knowledge proof of knowledge that addresses the limited size of passwords. 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. One of the most fascinating uses of zero-knowledge proofs within cryptographic protocols is to enforce honest behavior while maintaining privacy. Roughly, the idea is to force a user to prove, using a zero-knowledge proof, that its behavior is correct according to the protocol. Because of soundness, we know that the user must really act honestly in order to be able to provide a valid proof. Because of zero knowledge, we know that the user does not compromise the privacy of its secrets in the process of providing the proof. This application of zero-knowledge proofs was first used in the ground-breaking paper of Goldreich , Micali , and Wigderson on Secure Multiparty Computation . CAVE STORY There is a well-known story presenting some of the ideas of zero-knowledge proofs, first published by Jean-Jacques Quisquater et al. in their "How to Explain Zero-Knowledge Protocols to Your Children".http://www.dice.ucl.ac.be/crypto/publications/1990/alibaba.pdf 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 . In this story, Peggy has uncovered the secret word used to open a magic door in a cave. The cave is shaped like a circle, with the magic door at one end and the entrance at the other. Victor says he'll pay her for the secret, but not until he's sure that she really knows it. Peggy says she'll tell him the secret, but not until she receives the money. They devise a scheme by which Peggy can prove that she knows the word without telling it to Victor. First, Victor waits outside the cave as Peggy goes in. We label the left and right paths from the entrance A and B. She randomly takes either path A or B. Then, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random. Providing she really does know the magic word, this is easy: she opens the door, if necessary, and returns along the desired path. However, suppose she does not know the word. Then, she can only return by the named path if Victor gives the name of the same path that she entered by. Since Victor chooses A or B at random, she has at most a 50% chance of guessing correctly. If they repeat this trick many times, say 20 times in a row, her chance of successfully anticipating all of Victor's requests becomes vanishingly small, and Victor is convinced that she knows the secret. EXAMPLE We can extend these ideas to a more realistic cryptography scenario. 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 believed to be 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 a game.
During any given round, Peggy does not know which question she will be asked until after she has already given Victor the graph. Therefore she must be prepared to answer both questions, which means that the graph she gives Victor must be equivalent to ''G'' and that she must be able to demonstrate a Hamiltonian cycle in the graph. Because only Peggy would always be able to answer both questions, Victor (after a sufficient number of rounds) becomes convinced that Peggy is who she says she is. However, Peggy's answers do not compromise her secret knowledge of the Hamiltonian cycle in ''G''. On 50% of the rounds, Victor will learn of a Hamiltonian cycle in an encrypted graph. Because he is only given enough information to decrypt the cycle, and not the entire graph, he still can't locate the cycle in ''G''. On the other 50% of the rounds, Victor will learn no new information, as Peggy will simply prove that the encrypted graph is ''G'', and ''G'' is already public. An impostor ('Pamela') can try to impersonate Peggy. In order to answer both of Victor's questions correctly, Pamela would have to know a Hamiltonian cycle in ''G''. Because she does not, she only 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. HISTORY AND RESULTS Zero-knowledge proofs were first conceived in ) 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:
The quadratic nonresidue problem has both an NP and a '''co-NP''' algorithm, and so lies in the intersection of NP and '''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 modulus is not a Blum Integer Oded Goldreich. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript. 1985.. s, 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 knowledgeMichael 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.. Not liking to make unnecessary assumptions, many theorists sought a way to eliminate the necessity of One Way Function s. One way this was done was with ''multi-prover interactive proof systems'' (see Interactive Proof System ), which have multiple independent provers instead of only one, allowing the verifier to "cross-examine" the provers in isolation to avoid being misled. It can be shown that, without any intractability assumptions, all languages in NP have zero-knowledge proofs in such a systemM. Ben-or, Shafi Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions . ''Proceedings of the 20th ACM Symposium on Theory of Computing'', p.113-121. 1988. It turns out that in an Internet-like setting, where multiple protocols may be executed concurrently, building zero-knowledge proofs is more challenging. The line of research investigating concurrent zero-knowledge proofs was initiated by the work of Dwork, Naor, and Sahai Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent Zero Knowledge. ''Journal of the ACM (JACM)'', v.51 n.6, p.851-898, November 2004.. REFERENCES SEE ALSO EXTERNAL LINKS
|
|
|