# Introducing CUTS, a new few-time hash-based signature scheme

- URL: https://research.projecteleven.com/articles/cuts-a-few-time-hash-based-signature
- Published: 2026-09-28
- Authors: Conor Deegan
- Categories: Cryptography

CUTS (Chained Uniform-sum Tree Signatures) is Project Eleven's new few-time, hash-based, post-quantum signature scheme with compact signatures that stay secure even if a key signs twice.

---

The elliptic-curve signatures that protect Bitcoin and most other blockchains, such as ECDSA and Schnorr, could be broken by a large enough quantum computer. Hash-based signatures are the most conservative replacement. Their security rests only on hash functions, which blockchains already depend on. Their cost is size, and on a blockchain size is block space: larger signatures mean fewer transactions fit in each block.

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.

Today we are sharing an early look at Chained Uniform-sum Tree Signatures (CUTS), a few-time scheme by Furkan Akal, Conor Deegan, Jamie Judd and Louis Tajan of the Project Eleven research team. 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.

The full paper, with the complete specification and security proofs, will be published soon. The figures here come from our current analysis, and the parameter sets and numbers in the paper may differ.

## One-time signatures and signer state

The standardised hash-based schemes, the eXtended Merkle Signature Scheme (XMSS), Leighton-Micali Signatures (LMS) and SLH-DSA, are all built on the Winternitz one-time signature (WOTS). A WOTS key is a row of hash chains, and a signature reveals one position on each chain, picked by the message hash. Anyone can hash a revealed value forward, so WOTS+C, a Winternitz variant with a counter, requires the positions to add up to a fixed total. Moving one chain forward then forces another back, which a forger cannot do.

A second signature on a different message gives the forger two positions per chain, and they can use the lower of each pair. By our estimate, a WOTS+C key that signs twice keeps about 34 bits of security, which is under a second of work on one high-end GPU ([hashcat benchmark, RTX 5090](https://gist.github.com/Chick3nman/09bac0775e6393468c2925c1e1363d5c)).

Stateful schemes such as XMSS and LMS therefore keep a counter of which keys are used. NIST's guidance, [Special Publication 800-208](https://csrc.nist.gov/pubs/sp/800/208/final), requires key generation and signing to happen in hardware modules that do not export private keys, in part to prevent a key's state from being copied. A counter can still go wrong in ordinary operation:

- A wallet restored from a backup taken before its last signature.
- A phone or laptop restored from a cloud backup, which rolls the counter back.
- A virtual machine or hardware security module restored from a snapshot.
- The same seed loaded on two devices, each with its own counter.
- Threshold signing, where two groups of signers each sign a different message under one key.

In each case, the system can produce a second signature without realizing that the underlying one-time key has already been used. On a blockchain, both signatures are then public.

SLH-DSA ([FIPS 205](https://csrc.nist.gov/pubs/fips/205/final)) avoids state by signing each message with a few-time FORS key selected at random. A FORS key is k Merkle trees, each with 2^a secret leaves. A signature reveals one leaf per tree, picked by the message hash, along with the hashes needed to check it against the tree's root. A second signature reveals more leaves, but a forger still needs every one of their k leaves to be among those already revealed, so security falls slowly with each signature. The cost is size: the smallest SLH-DSA signature is 7,856 bytes, of which 2,912 are the FORS portion.

We designed CUTS on the assumption that a key will sometimes sign twice, and chose its parameters for how much security it keeps when it does.

## How CUTS works

CUTS signs by revealing a fixed-size cut through a binary tree whose nodes each carry a short hash chain. The tree's branching means two signatures usually reveal different parts of the key, preserving much of its security after reuse. The chains let each revealed value encode more of the message, which keeps signatures small. The revealed positions must add up to a fixed total, and the message hash maps straight to a valid set of positions. Both ideas follow WOTS-cs, the constant-sum Winternitz signature of [Perin et al.](https://link.springer.com/article/10.1007/s13389-021-00264-9). [SPHINCS-α](https://eprint.iacr.org/2022/059) later used constant-sum Winternitz in a stateless scheme.

**The key.** Take a binary tree of height h. Every node except the root carries a hash chain of w positions. A leaf's chain starts from a value derived from the secret seed. An internal node's chain starts from the hash of its two children's chain ends. The root hashes its two children's chain ends, and that hash is the public key. The following graphics use a small example: a tree of height 3 with 3 positions per chain, frontiers of 4 nodes, and positions that sum to 4. That gives 95 possible encodings, a term defined below.

![CUTS: KeyGen](https://research.projecteleven.com/images/cuts-keygen.gif)

**The frontier.** A signature reveals L nodes that together cut every path from the root to a leaf exactly once. We call this set a frontier. For each frontier node the signer also picks a position on its chain, and the L positions must add up to a fixed total S.

![CUTS: Frontier](https://research.projecteleven.com/images/cuts-frontier.gif)

**Signing.** A frontier and its positions together form an encoding. For fixed parameters there are M valid encodings, and we can count them and list them in a fixed order. The signer hashes the message to a uniformly distributed value below M and selects the encoding at that index. The signature is a randomiser, derived from the secret seed and the message, followed by the L revealed chain values.

![CUTS: Signing](https://research.projecteleven.com/images/cuts-signing.gif)

**Verifying and forging.** The verifier derives the same encoding, hashes each revealed value to the end of its chain, and rebuilds the tree above the frontier up to the public key. From one signature, every route to a different encoding needs a value that was never revealed: a node below the frontier, or an earlier position on a chain. Two signatures usually cut the tree differently, so even combining both, a forger can build only a small share of the encodings.

**CUTS+C.** Like WOTS+C, CUTS+C grinds a 2-byte counter into the message hash. The grinding increases the work required for each forgery attempt by about 9 bits, and it lets the position sum rise, which shortens verification, while one-use security stays at 128 bits.

## 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.

**Table 1.** CUTS compared with WOTS+C and FORS.

| 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.

## What comes next

The parameters trade off signature size, verification cost, key generation and security after reuse, allowing for a near-continuous range of parameter sets. Several lines of work are in progress at Project Eleven:

- Parameter sets that stay within a few bytes of WOTS+C and its costs, with more security after reuse.
- Parameter sets for settings where verification is metered, which push verification further below the sets shown here.
- Variants of the tree itself, including trees with more than two children per node.
- Stateless signature schemes built on CUTS.
- Parameter sets tuned for specific applications across digital assets and blockchains.

The CUTS paper will be published soon, with the full specification, the security proofs and recommended parameter sets, alongside a reference implementation of CUTS and CUTS+C.