Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Post-Quantum Cryptography, Digital Signatures, Hash Functions, Random Oracles, Multi-User Setting

Original Publication (with minor differences): 24th Annual Conference on Selected Areas in Cryptography (SAC2017)

Date: received 22 Jun 2017, last revised 8 Aug 2017

Contact author: ted eaton at isara com

Available format(s): PDF | BibTeX Citation

Note: Minor editing and exposition.

Version: 20170808:130408 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]