Paper 2018/069

Reusing Nonces in Schnorr Signatures

Marc Beunardeau, Aisling Connolly, Houda Ferradi, Rémi Géraud, David Naccache, and Damien Vergnaud

Abstract

The provably secure Schnorr signature scheme is popular and efficient. However, each signature requires a fresh modular exponentiation, which is typically a costly operation. As the increased uptake in connected devices revives the interest in resource-constrained signature algorithms, we introduce a variant of Schnorr signatures that mutualises exponentiation efforts. Combined with precomputation techniques (which would not yield as interesting results for the original Schnorr algorithm), we can amortise the cost of exponentiation over several signatures: these signatures share the same nonce. Sharing a nonce is a deadly blow to Schnorr signatures, but is not a security concern for our variant. Our Scheme is provably secure, asymptotically-faster than Schnorr when combined with efficient precomputation techniques, and experimentally $2$ to $6$ times faster than Schnorr for the same number of signatures when using 1\,MB of static storage.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ESORICS 2017
Keywords
Schnorr digital signature efficiency
Contact author(s)
marc beunardeau @ ingenico com
History
2018-01-18: received
Short URL
https://ia.cr/2018/069
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/069,
      author = {Marc Beunardeau and Aisling Connolly and Houda Ferradi and Rémi Géraud and David Naccache and Damien Vergnaud},
      title = {Reusing Nonces in Schnorr Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/069},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/069}},
      url = {https://eprint.iacr.org/2018/069}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.