|Previous||Table of Contents||Next|
Noninteractive Zero-Knowledge Proofs
Carol cant be convinced because the protocol is interactive, and she is not involved in the interaction. To convince Carol, and anyone else who may be interested, we need a noninteractive protocol.
Protocols have been invented for noninteractive zero-knowledge proofs [477,198,478,197]. These protocols do not require any interaction; Peggy could publish them and thereby prove to anyone who takes the time to check that the proof is valid.
The basic protocol is similar to the parallel zero-knowledge proof, but a one-way hash function takes the place of Victor:
This is amazing: Peggy can publish some data that contains no information about her secret, but can be used to convince anyone of the secrets existence. The protocol can also be used for digital signature schemes, if the challenge is set as a one-way hash of both the initial messages and the message to be signed.
This works because the one-way hash function acts as an unbiased random-bit generator. For Peggy to cheat, she has to be able to predict the output of the one-way hash function. (Remember, if she doesnt know the solution to the hard problem, she can do either (a) or (b) of step (4), but not both.) If she somehow knew what the one-way hash function would ask her to do, then she could cheat. However, there is no way for Peggy to force the one-way function to produce certain bits or to guess which bits it will produce. The one-way function is, in effect, Victors surrogate in the protocolrandomly choosing one of two proofs in step (4).
In a noninteractive protocol, there must be many more iterations of the challenge/reply sequence. Peggy, not Victor, picks the hard problems using random numbers. She can pick different problems, hence different commitment vectors, till the hash function produces something she likes. In an interactive protocol, 10 iterationsa probability of 1 in 210 (1 in 1024) that Peggy can cheatmay be fine. However, thats not enough for noninteractive zero-knowledge proofs. Remember that Mallory can always do either (a) or (b) of step (4). He can try to guess which he will be asked to do, go through steps (1) through (3), and see if he guessed right. If he didnt, he can try againrepeatedly. Making 1024 guesses is easy on a computer. To prevent this brute-force attack, noninteractive protocols need 64 iterations, or even 128 iterations, to be valid.
This is the whole point of using a one-way hash function: Peggy cannot predict the output of the hash function because she cannot predict its input. The commitments which are used as the input are only known after she solves the new problems.
Blum proved that any mathematical theorem can be converted into a graph such that the proof of that theorem is equivalent to proving a Hamiltonian cycle in the graph. The general case that any NP statement has a zero-knowledge proof, assuming one-way functions and therefore good encryption algorithms, was proved in . Any mathematical proof can be converted into a zero-knowledge proof. Using this technique, a researcher can prove to the world that he knows the proof of a particular theorem without revealing what that solution is. Blum could have published these results without revealing them.
There are also minimum-disclosure proofs . In a minimum-disclosure proof, the following properties hold:
Zero-knowledge proofs have an additional condition:
There is considerable mathematical difference between proofs that are only minimum-disclosure and those that are zero-knowledge. That distinction is beyond the scope of this book, but more sophisticated readers are welcome to peruse the references. The concepts were introduced in [626,619,622]. Further elaboration on their ideas, based on different mathematical assumptions, were developed in [240,319,239].
There are also different kinds of zero-knowledge proofs:
Over the years, extensive work, both theoretical and applied, has been done on minimum-disclosure and zero-knowledge proofs. Mike Burmester and Yvo Desmedt invented broadcast interactive proofs, where one prover can broadcast a zero-knowledge interactive proof to a large group of verifiers . Cryptographers proved that everything that can be proven with an interactive proof can also be proven with a zero-knowledge interactive proof [753,137].
A good survey article on the topic is . For additional mathematical details, variations, protocols, and applications, consult [590,619,240,319,620,113,241,1528,660,238,591,617,510,592,214,104,216,832,
97,939,622,482,615,618,215,476,71]. A lot has been written on this subject.
In the real world, we often use physical tokens as proofs of identity: passports, drivers licenses, credit cards, and so on. The token contains something that links it to a person: a picture, usually, or a signature, but it could almost as easily be a thumbprint, a retinal scan, or a dental x-ray. Wouldnt it be nice to do the same thing digitally?
Using zero-knowledge proofs as proofs of identity was first proposed by Uriel Feige, Amos Fiat, and Adi Shamir [566,567]. Alices private key becomes a function of her identity. Using a zero-knowledge proof, she proves that she knows her private key and therefore proves her identity. Algorithms for this can be found in Section 23.11.
This idea is quite powerful. It allows a person to prove his identity without any physical token. However, its not perfect. Here are some abuses.
|Previous||Table of Contents||Next|