Cryptology ePrint Archive: Report 2016/357

State Management for Hash-Based Signatures

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

Abstract: 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.

Category / Keywords: public-key cryptography / digital signatures

Original Publication (with major differences): SSR 2016

Date: received 6 Apr 2016, last revised 2 Sep 2016

Contact author: mcgrew at cisco com

Available format(s): PDF | BibTeX Citation

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

Version: 20160902:075951 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]