Hash function requirements for Schnorr signatures

Abstract

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, Lecture Notes in Computer Science 4004: 183–200, 2006), and, when considering keyed compression functions, both are closely related to the ePre and eSec notions by Rogaway and Shrimpton (FSE, Lecture Notes in Computer Science 3017: 371–388, 2004).

Keywords

• schnorr signatures
• generic group model
• hash function