Cryptography Reference
In-Depth Information
KeyGen
: This is the same as classic textbook Elgamal encryption. It outputs an algebraic
group, an element
g
of prime order
r
, a public key
h
=
g
a
and a private key 1
≤
a<r
where
a
is uniformly chosen.
Sign
(
g,a,
m
): Choose uniformly at random 0
≤
k<r
, compute
s
0
=
g
k
,
s
1
=
H
(
m
s
0
)and
s
2
=
k
+
a
s
1
(mod
r
), where the binary string
s
1
is interpreted as an integer in the usual way.
The signature is (
s
1
,
s
2
).
Ve r i f y
(
g,h,
m
,
(
s
1
,
s
2
)): Ensure that
h
is a valid public key for the user in question then test
whether
s
1
=
H
(
m
g
s
2
h
−
s
1
)
.
Box 22.1
Schnorr signature scheme
compute
s
2
=
k
+
a
s
1
≡
20
+
11
·
9
≡
26 (mod
r
). The signature is (
s
1
,
s
2
)
=
(1001
,
26).
To verify the signature one computes
g
s
2
h
−
s
1
169
26
47
−
9
=
≡
225 (mod
p
)
and checks that
s
1
=
H
(
m
11100001).
Exercise 22.1.10
Show that the Verify algorithm does succeed when given a pair (
s
1
,
s
2
)
output by the Sign algorithm.
22.1.3 Security of Schnorr signatures
The security of Schnorr signatures essentially follows from the same ideas as used in
Theorem
22.1.5
. In particular, the security depends on the discrete logarithm problem
(rather than CDH or DDH as is the case for Elgamal encryption). However, since the
challenge is now a function of the message
m
and
s
0
, the exact argument of Theorem
22.1.5
cannot be used directly.
One approach is to replace the hash function by a random oracle
H
(see Section
3.7
).
The simulator can then control the values of
H
, and the proof of Theorem
22.1.5
can be
adapted to work in this setting. A careful analysis of Schnorr signatures in the random
oracle model, using this approach and the Forking Lemma, was given by Pointcheval and
Stern [
433
]. We refer to Theorem 14 of their paper for a precise result in the case where
the output of
H
is (
)
∗
. A proof is also given in Section 10.4.2 of Vaudenay [
553
]. An
analysis of the case where the hash function
H
maps to
Z
/r
Z
l
where
l<
log
2
(
r
)isgiven
{
0
,
1
}
by Neven, Smart and Warinschi [
406
].
There is no known proof of the security of Schnorr signatures in the standard model (even
under very strong assumptions about the hash function). Paillier and Vergnaud [
426
]give
evidence that one cannot give a reduction, in the standard model, from signature forgery for
Schnorr signatures (with
H
mapping to
Z
/r
Z
) to DLP. More precisely, they show that if
