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

Protocol Design
,
21

A small modification to the original SHRINCS scheme improves the user experience of losing state and initializing new signing devices: instead of backing up a fresh secret seed for every new device, the user backs up a single static seed once, plus a public per-device identifier.

Suppose a user loses their original SHRINCS signing device. They can restore the seed on a new device, but that device can only spend through the inefficient stateless path because the signing state is missing. To get back to compact stateful signatures, the user has to migrate the coins to a fresh key pair. They run \textsf{KeyGen} on the new device, which initializes the state needed for the efficient stateful path, back up the new seed, and hand out the new public key. After this, the device holds two seeds and two key pairs: the old one with only the stateless path, and the new one with both paths. The old seed can be deleted once the user is sure the old key pair is no longer needed.

In summary, every time a device is initialized, a new secret seed has to be securely backed up to allow for compact stateful signing.

With a small change to the scheme, each device initialization instead only requires backing up a public per-device \mathit{id}, while a single static \mathit{master\_seed} is backed up once. The advantage is that \mathit{id} does not need to be secret for the security of the signature scheme. It is, however, essential for deriving the device’s key pair and producing signatures. That makes \mathit{id} behave a lot like a descriptor. It can be backed up in many more places than a seed, including, if desired, the blockchain itself (though this is arguably a misuse of blockspace).

The idea is that on initialization, the device draws \mathit{id} uniformly at random and computes the SHRINCS seed as \textsf{PRF}(\text{key} = \mathit{master\_seed}, \mathit{id}), where \textsf{PRF} is a pseudorandom function (built from a hash function, for example). The \mathit{master\_seed} is secret, but on its own it is not enough to derive the SHRINCS seed. Deriving it also requires \mathit{id}. So \mathit{id} can be public, yet it still has to be backed up.

In more detail, the modified scheme has these algorithms (ignoring hardened derivation and the hybrid signature):

  • \textsf{MasterSeedGen}() \rightarrow \mathit{master\_seed}: generates a fresh, uniformly random byte string \mathit{master\_seed}.
  • \textsf{KeyGen}(\mathit{master\_seed}) \rightarrow (\mathit{id}, \mathit{pk}, \mathit{state}): draws a ~20-byte uniformly random \mathit{id}, computes the SHRINCS seed \mathit{seed} = \textsf{PRF}(\text{key} = \mathit{master\_seed}, \mathit{id}), derives the SHRINCS public key \mathit{pk} from \mathit{seed}, and sets \mathit{state}.\mathit{id} := \mathit{id} and \mathit{state}.\textsf{SHRINCS} to the initial SHRINCS state.
  • \textsf{Sign}(\mathit{master\_seed}, \mathit{id}, \mathit{state}, m) \rightarrow (\mathit{state}', \mathit{sig}): computes the SHRINCS seed \mathit{seed} = \textsf{PRF}(\text{key} = \mathit{master\_seed}, \mathit{id}). If \mathit{id} = \mathit{state}.\mathit{id}, it returns \textsf{SHRINCS.Sign}(\mathit{seed}, \mathit{state}, m). Otherwise, it returns \textsf{SHRINCS.Sign}(\mathit{seed}, \textsf{LOST}, m).

Unlike the original SHRINCS, \textsf{MasterSeedGen}() does not have to run on any particular device and can be the result of, say, dice rolls.

Thanks to @conduition, @EthanHeilman, @MikKud, and @theblackmarble for the discussions that led to this idea.

3 Likes
22

Very neat idea @jonasnick! The key observation that enables this is that, in order to safely use the stateful signing path of SHRINCS, the signer needs to be absolutely sure that nothing and nobody else has ever used the same stateful keys before. The only way to do that is to generate the keys yourself. Your idea here is that, instead of generating the master seed, the stateful signer software can content itself by deriving a pseudorandom child key, based on a salt (the “ID”) that the signer software generates itself. For the purposes of ensuring “virgin state”, this is just as good as generating a fresh master seed, provided the salt has enough entropy to ensure collisions are overwhelmingly improbable.

The keys derived from the master seed are unlinkable without the master seed itself, so there is no privacy tradeoff here. Sounds like a strict improvement over the original scheme where to use the stateful path again, you’d need to rotate seed phrases anytime you recover from seed. With this change, you just need to back up the IDs.

Since IDs are safe to share publicly, you could back them up pretty much anywhere: on-chain, Nostr, IPFS, dropbox, a git repo, whatever. As long as they exist somewhere that you or your wallet software can find them later upon restore.

Also worth noting that if we deploy SHRINCS in the real-world, each ID will represent an individual HD wallet, and so instead of just one keypair, a single ID can derive effectively unlimited SHRINCS keypairs, to use for different wallet addresses.

1 Like