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

 

By: Edward Eaton, Security Researcher, ISARA Corporation
Date: originally posted to the IACR Cryptology ePrint Archive on 22 Jun 2017

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)

 

Download the whitepaper in PDF format from IACR Cryptology ePrint Archive.

Review IACR Cryptology ePrint Archive page for this report.

 

 

RELATED POSTS