Hash-based signatures, one type of quantum resistant signature proposal, are large but also tend to have this property where they very quickly lose their security properties if keys are used more than once.
Hash-based schemes are built from small signing keys of two kinds. A one-time key, such as a Winternitz key, gives signatures of about 500 bytes but must never sign twice, and keeping track of which keys have been used is where real systems can go wrong. A few-time key, such as the FORS (Forest of Random Subsets) keys inside SLH-DSA, keeps its security after a second signature, and its signatures are more than 2 KB at 128-bit security.
Project Eleven released CUTS which claims to reduce the security hit that comes from reusing a key, while preserving some of the efficiency gains of stateful signature schemes (even though I believe CUTS is not stateful).
CUTS targets the middle ground between these two approaches. Every parameter set in this post gives 128-bit security for a key's first signature. At 546 bytes, close to one-time size, a CUTS key keeps 53 bits after two signatures. From 1,360 bytes it keeps the full 128 bits, with signatures 41% smaller than any FORS signature with practical key generation at that security. At 2,128 bytes it is also faster to verify and cheaper to generate than the FORS sets we compare it with.
I found their numbers a little confusing to interpret, but they promise a paper soon:
Results
The table compares CUTS with WOTS+C and FORS. Every key gives 128-bit security for its first signature. Signatures include a 16-byte randomiser, plus a 2-byte counter for WOTS+C and CUTS+C. Hash counts are for 16-byte hash values and leave out hashing the message.
| Key | Signature | Verification (hashes) | Key generation (hashes) | Security after two signatures |
| WOTS+C | 530 B | 241 | 513 | about 34 bits |
| CUTS+C (9, 5, 33, 82) | 546 B | 206 | 5,111 | 53 bits |
| CUTS+C (11, 2, 61, 31) | 994 B | 149 | 8,189 | 80 bits |
| CUTS (15, 5, 84, 201) | 1,360 B | 546 | 327,671 | 128 bits |
| CUTS (15, 1, 132, 0) | 2,128 B | 131 | 65,535 | 128 bits |
| FORS (8, 17) | 2,320 B | 145 | 3,145,721 | 128 bits |
| FORS (14, 12), as in SLH-DSA-128s | 2,928 B | 183 | 172,019 | 154 bits |
CUTS rows give (h, w, L, S) and FORS rows give (k, a). Two-signature figures report the forger's average success over random pairs of signatures as log2, and 128 bits is the most that 16-byte hashes allow. The CUTS figures are Monte Carlo estimates from our analysis tools, and the paper replaces them with proven bounds. The FORS figures are exact.
Near one-time size, the gain is in what a reused key keeps. The 546-byte set is 16 bytes larger than WOTS+C and verifies with 35 fewer hashes. After an accidental second signature, forging against the 546-byte set takes about four days on one high-end GPU, while the 994-byte set would take about 1.4 million years. A key that has signed twice should still be retired, and the extra time is what lets its owner move the funds.
At full security after two signatures, CUTS is smaller than FORS. No FORS set with key generation under a billion hashes goes below 2,320 bytes at this security. CUTS reaches it at 1,360 bytes, 41% smaller. At 2,128 bytes it is smaller, faster to verify and cheaper to generate than both FORS sets in the table.
CUTS pays for this in key generation: 10 to 16 times the hashing of WOTS+C for the sets near one-time size, and more for the larger sets. Key generation runs once, and signing in our reference implementation costs about the same unless the signer caches the tree. Beyond two signatures, our analysis suggests CUTS keeps its security but currently loses it faster than FORS with each further use. The paper will compare the two at higher signature counts.