Cryptography Reference
In-Depth Information
Prover
Verifier
x
−−−−−−−−−−−−−−−−−−−→
e
←−−−−−−−−−−−−−−−−−−−
v
,
r
2
pick
r
,
x
=
mod
n
pick
e
=
0or1
y
−−−−−−−−−−−−−−−−−−−→
rs
e
y
=
mod
n
check
y
2
v
e
≡
x
(
mod
n
)
Figure 11.1.
One round of the basic Fiat-Shamir protocol.
See Fig. 11.1.) This interactive proof is obviously complete: if the prover and the verifier
behave as specified, then the final check of each round leads to
y
2
e
r
2
(
s
2
)
e
r
2
v
≡
v
≡
≡
x
(mod
n
)
.
The difference between the Goldwasser-Micali-Rackoff protocol and this version
of the Fiat-Shamir protocol is that the former was stated as a “zero-knowledge proof
of membership,” i.e. a proof that
is a quadratic residue, and the latter was stated as a
“zero-knowledge proof of knowledge,” i.e. a proof that the prover owns a square root
of
v
v
. The latter version is more practical from a cryptographic perspective since one
frequently has to identify itself by some kind of proof of ownership. People traditionally
say that the protocol is not completely zero-knowledge and does reveal one bit of
information: that
was not a square, the protocol would eventually fail.
Since distinguishing squares from non-squares is hard in
Z
n
, this is actually one bit
of information. This is however not a weakness, because people who want to retrieve
information are dishonest verifiers, and people who choose
v
is a square. If
v
not to be square are
dishonest provers. So we do not really care about what kind of interaction comes out
between a dishonest prover and a dishonest verifier.
v
Soundness is easy: First of all, we notice that if the prover is able to answer the two
possible challenges
e
1 in a single round with commitment
x
, it means
that he can compute
y
0
and
y
1
such that
=
0 and
e
=
y
0
≡
y
1
v
x
≡
(mod
n
)
.
y
1
mod
n
such that
z
2
Therefore, he can produce
z
(mod
n
). Let us now
consider a dishonest prover who is able to pass the protocol with probability
p
=
y
0
/
≡
v
=
2
−
t
and let us construct an extractor. Let
p
0
be the probability that the prover
is not able to answer both challenges in any round of a protocol. Clearly, we have
p
+
ε
p
0
2
−
t
≤
+
(1
−
p
0
), hence
ε
p
0
≤
−
2
−
t
≤
−
ε.
1
1
1
−
)
1
1
ε
Therefore, if we iterate
rounds, we have a probability greater than (1
−
ε
which is
ε
e
−
1
that the prover can answer two challenges in a single round. The
extractor works as follows: we iterate many times the protocol with a honest verifier. In
each round, we reset the prover and we ask the other challenge. If the prover happens to
approximately 1
−
Search WWH ::
Custom Search