Cryptology ePrint Archive: Report 2018/069

Reusing Nonces in Schnorr Signatures

Marc Beunardeau and Aisling Connolly and Houda Ferradi and Rémi Géraud and 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.

Category / Keywords: public-key cryptography / Schnorr digital signature efficiency

Original Publication (with minor differences): ESORICS 2017

Date: received 15 Jan 2018

Contact author: marc beunardeau at ingenico com

Available format(s): PDF | BibTeX Citation

Version: 20180118:124900 (All versions of this report)

Short URL: ia.cr/2018/069


[ Cryptology ePrint archive ]