Paper 2017/607

Leighton-Micali Hash-Based Signatures in the Quantum Random-Oracle Model

Edward Eaton

Abstract

Digital signatures constructed solely from hash functions offer competitive signature sizes and fast signing and verifying times. Moreover, the security of hash functions against a quantum adversary is believed to be well understood. This means that hash-based signatures are strong candidates for standard use in a post-quantum world. The Leighton-Micali signature scheme (LMS) is one such scheme being considered for standardization. However all systematic analyses of LMS have only considered a classical adversary. In this work we close this gap by showing a proof of the security of LMS in the quantum random-oracle model. Our results match the bounds imposed by Grover's search algorithm within a constant factor, and remain tight in the multi-user setting.

Note: Minor editing and exposition.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.24th Annual Conference on Selected Areas in Cryptography (SAC2017)
Keywords
Post-Quantum CryptographyDigital SignaturesHash FunctionsRandom OraclesMulti-User Setting
Contact author(s)
ted eaton @ isara com
History
2017-08-08: revised
2017-06-26: received
See all versions
Short URL
https://ia.cr/2017/607
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/607,
      author = {Edward Eaton},
      title = {Leighton-Micali Hash-Based Signatures in the Quantum Random-Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2017/607},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/607}},
      url = {https://eprint.iacr.org/2017/607}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.