Scribed by Anindya De
In this lecture, we show that the protocol for quadratic residuosity discussed last week is indeed zero-knowledge. Next 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. We also start discussing the primitives required to prove that any language in admits a zero-knowledge proof.
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 checks that if or that if , and accepts if it is so.
Clearly, the protocol is complete i.e. if , then the verifier accepts with probability . To show soundness of the protocol, note that if is not a quadratic residue , then for any , both and cannot be quadratic residues in . Hence, in case is not a quadratic residue, the verifier rejects with probability at least .
We now show that the above protocol is also zero knowledge. More precisely, we show the following.
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
Proof: The simulator is defined as follows. It first picks uniformly at random. It also picks uniformly at random. If , set and if , set . Note that irrespective of the value of , is a uniformly random element of . With this simulates the interaction as follows. First, it simulates the prover by sending . If the second round reply from (call it ) is not the same as , then it aborts the simulation and starts again. If not, then clearly is the reply the prover will send for both and . Hence whenever the simulation is completed, the distribution of the simulated interaction is same as the actual interaction. Also observe that is a random bit statistically independent of while is totally dependent on (and probably some other random coin tosses). Hence in expectation, in two trials of the simulation, one will be able to simulate one round of the actual interaction.Hence the expected time required for simulation is the time to simulate twice and the time to do couple of multiplications in . So, in total it is at most .
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 prover 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 prover 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.
Proof: Consider an such that the prover returns the correct answer both when and . More precisely, when , prover returns in the third round of the interaction and if , prover returns in the third round of interaction. If we can find such an , then upon dividing the answers (for the cases when and ) returned by the prover strategy in third round, we can get the value of . Note that if verifier accepts with probability , then by a Markov argument, we get that with probability , a randomly chosen is such that for both and , the prover returns the correct answer. Clearly, the knowledge error of the protocol is and for one particular , the prover strategy is executed twice. So, the extractor slowdown is . Note that in expectation, we will be sampling about times before we get an with the aforementioned property. Hence, the total expected time for running is
3. Uses of Zero Knowledge proofs
In the coming lectures, we shall consider general multi-party protocols, an example of which might be playing “poker over the phone/internet”. In this, one needs to devise a protocol such that mutually distrusting players can play poker or any other game over the internet.
Our approach will be to first devise a protocol for the “honest but curious” case, in which all the players follow the protocol but they do try to gain information about others by simply tracking all the moves in the game. To go to the general case, we will require that every player gives a zero knowledge proof that it played honestly in every round. As one can see, this statement is much more general than say that two graphs are isomorphic. However, it is a statement which has a short certificate and hence is in . This gives motivation for our next topic which is developing zero knowledge protocols for every language in . We shall describe an important primitive for this purpose called commitment schemes.
4. Introduction to Commitment scheme
Consider the situation when Alice and Bob are interacting using a protocol. The protocol may want that at some stage Alice commits to a value so that she cannot go back on it later. Simultaneously, it may also require that it is infeasible for Bob to know what the value is to which Alice has committed unless much later in the interaction (may be when Alice wants to reveal it). This kind of a scheme is called a commitment scheme. A real world situation is the following. Alice writes the value she wants to commit to, on a piece of paper and puts it inside a locked box. Subsequently, she sends the locked box to Bob without its key. In this situation, it is not possible for Alice to repudiate what she had committed to but at the same time unless Bob has the key, he also cannot the value Alice has committed to.
There are two parts to such a protocol. One is that Alice cannot deny her commitment and another is that Bob cannot know the contents without help from Alice. It should be clear that exactly one of these things can be information theoretically hard. That is, we may have exactly one of following two situations: It is information theoretically impossible for Alice to go back on her commitment but only computationally infeasible for Bob to know the commitment without Alice’s consent and vice versa.