Paper 2016/357

State Management for Hash-Based Signatures

David McGrew, Panos Kampanakis, Scott Fluhrer, Stefan-Lukas Gazdag, Denis Butin, and Johannes Buchmann


The unavoidable transition to post-quantum cryptography requires dependable quantum-safe digital signature schemes. Hash-based signatures are well-understood and promising candidates, and the object of current standardization efforts. In the scope of this standardization process, the most commonly raised concern is statefulness, due to the use of one-time signature schemes. While the theory of hash-based signatures is mature, a discussion of the system security issues arising from the concrete management of their state has been lacking. In this paper, we analyze state management in N -time hash-based signature schemes, considering both security and performance, and categorize the security issues that can occur due to state synchronization failures. We describe a state reservation approach that loosens the coupling between volatile and nonvolatile storage, and show that it can be naturally realized in a hierarchical signature scheme. To protect against unintentional copying of the private key state, we consider a hybrid stateless/stateful scheme, which provides a graceful security degradation in the face of unintentional copying, at the cost of increased signature size. Compared to a completely stateless scheme, the hybrid approach realizes the essential benefits, with smaller signatures and faster signing.

Note: This is a revised and expanded version, as published in the proceedings of SSR2016.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. SSR 2016
digital signatures
Contact author(s)
mcgrew @ cisco com
2016-09-02: revised
2016-04-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {David McGrew and Panos Kampanakis and Scott Fluhrer and Stefan-Lukas Gazdag and Denis Butin and Johannes Buchmann},
      title = {State Management for Hash-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2016/357},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.