International Association
for Cryptologic Research

The unavoidable transition to post-quantum cryptography requires mature quantum-safe digital signature schemes. Hash-based signatures are well-understood and promising candidates. A common concern regarding their deployment is their statefulness, due to their use of one-time signature schemes. While the theory of hash-based signatures is mature, a complete understanding 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 be- tween volatile and nonvolatile storage, and show that it can be naturally realized in a hierarchical signature scheme. To protect against unintentional copying of 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.