Cryptography Reference
In-Depth Information
s
0
to the Verifier. The Verifier sends a “challenge” 1
≤
s
1
<r
to the Prover. The Prover
returns
s
2
=
k
+
a
s
1
(mod
r
). The Verifier then checks whether
g
s
2
s
0
h
s
1
=
(22.1)
and accepts the proof if this is the case. In other words, the Prover has successfully identified
themself to the Verifier if the Verifier accepts the proof.
Exercise 22.1.1
Show that the Verifier in an execution of the Schnorr identification scheme
does accept the proof when the Prover follows the steps correctly.
Exercise 22.1.2
Let
p
=
311 and
r
=
31
|
(
p
−
1). Let
g
=
169, which has order
r
.Let
g
a
a
47 (mod
p
). Which of the following is a transcript (
s
0
,
s
1
,
s
2
)ofa
correctly performed execution of the Schnorr identification scheme?
=
11 and
h
=
≡
(15
,
10
,
12)
,
(15
,
10
,
27)
,
(16
,
10
,
12)
,
(15
,
16
,
0)
.
Security of the private key
Unlike public key encryption (at least, under passive attacks), with identification schemes
and digital signature schemes, a user is always outputting the results of computations involv-
ing their private key. Hence, it is necessary to ensure that we do not leak information about
the private key. Therefore, we now explain why executions of the Schnorr identification
protocol do not leak the private key.
The idea is that, since
k
is chosen uniformly at random, the private key
a
is completely
hidden. More precisely, for any pair (
s
1
,
s
2
) and every 1
≤
a<r
there is some integer
0
a
s
1
(mod
r
). Now, if
k
were known to the verifier then they
could solve for
a
. But, since the discrete logarithm problem is hard, it is computationally
infeasible to determine any significant information about the distribution of
k
from
s
0
.
Hence,
s
2
leaks essentially no information about
a
. Furthermore, there are no choices for
s
1
that more readily allow the verifier to determine
a
. This concept is known as “zero
knowledge” and it is beyond the scope of this topic to discuss it further. For security,
k
must be chosen uniformly at random; see Exercise
22.1.3
and Section
22.3
for attacks if
some information on
k
is known. We stress that such attacks are much stronger than the
analogous attacks for Elgamal encryption (see Exercise
20.4.1
); there the adversary only
learns something about a single message, whereas here they learn the private key!
≤
k<r
such that
s
2
≡
k
+
Exercise 22.1.3
Suppose the random values
k
used by a prover are generated using the
linear congruential generator
k
i
+
1
=
A,B <r
. Suppose
an adversary knows
A
and
B
and sees two protocol transcripts (
s
0
,
s
1
,
s
2
) and (
s
0
,
s
1
,
s
2
)
generated using consecutive outputs
k
i
and
k
i
+
1
of the generator. Show how the adversary
can determine the private key
a
.
Ak
i
+
B
(mod
r
)forsome1
≤
A generalisation of Exercise
22.1.3
, where the modulus for the linear congruential
generator is not
r
, is given by Bellare, Goldwasser and Micciancio [
32
].
