Paper 2015/996

Multi-user Schnorr security, revisited

Daniel J. Bernstein

Abstract

Three recent proposals for standardization of next-generation ECC signatures have included "key prefixing" modifications to Schnorr's signature system. Bernstein, Duif, Lange, Schwabe, and Yang stated in 2011 that key prefixing is "an inexpensive way to alleviate concerns that several public keys could be attacked simultaneously". However, a 2002 theorem by Galbraith, Malone-Lee, and Smart states that, for the classic Schnorr signature system, single-key security tightly implies multi-key security. Struik and then Hamburg, citing this theorem, argued that key prefixing was unnecessary for multi-user security and should not be standardized. This paper identifies an error in the 2002 proof, and an apparently insurmountable obstacle to the claimed theorem. The proof idea does, however, lead to a different theorem, stating that single-key security of the classic Schnorr signature system tightly implies multi-key security of the key-prefixed variant of the system. This produces exactly the opposite conclusion regarding standardization.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Schnorr signaturesmulti-user securityproof errors
Contact author(s)
authorcontact-multischnorr @ box cr yp to
History
2015-10-14: received
Short URL
https://ia.cr/2015/996
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/996,
      author = {Daniel J.  Bernstein},
      title = {Multi-user Schnorr security, revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2015/996},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/996}},
      url = {https://eprint.iacr.org/2015/996}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.