Summary
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
and
are identical.
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.