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.
Search WWH ::




Custom Search