Cryptography Reference
In-Depth Information
there is a reduction of a certain type (which they call an algebraic reduction) in the standard
model from signature forgery for Schnorr signatures to DLP then there is an algorithm for
the “one-more DLP”. We refer to [
426
] for the details.
We now discuss some specific ways to attack the scheme:
1. Given a signature (
s
1
,
s
2
) on message
m
, if one can find a message
m
such that
H
(
m
g
s
2
h
−
s
1
) then one has a signature also for the message
m
.
This fact can be used to obtain an existential forgery under a chosen-message attack.
While one expects to be able to find hash collisions after roughly 2
l/
2
computations
of
H
(see Section
3.2
), what is needed here is not a general hash collision. Instead,
we need a collision of the form
H
(
m
g
s
2
h
−
s
1
)
H
(
m
=
g
s
2
h
−
s
1
is
not known
until a signature (
s
1
,
s
2
)on
m
has been obtained. Hence, the adversary must first
output a message
m
, then get the signature (
s
1
,
s
2
)on
m
and then find
m
such that
H
(
m
H
(
m
R
)
=
R
) where
R
=
H
(
m
R
). This is called the random-prefix second-preimage problem in
Definition 4.1 of [
406
]. When
R
is sufficiently large it seems that solving this problem
is expected to require around 2
l
computations of
H
.
2. There is a passive existential forgery attack on Schnorr signatures if one can compute
preimages of
H
of a certain form. Precisely, choose any (
s
1
,
s
2
) (for example, if the
output of
H
is highly non-uniform then choose
s
1
to be a “very likely” output of
H
),
compute
R
R
)
=
g
s
2
h
−
s
1
, then find a bitstring
m
such that
H
(
m
=
R
)
=
s
1
. This attack is
prevented if the hash function is hard to invert.
Hence, given a security parameter
κ
(so that breaking the scheme is required to take
more than 2
κ
bit operations) one can implement the Schnorr signature scheme with
r
2
2
κ
≈
128, 2
255
<r<
2
256
and
l
=
κ
. For example, taking
κ
=
and
l
=
128 gives signatures of
384 bits.
}
∗
. Can a pair (
s
1
,
s
2
) be a Schnorr
signature on the same message
m
for two different public keys? Are there any security
implications of this fact?
Exercise 22.1.11
Fix
g
∈
G
of order
r
and
m
∈{
0
,
1
22.1.4 Efficiency considerations for Schnorr signatures
The Sign algorithm performs one exponentiation, one hash function evaluation and one
computation modulo
r
. The Verify algorithm performs a multi-exponentiation
g
s
2
h
−
s
1
where 0
s
1
<
2
l
and one hash function evaluation. Hence, signing is
≤
s
2
<r
and 1
≤
faster than verifying.
There are a number of different avenues to speed up signature verification, depending
on whether
g
is fixed for all users, whether one is always verifying signatures with respect
to the same public key
h
or whether
h
varies, etc. We give a typical optimisation in
Example
22.1.13
. More dramatic efficiency improvements are provided by online/offline
signatures (see Section
22.4
), server-aided signatures etc.