A stateless signature scheme avoids a persistent signing counter. That matters because lost or duplicated state—such as a filesystem rollback or one key used on multiple servers—can reuse one-time signing material and enable forgery. section 14.2.3
SPHINCS+ adapts XMSSMT with three safeguards: it derives the hypertree path from the private key and message, uses many more one-time signatures to reduce collisions, and replaces the final one-time signature with a few-time signature. section 14.2.3
The central tradeoff is simple:
- XMSS tracks which one-time signature was used; SPHINCS+ avoids that bookkeeping by making path reuse unlikely and less immediately damaging. section 14.2.3
- Signing the same message twice produces the same signature, while the private key prevents attackers from predicting paths for messages they submit. section 14.2.3
- Stateless hash-based signatures belong to post-quantum cryptography; SPHINCS+ is paired with XMSS as its stateless counterpart. section 14.5
Why state becomes dangerous
Imagine signing after restoring an old filesystem snapshot, or signing from two servers that share a key. Both situations can repeat a hypertree path. A stateless design removes the counter users might forget to preserve and compensates with more one-time signatures and few-time signatures. section 14.2.3
Figure 14.6 The XMSSMT stateful hash-based signature scheme uses multiple trees to increase the amount of signatures supported by the scheme while reducing the work at key generation and signing time. Each tree is deterministically generated only when they are used in the path to the final leaf that contains the OTS used to sign a message.
Use the XMSSMT tree diagram to contrast a stateful design, which generates trees along the signing path and tracks usage, with the stateless alternative. section 14.2.3
