1/ Our
@projecteleven research team (
@conordeegan,
@furkanakal, Louis Tajan, and Jamie Judd) just published an early look at CUTS, a new few-time hash-based signature scheme. At 546 bytes, close to WOTS size, & a key that signs twice in error keeps 53 bits of security instead of collapsing. 🧵
Introducing CUTS (Chained Uniform-sum Tree Signatures), a new few-time hash-based signature scheme from our research team at Project Eleven.
Hash-based signatures are one of the most conservative paths to post-quantum security. Their security rests only on hash functions, but that simplicity comes at the cost of larger signatures.
The most compact schemes reduce that cost by using one-time keys, which become vulnerable if they are ever reused. Restore an old backup or load the same seed onto two devices, and a one-time key can end up signing twice. A WOTS+C key that has signed twice keeps only about 34 bits of security. One GPU can then forge a new signature in under a second.
By contrast, few-time signatures are built to handle reuse, but they are larger. FORS, the few-time construction inside SLH-DSA, needs more than 2 KB per signature at 128-bit security.
CUTS targets the middle ground: more security after reuse, at sizes close to one-time signatures. It arranges hash chains in a tree, and the message hash picks which chains each signature reveals. When a key signs twice, the two signatures usually expose different parts of the key.
At 546 bytes, close to one-time size, a CUTS key keeps 53 bits of security after two signatures.
At 1,360 bytes it keeps the full 128 bits. That is 41% smaller than any FORS parameter set at that security with practical key generation.
At 2,128 bytes, CUTS is smaller, faster to verify and cheaper to generate than every FORS parameter set we compared, including the one in SLH-DSA-128s.
The aim is hash-based signatures that hold up in systems where accidental key reuse can happen. The parameters let each application trade signature size, verification cost, key generation and security after reuse against each other.
The paper, with the full specification and security proofs, is coming soon. These figures come from our current analysis, and the parameter sets and numbers in the paper may differ. We'd love feedback, from improvements to attacks. Reply or get in touch.