Scribed by Anindya De
Summary
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
and
are identical.
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.