Cryptography Reference
In-Depth Information
answer both challenges, then we extract
z
as above, otherwise we keep on running the
protocol. Our analysis shows that we have a fair chance of extracting the secret within
an order of magnitude of
1
ε
iterations.
It is easy to cheat with probability 2
−
t
: in each round, we start by predicting the
challenge
e
0
. Then we generate
x
e
0
mod
n
for a random
y
and take it as the
commitment. If the challenge
e
chosen by the verifier is equal to
e
0
, then we can answer
it by
y
. Otherwise it fails.
y
2
=
v
This inspires the simulator: we play with the malicious verifier by trying to predict
e
0
and picking
x
=
y
2
v
e
0
mod
n
for a random
y
. The simulator sends
x
to the verifier
=
and receives
e
.If
e
e
0
, the simulator can produce
y
. Otherwise the simulator resets
the verifier and tries again. It can be easily checked that both
x
is uniformly generated
among all quadratic residues modulo
n
. In addition, we can easily check that the
generated
x
in the simulation is independent from
e
0
. Therefore no malicious verifier
can pick
e
and have it equal to
e
0
with probability different from
1
2
. This means that
the simulation works with probability
2
. If it fails, we can just reset the verifier to
the state before the commitment, and try again with other choices for (
e
0
,
y
). The
generated (
x
y
) protocol history will obviously get the same distribution as for
the right interaction between the honest prover and the malicious verifier. Therefore
the verifier has no advantage in playing with the real prover (but a complexity factor
due to the probability of failures in the simulation of Step 2) and the protocol discloses
zero-knowledge.
,
e
,
An additional interesting property of the Fiat-Shamir protocol is that keys can
be
identity-based
: in the Schnorr identification protocol, the key was
y
g
x
mod
p
,
and we had to produce a certificate that
y
actually corresponds to some given identity.
Here, the certificate can be included in the secret key. Actually, if the certificate issuing
authority keeps
p
and
q
, it can choose
=
as the formatted identity string and compute one
square root for
s
to give it to the prover. Here,
v
v
is bound to correspond to some identity.
11.1.3
The Feige-Fiat-Shamir Protocol
The basic Fiat-Shamir protocol has been improved (see Ref. [66]). Here are the speci-
fications of the Feige-Fiat-Shamir protocol.
≡
Setup of public parameters
: We generate two prime numbers
p
and
q
such that
p
≡
=
−
q
3
(mod 4). We let
n
pq
and we then erase
p
and
q
. (Note that
1isnot
a quadratic residue modulo both
p
and
q
. Therefore the Jacobi symbol (
−
1
/
n
)
is equal to
+
1.) We also let
k
and
t
be two security parameters (typically,
k
=
5,
4).
Setup of the keys
: The secret key consists of
k
random elements
s
i
∈
Z
n
t
=
for
i
=
1
,...,
k
and
k
random bits
b
1
,...,
b
k
. The public key consists of all
v
i
=
1)
b
i
s
i
(
−
/
mod
n
. (All
v
i
are random residues with Jacobi symbol equal to
+
1.)
Search WWH ::
Custom Search