Cryptography Reference
In-Depth Information
Prover
Verifier
x
−−−−−−−−−−−−−−→
e
1
,
e
k
←−−−−−−−−−−−−−−
v
1
,
,
v
k
,
r
2
pick
r
,
x
=
±
mod
n
pick
e
1
,
,
e
k
=
0or1
y
−−−−−−−−−−−−−−→
rs
e
1
s
e
k
=
y
mod
n
v
e
k
≡±
check
y
2
v
e
1
x
(
mod
n
)
Figure 11.2.
One round of the Feige-Fiat-Shamir protocol.
Protocol
: Perform
t
rounds in which
1. the prover picks a random
r
and sends a
commitment x
r
2
=±
mod
n
to
the verifier,
2. the verifier sends random bits
e
1
,...,
e
k
as a
challenge
to the prover,
s
e
k
k
mod
n
to the verifier,
4. the verifier aborts the protocol and rejects unless
y
2
rs
e
1
1
3. the prover sends the
response y
=
...
e
1
1
e
k
k
v
...v
≡±
x
(mod
n
).
(See Fig. 11.2.) After
t
successful rounds, the verifier accepts.
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
1
e
k
k
r
2
(
s
1
v
1
)
e
1
(
s
k
v
k
)
e
k
r
2
(
1)
b
1
+···+
b
k
v
···
v
≡
...
≡
−
≡±
x
(mod
n
)
.
It is also easy to cheat with probability 2
−
k
in each iteration (thus with prob-
ability 2
−
kt
): if we can predict the challenge
e
1
,...,
e
k
(which we can with prob-
ability 2
−
k
), we can just pick a random response
y
and compute the commitment
x
e
k
e
1
1
y
2
k
mod
n
at random. This property is actually used for proving the
zero-knowledge property.
=±
v
...v
Let
G
be the subgroup of
Z
n
of all
z
such that the Jacobi symbol (
z
/
n
)is
+
1. We notice that the
x
generated by the right prover is a random element of
G
with uniform distribution. If we predict to have a challenge
e
0
and we gener-
ate
x
as above, we also obtain a random
x
G
with uniform distribution, which is
further independent from the guessed challenge
e
0
: let
∈
e
1
1
e
k
k
e
0
denote
v
v
...v
mod
n
.We
have
1
2
1
2
P
y
[
1
#
G
P
e
[
e
]
y
2
e
y
2
e
]P
e
[
e
]
Pr
x
,
e
[
x
,
e
]
=
Pr
y
,
e
[
±
=
x
|
v
,
e
]
=
±
=
x
|
v
=
.
Therefore the generated
x
is independent from the guessed
e
0
. One problem is that
the challenge
e
may be chosen by the malicious verifier with an unusual distribution,
depending on
x
. But since
x
is independent from
e
0
, which is moreover chosen with
the uniform distribution, the probability Pr[
e
x
] must be 2
−
k
. Therefore if we
play with the verifier and make a reset after each failure, we can simulate one round
after about 2
k
e
0
=
|
trials. We thus generate (
x
,
e
,
y
) with the same distribution as the real
Search WWH ::
Custom Search