Cryptography Reference
In-Depth Information
First note that if values
s
0
and
s
2
satisfy equation (
22.1
) then
s
0
lies in the group generated
by
g
and so is of the form
s
0
=
g
k
for some 0
≤
k<r
. Furthermore, it then follows that
s
2
≡
a
s
1
(mod
r
).
Now the simulator can re-run
A
on the same
h
and the same function
Random
(this
is the re-winding). It follows that
A
will output
s
0
again. The simulator then gives
A
a
challenge
s
1
=
k
+
s
1
. Since
A
is perfect, it responds with
s
2
satisfying equation (
22.1
).
We have
s
2
≡
a
s
1
(mod
r
) and
s
2
≡
a
s
1
(mod
r
). Hence, the simulator can
k
+
k
+
s
1
)
−
1
(mod
r
) and solve the DLP. In other words, if there is
no polynomial-time algorithm for the DLP then there can be no polynomial-time adversary
A
against the protocol.
s
2
)(
s
1
−
compute
a
≡
(
s
2
−
The above proof gives the basic idea, but is not sufficient since we must consider
adversaries that succeed with rather small probability. There are various issues to deal with.
For example,
A
may not necessarily succeed on the first execution of the identification
protocol. Hence, one must consider many executions (
s
i,
0
,
s
i,
1
,
s
i,
2
)for1
t
and
guess the value
i
into which one introduces the challenge
s
i,
1
.Also,
A
may only succeed
for a small proportion of the challenges
s
1
for a given
s
0
(it is necessary for the proof that
A
can succeed on two different choices of
s
1
for the same value
s
0
). This latter issue is not
a problem (since
A
succeeds with noticeable probability, it must succeed for a noticeable
proportion of values
s
1
for most values
s
0
). The former issue is more subtle and is solved
using the Forking Lemma.
The
Forking Lemma
was introduced by Pointcheval and Stern [
433
]. A convenient
generalisation has been given by Bellare and Neven [
33
]. The Forking Lemma deter-
mines the probability that a rewinding attack is successful. More precisely, consider an
algorithm
A
(the adversary against the signature scheme) that takes as input a
Random
function and a list of responses
s
1
to its outputs
s
0
. We will repeatedly choose a
Random
function and run
A
twice, the first time with a set of values (
s
1
,
1
,...,
s
t,
1
) being the
responses in the protocol and the second time with a set (
s
1
,
1
,...,
s
j
−
1
,
1
,
s
j,
1
,...,
s
t,
1
)
of responses for some 1
≤
i
≤
≤
≤
j
t
. Note that
A
will output the same values
s
i,
0
in
≤
≤
both runs when 1
j
. The Forking Lemma gives a lower bound on the proba-
bility that
A
succeeds in the identification protocol in the
j
th execution as desired.
Lemma 1 of [
33
] states that the success probability is at least
p
(
p/t
i
1
/r
) where
p
is the success probability of
A
,
t
is the number of executions of the protocol in each
game and
r
is the size of the set of possible responses. Hence, if
p
is noticeable,
t
is polynomial and 1
/r
is negligible then the simulator solves the DLP with notice-
able probability. We refer to [
33
,
433
] and Section 10.4.1 of Vaudenay [
553
] for further
details.
−
Exercise 22.1.6
Show that if the challenge values
s
1
chosen by a Verifier can be predicted
(e.g., because the Verifier is using a weak pseudorandom number generator) then a malicious
player can impersonate an honest user in the Schnorr identification scheme.
