RSA Security - 2.1.8 What are interactive proofs and zero-knowledge proofs?

Informally, an interactive proof is a protocol between two parties in which one party, called the prover, tries to prove a certain fact to the other party, called the verifier. An interactive proof usually takes the form of a challenge-response protocol, in which the prover and the verifier exchange messages and the verifier outputs either "accept" or "reject" at the end of the protocol. Apart from their theoretical interest, interactive proofs have found applications in cryptography and computer security such as identification and authentication. In these situations, the fact to be proved is usually related to the prover's identity, such as the prover's private key.

It is useful for interactive proofs to have the following properties, especially in cryptographic applications:

Completeness. The verifier always accepts the proof if the fact is true and both the prover and the verifier follow the protocol.
Soundness. The verifier always rejects the proof if the fact is false, as long as the verifier follows the protocol.
Zero knowledge. The verifier learns nothing about the fact being proved (except that it is correct) from the prover that he could not already learn without the prover, even if the verifier does not follow the protocol (as long as the prover does). In a zero-knowledge proof, the verifier cannot even later prove the fact to anyone else. (Not all interactive proofs have this property.)

A typical round in a zero-knowledge proof consists of a "commitment" message from the prover, followed by a challenge from the verifier, and then a response to the challenge from the prover. The protocol may be repeated for many rounds. Based on the prover's responses in all the rounds, the verifier decides whether to accept or reject the proof.

Figure 2.8: Ali Baba's Cave (click for a larger image)

Let us consider an intuitive example called Ali Baba's Cave [QG90] (see Figure 2.8). Alice wants to prove to Bob that she knows the secret words that will open the portal at R-S in the cave, but she does not wish to reveal the secret to Bob. In this scenario, Alice's commitment is to go to R or S. A typical round in the proof proceeds as follows: Bob goes to P and waits there while Alice goes to R or S. Bob then goes to Q and shouts to ask Alice to appear from either the right side or the left side of the tunnel. If Alice does not know the secret words (for example, "Open Sesame"), there is only a 50 percent chance she will come out from the right tunnel. Bob will repeat this round as many times as he desires until he is certain Alice knows the secret words. No matter how many times the proof repeats, Bob does not learn the secret words.

There are a number of zero-knowledge and interactive proof protocols in use today as identification schemes. The Fiat-Shamir protocol [FS87] is the first practical zero-knowledge protocol with cryptographic applications and is based on the difficulty of factoring. A more common variation of the Fiat-Shamir protocol is the Feige-Fiat-Shamir scheme [FFS88]. Guillou and Quisquater [GQ88] further improved Fiat-Shamir's protocol in terms of memory requirements and interaction (the number of rounds in the protocol).

Identification schemes based on interactive proofs can usually be transformed into digital signature schemes (see Question 2.2.2 and [FS87]).

Section Index Foreword Chapter 1 Introduction Chapter 2 Cryptography 2.1 Cryptographic Tools 2.2 Simple Applications of Cryptography 2.3 Hard Problems 2.4 Cryptanalysis 2.5 Supporting Tools in Cryptography Chapter 3 Techniques in Cryptography Chapter 4 Applications of Cryptography Chapter 5 Cryptography in the Real World Chapter 6 Laws Concerning Cryptography Chapter 7 Miscellaneous Topics Chapter 8 Further Reading Appendix A Mathematical concepts Appendix B Glossary Appendix C References	Home: Crypto FAQ: Chapter 2 Cryptography: 2.1 Cryptographic Tools 2.1.8 What are interactive proofs and zero-knowledge proofs? Informally, an interactive proof is a protocol between two parties in which one party, called the prover, tries to prove a certain fact to the other party, called the verifier. An interactive proof usually takes the form of a challenge-response protocol, in which the prover and the verifier exchange messages and the verifier outputs either "accept" or "reject" at the end of the protocol. Apart from their theoretical interest, interactive proofs have found applications in cryptography and computer security such as identification and authentication. In these situations, the fact to be proved is usually related to the prover's identity, such as the prover's private key. It is useful for interactive proofs to have the following properties, especially in cryptographic applications: Completeness. The verifier always accepts the proof if the fact is true and both the prover and the verifier follow the protocol. Soundness. The verifier always rejects the proof if the fact is false, as long as the verifier follows the protocol. Zero knowledge. The verifier learns nothing about the fact being proved (except that it is correct) from the prover that he could not already learn without the prover, even if the verifier does not follow the protocol (as long as the prover does). In a zero-knowledge proof, the verifier cannot even later prove the fact to anyone else. (Not all interactive proofs have this property.) A typical round in a zero-knowledge proof consists of a "commitment" message from the prover, followed by a challenge from the verifier, and then a response to the challenge from the prover. The protocol may be repeated for many rounds. Based on the prover's responses in all the rounds, the verifier decides whether to accept or reject the proof. Figure 2.8: Ali Baba's Cave (click for a larger image) Let us consider an intuitive example called Ali Baba's Cave [QG90] (see Figure 2.8). Alice wants to prove to Bob that she knows the secret words that will open the portal at R-S in the cave, but she does not wish to reveal the secret to Bob. In this scenario, Alice's commitment is to go to R or S. A typical round in the proof proceeds as follows: Bob goes to P and waits there while Alice goes to R or S. Bob then goes to Q and shouts to ask Alice to appear from either the right side or the left side of the tunnel. If Alice does not know the secret words (for example, "Open Sesame"), there is only a 50 percent chance she will come out from the right tunnel. Bob will repeat this round as many times as he desires until he is certain Alice knows the secret words. No matter how many times the proof repeats, Bob does not learn the secret words. There are a number of zero-knowledge and interactive proof protocols in use today as identification schemes. The Fiat-Shamir protocol [FS87] is the first practical zero-knowledge protocol with cryptographic applications and is based on the difficulty of factoring. A more common variation of the Fiat-Shamir protocol is the Feige-Fiat-Shamir scheme [FFS88]. Guillou and Quisquater [GQ88] further improved Fiat-Shamir's protocol in terms of memory requirements and interaction (the number of rounds in the protocol). Identification schemes based on interactive proofs can usually be transformed into digital signature schemes (see Question 2.2.2 and [FS87]). Top of Page	2.1 Cryptographic Tools 2.1.1 What is public-key cryptography? 2.1.2 What is secret-key cryptography? 2.1.3 What are the advantages and disadvantages of public-key cryptography compared with secret-key cryptography? 2.1.4 What is a block cipher? 2.1.5 What is a stream cipher? 2.1.6 What is a hash function? 2.1.7 What are Message Authentication Codes? 2.1.8 What are interactive proofs and zero-knowledge proofs? 2.1.9 What are secret sharing schemes?
		Email to a friend Print