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

The discussion initiates with an exploration into the distinguishability of unbalanced and balanced XMSS (eXtended Merkle Signature Scheme) through the observation of the authentication path length. In a directionless XMSS configuration, what a verifier observes—comprising a WOTS (Winternitz One-Time Signature) alongside an array of hash values forming the Merkle authentication path—does not disclose the structure of the Merkle tree but merely sets a lower bound on its maximum height. This scenario is likened to Taproot in Bitcoin, where observing a Taproot script spend with two hashes does not reveal the internal makeup of the script tree, only that there exists at least one leaf node at a specified height. It's delineated that sequential signatures from an unbalanced XMSS tree, such as those used in SHRINCS (SHashed Reducible Indexed Certificate Store), present indistinguishably from signatures derived from a balanced XMSS tree of corresponding height. This obfuscation assumes no additional information about the tree structure is made available to the verifier.

The dialogue then shifts to question the necessity of concealing the iteration count of a signature, especially given its potential visibility on the blockchain. The counterpoint offered suggests that in employing directionless XMSS, definitive on-chain visibility is compromised. For example, an observer identifying a Merkle authentication path comprising three hashes might speculate on the key being an unbalanced XMSS variant with three prior signatures, or alternatively, a balanced XMSS key with up to seven previous signatures, among other possibilities. This inherent ambiguity serves to complicate on-chain analysis and by extension, complicates efforts by attackers to leverage strategies like replacement cycling attacks aimed at depleting a victim's signature reserves.

The final portion of the discourse addresses emerging concerns regarding the limitations inherent to directionless XMSS in creating uniquely tweaked hash functions for each node within the Merkle tree—a feature characteristic of SPHINCS. The best achievable under directionless XMSS is the implementation of a singular tweaked hash function per layer within the tree, which raises apprehensions regarding the potential dilution of the security proof's robustness. This concern underscores a fundamental challenge in balancing the need for cryptographic agility and maintaining stringent security assurances within the framework of XMSS implementations.