Cryptography Reference
In-Depth Information
protocol then works in rounds, where each round can be formally expressed as
illustrated in Protocol 17.1. In this setting, A is the prover and B is the verifier.
Protocol 17.1
A round in the Fiat-Shamir authentication protocol.
A
B
(
n, x
)
(
n, y
)
r ∈
R
Z
n
t
=
r
2
(mod
n
)
t
−
c
←−
c ∈
R
{
0
,
1
}
s
−→
s ≡ rx
c
(mod
n
)
s
2
?
≡ ty
c
(mod
n
)
(
accept
or
reject
)
∈
R
Z
n
and computes
t
=
r
2
(mod
n
).
This value is sent to B. B, in turn, randomly selects a bit
c
In every round, A randomly selects
r
and uses it
to challenge A. If
c
=0, then A must respond with
s
=
r
and B must verify that
s
2
∈
R
{
0
,
1
}
t
(mod
n
). If, however,
c
=1, then A must respond with
s
=
rx
(mod
n
)
and B must verify that
s
2
≡
ty
(mo d
n
). In either case, the authentication is
accepted or rejected (depending on the outcome of the corresponding verification
step). The protocol is complete, because
≡
s
2
r
2
(
x
c
)
2
t
(
x
2
)
c
ty
c
(mod
n
)
.
≡
≡
≡
To show that it is also sound, one must look at the adversary and ask what he
or she can do in every single round. Obviously, the adversary can randomly select a
t
Z
n
, wait for B to provide a challenge
c
, and guess an appropriate
value for
s
. Fortunately (from A's viewpoint), the success probability of this attack is
negligibly small (for any reasonably sized
n
). There are, however, also more subtle
attacks one may think of. If, for example, an adversary were able to properly predict
the challenge
c
, then he or she could prepare himself or herself to provide the correct
response.
∈
R
∈
R
{
0
,
1
}
•
If
c
=0, then the protocol can be executed as normal (i.e., he or she can
randomly select
r
and send
t
=
r
2
(mod
n
) and
s
=
r
to the verifier);
∈
R
Z
n
and compute
t
=
s
2
/y
(mod
n
). These values are then sent to the verifier in the appropriate
protocol steps.
•
If
c
=1, then the adversary can randomly select
s
