LMS: Lighter, faster key generation

The Leighton-Micali Signature (LMS) system is a stateful hash-based signature scheme whose security relies on properties of hash functions, standing at a comfortable security level against attackers in possession of quantum computers. As such, LMS has been standardized by NIST in SP-800-208 and is regarded as a suitable post-quantum signature algorithm in industry.

At its core, generating an LMS private key and obtaining its corresponding public key involves computing an exponential number of hashes and eventually representing large Merkle trees in memory. Moreover, signing with this key later requires recovering subsets of the hashes computed at key generation time. Sequential, high memory approaches to these operations achieve best signature speed, but make LMS key generation prohibitively slow and resource-intensive. While there are a number of hardware-oriented efforts to optimize LMS, some open-source software implementations do not take advantage of known memory trade-offs and opt for small parameter sets.

In this talk, we describe how to make LMS key generation procedure faster with SIMD hashing (by adapting the low-memory iterative algorithm of RFC8554) and recall algorithms that trade off signature speed against succinct representations of private keys in memory.

Francisco José Vial-Prado - Senior Cryptography Engineer at Fortanix