After showing that last week’s protocol for quadratic residuosity is indeed zero-knowledge, we move on to the formal definition of proof of knowledge, and we show that the quadratic residuosity protocol is also a proof of knowledge.
1. The Quadratic Residuosity Protocol
Last time we considered the following protocol for quadratic residuosity:
- Verifier’s input: an integer (product of two unknown odd primes) and a integer ;
- Prover’s input: and a square root such that .
- The prover picks a random and sends to the verifier
- The verifier picks at random and sends to the prover
- The prover sends back if or if
- The verifier cheks that if or that if , and accepts if so.
Today we show that it is zero knowledge, that is,
Theorem 1 For every verifier algorithm of complexity there is a simulator algorithm of average complexity such that for every odd composite , every which is a quadratic residue and every square root of of , the distributions
2. Proofs of Knowledge
Suppose that is a language in NP; then there is an NP relation computable in polynomial time and polynomial such that if and only if there exists a witness such that (where we use to denote the length of a bit-string ) and .
Recall the definition of soundness of a proof system for : we say that the proof system has soundness error at most if for every and for every cheating prover strategy the probability that accepts is at most . Equivalently, if there is a prover strategy such that the probability that accepts is bigger than , then it must be the case that . This captures the fact that if the verifier accepts then it has high confidence that indeed .
In a proof-of-knowledge, the prover is trying to do more than convince the verifier that a witness exists proving ; he wants to convince the verifier that he (the prover) knows a witness such that . How can we capture the notion that an algorithm “knows” something?
Definition 2 (Proof of Knowledge) A proof system for an NP relation is a proof of knowledge with knowledge error at most and extractor slowdown if there is an algorithm (called a knowledge extractor) such that, for every verifier strategy of complexity and every input , if
then outputs a such that in average time at most
In the definition, giving as an input to means to give the code of to . A stronger definition, which is satisfied by all the proof systems we shall see, is to let be an oracle algorithm of complexity , and allow to have oracle access to . In such a case, “oracle access to a verifier strategy” means that is allowed to select the randomness used by , to fix an initial part of the interaction, and then obtain as an answer what the next response from would be given the randomness and the initial interaction.
Theorem 3 The protocol for quadratic residuosity of the previous section is a proof of knowledge with knowledge error and extractor slowdown 2.