Stateful Hash-Based Signatures HBS

Project Overview

In Special Publication 800-208, Recommendation for Stateful Hash-Based Signature Schemes NIST approves two schemes for stateful hash-based signatures (HBS) as part of the post-quantum cryptography development effort.  The two schemes were developed through the Internet Engineering Task Force: 1) XMSS, specified in Request for Comments (RFC) 8391 in May 2018, and 2) LMS, in RFC 8554 in April 2019.

Background

HBS schemes were the topic for a session of talks during the first public workshop on post-quantum security, as well as the panel discussion that followed it. Participants expressed significant interest in the standardization of such schemes at that time, because the underlying technology was well understood. In particular, the security of an HBS scheme, when implemented properly, relies only on the preimage resistance of its component cryptographic hash function. This property is already the basis for the security of many NIST-approved cryptographic algorithms and protocols, and no quantum computing algorithms are known that would pose a practical threat in the foreseeable future.

Therefore, HBS schemes are good candidates for early standardization. The stateful versions of HBS schemes offer better performance than the stateless versions but are vulnerable to misuse if they are not implemented properly. NIST established a sub-project for approving stateful HBS schemes because they don’t meet the API requested for signatures and require state management.

NIST SP 800-208Recommendation for Stateful Hash-Based Signature Schemes

October 30, 2020: This publication supplements FIPS 186 by approving the use of two stateful hash-based signature schemes: the eXtended Merkle Signature Scheme (XMSS) and the Leighton-Micali Signature system (LMS) as specified in Requests for Comments (RFC) 8391 and 8554, respectively.

Stateful hash-based signature schemes are secure against the development of quantum computers, but they are not suitable for general use because their security depends on careful state management. They are most appropriate for applications in which the use of the private key may be carefully controlled and where there is a need to transition to a post-quantum secure digital signature scheme before the post-quantum cryptography standardization process has completed.

NIST SP 800-208 profiles LMS, XMSS, and their multi-tree variants. This profile approves the use of some but not all of the parameter sets defined in RFCs 8391 and 8554. The approved parameter sets use either SHA-256 or SHAKE256 with 192- or 256-bit outputs. This profile also requires that key and signature generation be performed in hardware cryptographic modules that do not allow secret keying material to be exported.

On February 4, 2019, NIST issued a request for public input on how to mitigate the potential misuse of stateful HBS schemes. 

On June 21, 2018, NIST issued a request for public input on XMSS and LMS.

 

Contacts

Morris Dworkin
morris.dworkin@nist.gov

Dustin Moody

Related Projects

Post-Quantum Cryptography

Created December 20, 2018, Updated October 30, 2020