SHRINCS: 324-byte stateful post-quantum signatures with static backups

SHRINCS is a novel hybrid signature scheme that combines the efficiency of stateful hash-based signatures with the robustness of stateless ones, making it particularly suitable for scenarios where only a limited number of signatures is needed from a given key. The core idea behind SHRINCS is to use an unbalanced XMSS tree for stateful operations and a variant of SPHINCS+ for stateless operations. This approach allows SHRINCS to offer extremely efficient operations under normal circumstances while providing a reliable fallback in case the state is lost or corrupted.

The public key in SHRINCS is derived from hashing both the stateful and stateless public keys, ensuring that the system can operate seamlessly between the two modes depending on the state's integrity. Key generation, restoration, signing, and verification are all designed to support this dual-mode functionality. During the initial setup, a master seed is used to generate secret keys for both the stateful and stateless schemes, from which the public keys are derived. If the state is intact, SHRINCS utilizes the stateful signing mechanism, which is more efficient. However, if the state is considered lost (for example, after restoring from a static seed), SHRINCS defaults to the stateless signing method.

The stateful component of SHRINCS employs an innovative "unbalanced" version of the XMSS tree, optimizing the authentication path length for early signatures and thus reducing the signature size significantly when few signatures are expected. This optimization is critical for applications like Bitcoin wallets, where the average number of signatures per public key is relatively low. The use of WOTS+C (Winternitz One-Time Signature Scheme plus Checksum) for the one-time signatures (OTS) further enhances the efficiency and security of the stateful path.

Despite its efficiencies, the primary challenge with SHRINCS—and indeed, any stateful signature scheme—is managing the state securely. Mismanagement can lead to security vulnerabilities. However, SHRINCS mitigates this risk by allowing a seamless transition to stateless signatures whenever there's uncertainty about the state's integrity. This fail-safe mechanism ensures that SHRINCS remains secure even in scenarios where state management might be compromised.

For a detailed exploration of the SHRINCS architecture, including the mathematical formulations and algorithmic details, readers are directed to the paper "Hash-based Signatures for Bitcoin," co-authored by Mikhail Kudinov, available at https://eprint.iacr.org/2025/2203. This paper provides comprehensive insights into the technical underpinnings of SHRINCS and its potential applications.