Cryptography Reference
In-Depth Information
In either case, it is not possible for the adversary to prepare himself or herself
for both cases (otherwise, he or she could extract the private key
x
). If, for example,
the adversary were able to prepare
s
0
for
c
=0(i.e.,
s
0
=
r
)and
s
1
for
c
=1(i.e.,
s
1
=
rx
), then he or she could easily compute
x
=
s
1
/s
0
.
Consequently, the attacker has a probability of 1
/
2 to cheat in every protocol
round. This suggests that the protocol must be executed in multiple rounds (until an
acceptable cheating probability is reached). If, for example, the protocol is repeated
k
times (where
k
is a security parameter), then the cheating probability is 1
/
2
k
.
The Fiat-Shamir authentication protocol has the zero-knowledge property,
because it is possible to efficiently simulate the protocol execution transcripts and
to compute
t
,
c
,and
s
(with the same probability distributions) without interacting
with the prover. Furthermore, there are several variations of the basic Fiat-Shamir
authentication protocol:
•
The
k
rounds can be performed in parallel to reduce the number of rounds. In
this case, the values
t
,
c
,and
s
are replaced with vectors of
k
values each. This
variation was actually the one proposed by Fiat and Shamir in their original
paper [23]. It is not zero knowledge, because the simulation cannot be done
efficiently.
•
Another parallel version is for A to have
z
different private keys
x
1
,...,x
z
(and hence public keys
y
1
,...,y
z
) [24]. As before, the first message is
t
=
r
2
(mod
n
), but now the challenge consists of
z
bits
c
1
,...,c
z
and the
prover must respond with
s
=
r
i
=1
x
c
i
(mod
n
). In this case, the cheating
i
probability is at most 2
−z
.
Other variations are described and discussed in the literature. For example,
the basic Fiat-Shamir authentication protocol can be generalized in a way that
e
th
powers (where
e
is a prime) are used (instead of squares), and the challenge
c
is
a value between 0 and
e
1 (instead of 0 or 1). The resulting protocol is due to
Louis C. Guillou and Jean-Jacques Quisquater [25]. Similar to RSA, it is assumed
that extracting
e
th
roots requires factoring a large integer, and hence it is assumed to
be computationally infeasible.
−
17.3.3
Guillou-Quisquater
Similar to the Fiat-Shamir authentication protocol, the Guillou-Quisquater authenti-
cation protocol works in rounds. A round is illustrated in Protocol 17.2. Again, A is
the prover and B is the verifier.
In every round, A proves that he or she knows the private key
x
that refers
to the public key
y
x
e
(mod
n
). A randomly selects an
r
Z
n
and computes
≡
∈
R
