A proposal for leanSphincs

  • 25% smaller signatures
  • 18% faster verificationi
  • more complex
  • 2× worse threshold

by Tom Wambsgans

SLH-DSA-128-24leanSphincs
h2226
k6248
a24104 + 3
OTSWOTS+WOTS+C
FTSFORSFORSWOTS foresti
HashSHA-2 or SHAKEBLAKE2si
Lifetime224230i
Size3,856 bytes5,6844,276 bytes
Verification
(compressions)		296373307
A leanSphincs signature: a path in a tree of height 26 to a leaf, the hash of a WOTS+C key of 64 chains of length 4, which signs the root of a FORS key of 24 trees of height 10 h = 26 WOTS+C w = 4 ℓ = 64 FORS a = 10 k = 24 WOTS forest 8 trees 4 3 WOTS w = 5 ℓ = 6

Key idea: the signer builds only part of the XMSS tree (pruning), so lifetime scales with keygen time.

One signer

LightLedger Nano S+i
Standardweak CPUi
Fullpowerful CPUi
Lifetimei
210K249K signatures (subtree of 213)
22M26M signatures (subtree of 220)
1.15B1.4B signatures (full tree of 226)
Key generation
1.98M compressions60 s
254M compressions2.0 s
16.2B compressions16 s
Signing
74K compressions, 16 KiB cache2.2 s
70K compressions, 1 MiB cache0.5 ms
93K compressions, 16 MiB cache0.1 ms

Threshold, t-of-n

Adapted from PRAWNS: a one-time ceremony at keygen precomputes every hash of a secret, run either as an honest-majority MPC among the operators (DKG) or by a trusted dealer; signing then needs no MPC (432≈ 820 bytes per signer, 3 rounds), and is secure against t − 1 malicious signers (with abort).

With DKG

Bottleneck: keygen traffic per operator

Lifetimei
(signatures)		7.5K8.9K signatures
(subtree of 28)		28.5K33.5K signatures
(subtree of 210)		108K128K signatures
(subtree of 212)
2-of-31121 GB4385 GB172342 GB
3-of-51326 GB52103 GB207410 GB
4-of-71428 GB55110 GB222440 GB

With a trusted dealer

Bottleneck: public data to store (also applies to the DKG version)

Lifetimei
(signatures)		28.5K33.5K
(subtree of 210)		108K128K
(subtree of 212)		410K485K
(subtree of 214)
Public data404 MB806 MB1.6 GB3.2 GB6.5 GB12.9 GB