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

Abstract: Stateful hash-based signature schemes can be very efficient when the number of signatures generated by a public key is small. One major problem with stateful schemes is that the state needs to be backed up and updated correctly after every signing operation. By using a straightforward combination of a stateless hash-based scheme (such as a variant of SPHINCS+) and an unbalanced XMSS tree of one-time signatures (stateful), we obtain a scheme that we call SHRINCS. It is extremely efficient when only a few signatures are required and can be backed up with a static seed. More precisely, the SHRINCS public key is a hash of the stateful and stateless public keys. We assume key generation happens on a signing device that is able to keep state securely. Therefore, the signing device can use efficient stateful signatures to sign for the public key. When the state is known to be corrupted or lost, for example when a static seed backup has been restored, the signing device only uses stateless signatures. As a result, SHRINCS provides the efficiency of stateful signatures during normal operation while maintaining the robustness of stateless signatures as a fallback.

SHRINCS

SHRINCS is briefly covered deep in the appendix of our report “Hash-based Signatures for Bitcoin” (Hash-based Signature Schemes for Bitcoin) by Mikhail Kudinov and myself. This post gives a fuller explanation and invites feedback.

The construction of SHRINCS requires a stateless signature scheme and a stateful signature scheme that generates small signatures. SHRINCS consists of the following algorithms:

• 𝖪𝖾𝗒𝖦𝖾𝗇() →(seed,pk,state): The keygen algorithm draws a master seed, derives secret keys sk1 and sk2 for the stateful and stateless signature schemes, respectively. Using these, it generates public keys pk1 and pk2 for the stateful and stateless schemes. Finally, 𝖪𝖾𝗒𝖦𝖾𝗇 returns the tuple (seed,pk,state) where pk =𝐻(pk1,pk2) and state is the initial state of the stateful scheme.
• 𝖱𝖾𝗌𝗍𝗈𝗋𝖾(seed) →(seed,pk,state): The restore algorithm rederives the SHRINCS public key pk, sets state to 𝖫𝖮𝖲𝖳 and returns the tuple (seed,pk,state).
• 𝖲𝗂𝗀𝗇(seed,state,𝑚) →(state′,sig): If state ≠𝖫𝖮𝖲𝖳, the signing algorithm rederives sk1 and pk2 and runs the 𝖲𝗂𝗀𝗇 algorithm of the stateful scheme with sk1, state and message 𝑚. Then, it returns the updated state state′ along with the signature concatenated with pk2. Otherwise, the signing algorithm rederives sk2 and pk1, runs the 𝖲𝗂𝗀𝗇 algorithm of the stateless scheme with sk2 and 𝑚, and returns state′ =state and the signature concatenated with pk1.
• 𝖵𝖾𝗋𝗂𝖿𝗒(pk,𝑚,sig) →{𝗍𝗋𝗎𝖾,𝖿𝖺𝗅𝗌𝖾}: The verification algorithm parses sig as sig′‖pk′, verifies sig′ according to the stateless or stateful scheme (which recovers the signing public key in hash-based schemes), and checks that the two public keys hash to pk.

So, when a signing device capable of maintaining state securely is initialized, it signs with the stateful scheme, but whenever a device is restored with the seed, it only signs with the stateless scheme. Because the stateful path is much more efficient in SHRINCS, signing from a restored device is much more expensive than from the device that originally ran 𝖪𝖾𝗒𝖦𝖾𝗇.

For the stateless signature scheme in SHRINCS, candidates include SLH-DSA or one of the variants of SPHINCS+ that we cover in detail in the report. Depending on the parameters, signature size is between 3KB and 8KB and the public key is 16 bytes (at NIST security level 1). For the stateful scheme SHRINCS uses what we call “unbalanced XMSS”. A regular XMSS public key is essentially a Merkle tree of one-time signature (OTS) public keys. A one-time signature scheme can generate no more than a single signature for a public key, otherwise it becomes insecure. So, the signing state is just the number of signatures that have already been produced, initialized at 𝑞 =0. To sign a message in XMSS, the signer increments 𝑞, produces a signature with the 𝑞-th one-time public key in the Merkle tree, and computes the authentication path (aka “Merkle proof”) to the root. The final signature is essentially the one-time signature concatenated with the authentication path.

Instead of using a balanced Merkle tree of OTSs, we use an unbalanced tree for the stateful part of SHRINCS. Thus, the first OTS is at depth 1, the second OTS at depth 2 and so on. This minimizes authentication path length for early signatures, which is optimal when few signatures are expected. The 𝑞-th signature for this “unbalanced XMSS” scheme is the 𝑞-th OTS signature and its authentication path. At NIST security level 1, the size of the authentication path is 𝑞 ⋅16 bytes and the size of the OTS signature is 292 bytes. More precisely, for the OTS we use WOTS+C (for details, check the paper).

Putting it all together, when signing with intact state, the signature size of SHRINCS is min(292 +𝑞 ⋅16,𝑠𝑙) +16 where 𝑞 is the number of signatures that have been generated for the public key through the stateful path and 𝑠𝑙 is the size of signatures generated with the stateless scheme. For 𝑞 =1 this signature is more than 11x smaller than the smallest NIST-standardized scheme (ML-DSA). I’d expect that average 𝑞 for regular Bitcoin wallets is between 1 and 2. The main downside of SHRINCS remains that security requires secure state management. However, unlike pure stateful schemes where state mismanagement can be catastrophic, if in doubt, SHRINCS signers can always fall back to the stateless path.

Originally posted: https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158