Paper 2015/169

Short Schnorr signatures require a hash function with more than just random-prefix resistance

Daniel R. L. Brown

Abstract

Neven, Smart and Warinschi (NSW) proved, in the generic group model, that full-length Schnorr signatures require only random-prefix resistant hash functions to resist passive existential forgery. Short Schnorr signatures halve the length of the hash function, and have been conjectured to provide a similar level of security. The NSW result is too loose to provide a meaningful security for short Schnorr signatures, but Neven, Smart and Warinschi conjecture that this is mere artefact of the proof technique, and not an essential deficiency of the short Schnorr signatures. In particular, this amounts to a conjecture that short Schnorr signature are secure under the same set of assumptions, namely random-prefix resistance of the hash function. This report provides a counterexample to the latter conjecture, in other words, a separation result. It finds a hash function that seems to suggest random-prefix resistance does not suffice for short Schnorr signatures. In other words, the loose reduction implicit in the NSW theorem is as tight as possible. Obviously, this result does not preclude the possibility of another proof for short Schnorr signatures, based on different hash function security properties such as preimage resistance.

Note: Rough draft

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
digital signatures
Contact author(s)
dbrown @ certicom com
History
2015-02-27: received
Short URL
https://ia.cr/2015/169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/169,
      author = {Daniel R.  L.  Brown},
      title = {Short Schnorr signatures require a hash function with more than just random-prefix resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2015/169},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/169}},
      url = {https://eprint.iacr.org/2015/169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.