SHRIMPS: 2.5 KB post-quantum signatures across multiple stateful devices
Abstract: SHRINCS achieves very small hash-based signatures utilizing a stateful signer whereas nonetheless permitting for static backups. However, its environment friendly stateful path requires transferring state to any new system, which is error-prone, so in apply any restored or secondary system will usually fall again to massive stateless signatures. SHRIMPS removes this single-device constraint. In settings the place every secret’s used for less than a small variety of signatures (as is typical in Bitcoin), a static seed backup could be loaded into many unbiased stateful signing devices, every producing a ~2564-byte signature at 128-bit safety. The development requires an higher certain on the variety of system initializations; with a conservative certain of 𝑛dev =210, SHRIMPS signatures are as much as 3 times smaller than SLH-DSA (7856 bytes). SHRIMPS could be mixed with SHRINCS: the first system produces ~324-byte signatures, whereas any backup system produces signatures beneath 3 KB.
Basic SHRIMPS
In SPHINCS+, the parameter 𝑞𝑠 bounds the variety of signatures that may be securely produced beneath a single key. Smaller 𝑞𝑠 permits smaller signature sizes. The development of SHRIMPS combines two SPHINCS+ situations beneath a single public key: a compact occasion with 𝑞𝑠 =𝑛dev the place 𝑛dev is an higher certain on the variety of system initializations, and a fallback occasion with sufficiently massive 𝑞𝑠 (e.g., 240 or 264). The SHRIMPS public secret’s a hash of the general public keys of each situations.
A signing system is initialized by loading the seed, which deterministically derives each SPHINCS+ key pairs. To signal, the system seems up its persistent state for this key to find out whether or not it has signed earlier than: if not, it indicators by way of the compact occasion and updates its state; in any other case, it indicators by way of the fallback occasion.
A SHRIMPS signature consists of a SPHINCS+ signature beneath the chosen occasion and the general public key of the opposite occasion (16 bytes[1]). The verifier reconstructs the signing occasion’s public key from the SPHINCS+ signature, hashes each public keys to reconstruct pk, and compares it to the identified public key. The 16-byte sibling public secret’s the one overhead past an ordinary SPHINCS+ signature.
Since every system indicators at most as soon as by way of the compact occasion, the entire variety of compact-path signatures across all devices is at most 𝑛dev, which is precisely the variety of signatures the compact occasion is parameterized to assist.
More typically, the compact occasion can enable every system 𝑛dsig signatures earlier than switching to the fallback, at the price of growing 𝑞𝑠 to 𝑛dev ⋅𝑛dsig. In Bitcoin, keys are generally used for only some signatures, so a small 𝑛dsig retains most signatures on the compact path.
In Bitcoin pockets setups, initializing a tool with a seed is usually a handbook course of that occurs hardly ever. 𝑛dev =210 =1024 is conservative; it’s onerous to think about importing a single seed into greater than a thousand devices. A tool that loses its state and re-initializes from the seed will use the compact path once more, consuming an extra signature from the compact occasion’s 𝑞𝑠 price range.
The fallback occasion could be any SPHINCS+ parameterization with sufficiently massive 𝑞𝑠. Using SLH-DSA (SPHINCS+ with 𝑞𝑠 =264), the fallback signature is 7856 bytes; utilizing a SPHINCS+ variant with 𝑞𝑠 =240 from Hash-based Signature Schemes for Bitcoin, it’s lower than 4.5 KB.
The following desk exhibits chosen compact-path parameter units, the place sizes are proven because the SPHINCS+ signature dimension plus the 16-byte sibling public key.
| Parameters | Size + 16 | Sign value | |
|---|---|---|---|
| W+C P+FP |
2324 B | 2.5M | |
| W+C P+FP |
2564 B | 6.8M | |
| W+C P+FP |
2708 B | 2.4M | |
| W+C P+FP |
2628 B | 9.9M | |
| W+C P+FP |
2884 B | 2.7M | |
| W+C P+FP |
2580 B | 41.0M | |
| W+C P+FP |
2772 B | 10.9M | |
| W+C P+FP |
3000 B | 2.5M |
Sign value is in SHA-256 compression calls. For comparability, SLH-DSA (𝑞𝑠 =264) produces 7856-byte signatures at 2.3M compression calls. Verification prices 0.30 compressions per signature byte; the 𝑑 =1 parameter units above obtain ~0.19 (about 35% decrease), whereas the 𝑑 =2 units obtain ~0.25. Each row could be reproduced utilizing the --params possibility of prices.sage in SPHINCS-Parameters (commit f2ea2a2):
sage prices.sage –params <scheme> <q_s> <ok> <a> <h> <d> <w> <S_wn>
For instance, the second row: sage prices.sage --params W+C_P+FP 10 8 17 12 1 16 240
State administration
The compact path requires per-key state: the system shops a counter of compact-path signatures made (⌈log2(𝑛dsig +1)⌉ bits).
With key derivation (much like BIP-32) from a single seed, every derived secret’s a separate SHRIMPS occasion. The system should keep this state for each derived key, or retailer a single bit per key indicating that the fallback path ought to be used.
If the variety of compact-path signatures exceeds the 𝑞𝑠 price range (for instance, as a result of extra devices had been initialized than anticipated, or as a result of a tool did not replace its state), safety doesn’t break down instantly. Instead, it degrades regularly. The following desk exhibits how safety decreases for the (𝑘,𝑎,ℎ,𝑑) =(8,17,12,1) parameter set as the entire variety of compact-path signatures grows past the 𝑞𝑠 =210 price range:
| Total compact-path signatures | Security |
|---|---|
| 128.0 bits | |
| 128.0 bits | |
| 125.1 bits | |
| 120.4 bits | |
| 115.0 bits | |
| 108.9 bits |
As an apart, statefulness is a powerful assumption, however the related threat is localized to particular person wallets that mismanage their state. By distinction, different post-quantum schemes carry systemic dangers: new cryptographic assumptions (lattices, isogenies) or bigger signatures.
Discussion
If we assume stateful wallets and may certain the variety of system initializations, SHRIMPS compact-path signatures are smaller than SLH-DSA at decrease verification value and comparable signing value. With 𝑛dev =210 and 𝑛dsig =1, signatures are 2564 bytes, about 3 times smaller than SLH-DSA’s 7856 bytes. Increasing 𝑛dsig to permit extra signatures per system prices extra bytes and signing time, however even at 𝑛dsig =24 the signature dimension stays beneath 3000 bytes.
SHRINCS already assumes stateful wallets, so SHRIMPS could be mixed with SHRINCS: the first system makes use of SHRINCS’s environment friendly stateful path (~324-byte signatures), whereas any backup system makes use of the SHRIMPS compact path as an alternative of falling again to full stateless signatures.
A comparability of key technology prices is left to future work. The parameter units on this submit all constrain verification value per byte to be at most that of SLH-DSA (~0.30 compressions per byte). Relaxing this constraint (for instance, permitting verification value similar to Schnorr signature verification per byte) would allow 𝑤 =256, probably yielding even smaller signatures. We go away this exploration to future work as effectively.
Thanks to Mikhail Kudinov and Oleksandr Kurbatov for the discussions that led to SHRIMPS and their suggestions on earlier variations of this submit.
- A SPHINCS+ public key consists of a public seed (PK.seed, 16 bytes) and a hypertree root (PK.root, 16 bytes). Both SHRIMPS situations share the identical PK.seed, so the sibling solely wants to incorporate PK.root. ↩︎
Originally posted: https://delvingbitcoin.org/t/shrimps-2-5-kb-post-quantum-signatures-across-multiple-stateful-devices/2355
