TY - JOUR

T1 - Hash Function Requirements for Schnorr Signatures

AU - Neven, Gregory

AU - Smart, Nigel

AU - Warinschi, Bogdan

N1 - Other identifier: 2001023

PY - 2009

Y1 - 2009

N2 - We provide two necessary conditions on hash functions
for the Schnorr signature scheme to be secure, assuming compact
group representations such as those which occur in elliptic curve
groups. We also show, via an argument in the generic group model,
that these conditions are sufficient. Our hash function security
requirements are variants of the standard notions of preimage and
second preimage resistance. One of them is in fact equivalent to
the Nostradamus attack by Kelsey and Kohno (Eurocrypt~2006), and,
when considering keyed compression functions, both are closely
related to the ePre and eSec notions by Rogaway and Shrimpton
(FSE~2004).
Our results have a number of interesting implications in practice.
First, since security does not rely on the hash function being
collision resistant, Schnorr signatures can still be securely
instantiated with SHA-1/SHA-256, unlike DSA signatures. Second,
we conjecture that our properties require $O(2^n)$ work to solve
for a hash function with $n$-bit output, thereby allowing the
use of shorter hashes and saving twenty-five percent in signature size.
And third, our analysis does not reveal any significant difference in
hardness between forging signatures and computing discrete
logarithms, which plays down the importance of the loose
reductions in existing random-oracle proofs, and seems to support
the use of ``normal-size'' groups.

AB - We provide two necessary conditions on hash functions
for the Schnorr signature scheme to be secure, assuming compact
group representations such as those which occur in elliptic curve
groups. We also show, via an argument in the generic group model,
that these conditions are sufficient. Our hash function security
requirements are variants of the standard notions of preimage and
second preimage resistance. One of them is in fact equivalent to
the Nostradamus attack by Kelsey and Kohno (Eurocrypt~2006), and,
when considering keyed compression functions, both are closely
related to the ePre and eSec notions by Rogaway and Shrimpton
(FSE~2004).
Our results have a number of interesting implications in practice.
First, since security does not rely on the hash function being
collision resistant, Schnorr signatures can still be securely
instantiated with SHA-1/SHA-256, unlike DSA signatures. Second,
we conjecture that our properties require $O(2^n)$ work to solve
for a hash function with $n$-bit output, thereby allowing the
use of shorter hashes and saving twenty-five percent in signature size.
And third, our analysis does not reveal any significant difference in
hardness between forging signatures and computing discrete
logarithms, which plays down the importance of the loose
reductions in existing random-oracle proofs, and seems to support
the use of ``normal-size'' groups.

M3 - Article (Academic Journal)

VL - 3(1)

SP - 69

EP - 87

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

ER -