Three hardness assumptions for the price of one signature

When the NIST post-quantum standardization program reached its final decisions in 2022 and published the first FIPS 203 through 205 drafts shortly after, the field of post-quantum cryptography was given a menu. ML-KEM (formerly Kyber) for key encapsulation. ML-DSA (formerly Dilithium) for lattice-based signatures. FALCON as an alternate lattice-based signature. SLH-DSA (formerly SPHINCS+) for hash-based signatures. You were supposed to pick one, maybe two, and ship.

Almost every deployed post-quantum system we've looked at has followed that guidance. Pick a scheme. Justify the choice. Ship it. Cross your fingers that the scheme you picked doesn't turn out to be the one with the unexpected cryptanalytic breakthrough lurking in it three years from now.

We went a different way. The substrate uses all three of ML-DSA-65, FALCON-512, and SLH-DSA-SHA2-128f together, in every single signing event, for every substrate ever minted, forever. Every substrate carries all three signatures. Verification checks all three. A forgery requires breaking all three. The three-family structure is not an optional feature or a future upgrade path. It's the base case.

This post explains why, and what we give up in exchange. The short version is: we gave up some per-operation signing speed, some persistent storage footprint (but less than you'd think), and some implementation simplicity, in exchange for a security property that is, to our knowledge, not available anywhere else in the post-quantum signing landscape: substrate forgery requires simultaneously breaking three independent mathematical hardness assumptions, from three disjoint areas of cryptographic research, with three different histories of cryptanalysis, three different sets of past breakthroughs, and three different sets of plausible future breakthroughs. The long version takes the rest of this post.

The three assumptions

Here is what's actually at stake when someone tries to forge a substrate.

ML-DSA-65 security rests on the Module Learning With Errors assumption and the Module Short Integer Solution assumption over module lattices. The underlying hard problem is: given a system of linear equations over a module lattice, where each equation has a small amount of random noise added to the right-hand side, recover the secret vector that satisfies the noise-corrupted system. This problem generalizes the classical Learning With Errors problem, and its hardness has been the subject of intense study since 2005. The current best attacks require exponential time in the dimension of the lattice. ML-DSA-65 chooses lattice parameters that put the attacker's effective cost above 2^192 classical operations, which is NIST security category 3.

FALCON-512 security rests on the Short Integer Solution assumption over NTRU lattices. The NTRU lattice is a specific algebraic structure that was first proposed by Hoffstein, Pipher, and Silverman in 1996, and has a substantially different mathematical flavor from the module lattices underlying ML-DSA. The Short Integer Solution problem over NTRU asks: given a set of vectors in an NTRU lattice, find a short integer linear combination that lies in a specific sublattice. The best known attacks on NTRU-SIS require either direct lattice reduction (BKZ-style attacks whose cost is exponential in the lattice dimension) or algebraic attacks that exploit the NTRU structure (which have been refined over 25+ years but have never achieved a break at the parameter sets NIST accepted). FALCON-512 chooses parameters that put NIST security category 1, approximately 2^128 classical operations.

SLH-DSA-SHA2-128f security rests entirely on the pre-image resistance of SHA2-256 as a cryptographic hash function. There are no lattice problems, no algebraic structures, no trapdoor assumptions. The entire security argument reduces to: can an adversary, given a SHA-256 output, find an input that hashes to that output? If the answer is no (if SHA-256 is a good random oracle), SLH-DSA signatures cannot be forged. If the answer is yes, SLH-DSA is broken. The current best attacks on SHA-256 require approximately 2^128 operations classically and approximately 2^128 operations under Grover's algorithm, bringing SLH-DSA-SHA2-128f to NIST security category 1.

Three schemes. Three mathematical foundations. Module lattices, NTRU lattices, hash pre-image resistance. The cryptographic research communities that attack these three problems are largely distinct. The techniques that work against one of them usually don't transfer to the others. A breakthrough in attacking module lattices does not typically translate into a breakthrough in attacking NTRU lattices or hash functions, and a cryptanalytic breakthrough against hash pre-image resistance is in many ways the least similar of the three to a breakthrough against either lattice problem.

What we are relying on, when we sign a substrate under all three families and require all three signatures to verify, is that a single adversary cannot simultaneously break all three problems. This is a bet about the structure of cryptographic failure. Historically, when a cryptographic family breaks, it breaks for a structural reason that is specific to the family, not for a reason that generalizes to every other family. DES's weakness in the 1990s did not also break RSA. The MD5 collision attacks of 2004 did not also break AES. The BEAST TLS attack of 2011 did not also break SSH key exchange. The Logjam attack of 2015 did not also break elliptic curve cryptography. And so on. When a cryptographic primitive breaks, the break is usually specific.

The three-family structure of the substrate is an insurance policy against exactly the kind of cryptanalytic surprise that would otherwise be a total break. Pick the one family you think is most likely to survive, and even if you're wrong — even if your best-guess family is the one that falls first — the other two are still standing. An attacker who has cracked ML-DSA still has to crack FALCON and SLH-DSA before a substrate forgery is possible. An attacker who has cracked SHA-256 still has to crack MLWE and NTRU-SIS. The attacker's work is cumulative across the three families, not substitutable between them.

The honest security level

Before going further, I need to say something that a lot of marketing material about three-family schemes gets wrong: the substrate's effective NIST security level is Level 1, not Level 3 or Level 5, and I want to be precise about why.

NIST security levels for post-quantum signatures are floors, not averages. NIST Level 1 means: approximately 128 classical bits of security, which is the equivalent of brute-forcing a 128-bit symmetric key. Level 3 means approximately 192 bits. Level 5 means approximately 256 bits. When you compose multiple signature families together, the effective level of the composition is bounded by the lowest-level component, because an adversary only has to defeat the weakest link in the chain.

In our three-family bundle:

• ML-DSA-65 is NIST Level 3 (approximately 192 classical bits)
• FALCON-512 is NIST Level 1 (approximately 128 classical bits)
• SLH-DSA-SHA2-128f is NIST Level 1 (approximately 128 classical bits)

The minimum of these three is 128 bits. That is the substrate's claimed NIST security level under the all-three-must-succeed verification policy. If you forge the weakest link, you have forged the bundle (because you still have to forge the other two, but the cost of forging the other two is also at least 128 bits, so the overall attacker cost is 128 bits of effort to break the weakest family and 128+ bits each to break the others — but those later costs only matter after you have succeeded at the first one, so the floor is 128).

This framing is not as punchy as "three Level 3 families" or "three Level 5 families," which is what some other three-family schemes have claimed in their marketing. But it's honest. When you describe the substrate as providing "three independent hardness assumptions at NIST security category 1," anyone who knows what NIST security categories mean can verify the claim by checking the underlying parameter sets. The honest claim is defensible. The exaggerated claim would unravel the first time a careful reviewer read the module spec.

The upside of honesty: when we say "three independent hardness assumptions," we are not hiding behind an inflated NIST level to dodge the independence claim. The independence of the three hardness assumptions — MLWE versus NTRU-SIS versus SHA-256 pre-image resistance — is a property that holds at any NIST level. Three Level 1 assumptions, independently, is a stronger security posture against cryptanalytic surprise than one Level 5 assumption alone.

Here's the intuition. Imagine a cryptanalyst announces a breakthrough attack against MLWE at NIST Level 3 parameters. The breakthrough reduces the cost of attacking ML-DSA-65 from 2^192 to, say, 2^100. An ML-DSA-only deployment at Level 3 would be catastrophically broken — every signature ever produced under that deployment becomes forgeable. The substrate's ML-DSA-65 component would also be degraded, but the substrate's overall security would not collapse, because FALCON-512 (NTRU-SIS, not affected by the MLWE breakthrough) and SLH-DSA-SHA2-128f (hash pre-image, not affected by any lattice breakthrough) are still standing at their original 2^128 cost. The substrate's effective security degrades from 2^128 (the NIST Level 1 floor) to 2^128 (unchanged, because the weakest link in the chain did not get any weaker). A single-family Level 3 scheme would be totally broken. A three-family Level 1 bundle would survive.

Now imagine the breakthrough is against NTRU-SIS instead. FALCON collapses. ML-DSA-65 is unaffected (module lattices, not NTRU). SLH-DSA-SHA2-128f is unaffected. The substrate's effective security stays at 2^128. And again: a single-family NTRU-based scheme would be totally broken, but the substrate survives.

Now imagine a breakthrough against SHA-256 pre-image resistance. SLH-DSA collapses. ML-DSA and FALCON are unaffected. The substrate stays at 2^128.

In every one of these three hypothetical breakthrough scenarios, the substrate's security degrades from "three independent assumptions at Level 1" to "two independent assumptions at Level 1," which is still stronger than any commercially available alternative. And in all three scenarios, a single-family deployment at Level 3 or Level 5 would be a total break.

This is the trade. A Level 3 or Level 5 single-family scheme is stronger than the substrate against brute-force attacks that respect the assumed hardness of the scheme's underlying problem. A three-family Level 1 bundle is stronger against cryptanalytic breakthroughs that violate the assumed hardness of any single scheme. Which trade is correct depends on which threat model you are betting against.

We bet against cryptanalytic breakthrough, for two reasons.

First, cryptanalytic breakthroughs are historically the way post-quantum schemes die. The NIST PQC standardization program itself lost multiple candidates to unexpected cryptanalytic work between 2017 and 2022 — Rainbow fell to a key recovery attack, SIKE fell to a polynomial-time attack, GeMSS fell, and several others. These were not gradual erosion of security margins. They were sudden total breaks. The signatures produced under the affected schemes went from secure to forgeable in a single publication. The substrate's three-family structure is designed precisely to survive that failure mode.

Second, an adversary who actually has a 2^128 budget is, in practical terms, a state-level attacker with access to purpose-built quantum hardware that probably does not exist yet in 2026. An adversary with a cryptanalytic breakthrough is a single paper that drops on arxiv.org next Thursday. The first kind of adversary is rare and expensive. The second kind of adversary is one NeurIPS submission away. We design against the more likely failure mode.

What composing three families costs

The three-family structure is not free. There are specific costs and we're going to be honest about each of them.

Signing cost. The substrate has to produce three signatures for every signing event. On a modern CPU core, ML-DSA-65 signs in roughly 300 microseconds, FALCON-512 signs in roughly 150 microseconds, and SLH-DSA-SHA2-128f signs in roughly 5 milliseconds. The dominant cost is SLH-DSA, by roughly an order of magnitude. The three-family bundle's total signing cost is approximately 5.5 milliseconds per signing event, of which SLH-DSA is 91%. In parallel, a well-optimized implementation can run all three signings concurrently on a three-core machine and complete the bundle in 5 milliseconds (the SPHINCS+ cost), overlapping the other two families.

Throughput under this cost model is approximately 180 signings per second per core, which is low compared to a single-family scheme (ML-DSA-65 alone would be roughly 3,300 signings per second per core). We recover the throughput through batched Merkle aggregation, which we'll cover in detail in another post. Short version: one bundle signs over a root of N per-leaf substrates, bringing the amortized per-leaf cost to 5.5 milliseconds divided by N, which at N=1000 is 5.5 microseconds per leaf.

Ephemeral storage cost. The three raw signatures together are approximately 21 kilobytes: 3,309 bytes for ML-DSA-65, approximately 666 bytes for FALCON-512, and 17,088 bytes for SLH-DSA-SHA2-128f. The dominant cost is again SLH-DSA. This is a lot of bytes relative to a classical ECDSA signature (64 bytes) or even a single ML-DSA-65 signature, and it is one of the reasons the substrate separates the ephemeral signature bundle from the persistent commitment. The persistent footprint is 74 bytes (substrate plus compact receipt plus on-chain anchoring, accounting for double-counted bytes); the 21 KB of raw signatures lives in an off-chain signature store operated by the signer and is fetched by verifiers who need to perform the cryptographic verification.

This two-tier persistence model is not an accident. The 74 bytes is what you pay to the blockchain. The 21 KB is what you pay to the signature store. If you lose the 21 KB, you lose the ability to fully verify historical substrates — but you keep the 74 bytes, which tells you that a substrate with a specific signing message existed at a specific time, even if you can no longer perform the full three-family verification. Degraded verification is still useful; it's just weaker. If you have both the 74 bytes and the 21 KB, you have the full chain of evidence back to the signer's three-family public key set.

Verification cost. Verification is the reverse of signing: all three signatures have to be verified. ML-DSA-65 verify is approximately 150 microseconds, FALCON-512 verify is approximately 100 microseconds, SLH-DSA-SHA2-128f verify is approximately 300 microseconds. In parallel, the three verifications can be overlapped and a bundle verify completes in roughly 300 microseconds (the SPHINCS+ bottleneck). On a commodity client machine, a single-thread verify of a substrate plus receipt plus bundle is approximately 593 microseconds wall clock, including all three signature verifications plus SHA3-256 recomputation, compact receipt parsing, and structural checks. This is a per-verify cost that matters for workloads where verification happens on many machines simultaneously, but it is not a bottleneck for most deployment patterns.

Key generation cost. Each of the three families has its own keypair, and each keypair must be generated independently at key rotation time. For production deployments the cost is amortized across long key lifetimes, but key generation for SLH-DSA-SHA2-128f specifically is on the order of 30-40 milliseconds, which is much slower than ML-DSA-65 keygen (roughly 0.5 milliseconds) or FALCON-512 keygen (roughly 5 milliseconds). In practice, keys are rotated on a 6-12 month cadence and the keygen cost is a one-time event per epoch.

Complexity cost. Three families means three separate dependency trees, three separate parameter sets, three separate test vectors, three separate known-answer-test corpora. Implementing and maintaining a three-family signer is more engineering work than implementing a single-family signer. We rely on the NIST reference implementations (via pqclean and the pqcrypto Rust crates) for each family, which reduces the cryptographic implementation burden, but the orchestration code that calls all three in parallel and assembles the compact receipt is our own and has its own maintenance tail.

None of these costs seemed prohibitive to us relative to the security benefit. The signing cost is dominated by SLH-DSA-SHA2-128f, which we would have had to pay anyway if we'd chosen a single-family hash-based scheme. The ephemeral storage cost is dominated by SLH-DSA-SHA2-128f, same reason. The verification cost is acceptable for any deployment pattern we're realistically expecting. The complexity cost is a one-time engineering tax on us, not an ongoing cost on our customers.

In exchange for these costs, we get the three-independence property. We consider it a favorable trade. Your mileage may vary depending on your threat model.

Why not a threshold scheme

A reasonable question at this point is: "If you want multiple signature families for defense in depth, why not use a threshold-of-three structure where the substrate is valid if any two of the three families verify? That would let you survive a complete loss of one family without completely invalidating historical substrates."

We considered this and rejected it, for two reasons.

First, a threshold scheme gives an attacker a choice. Under an any-two-of-three rule, an attacker can target whichever family they think is easiest to break and ignore the other two. If a breakthrough appears against ML-DSA-65, the attacker forges ML-DSA signatures and pairs them with either FALCON or SLH-DSA signatures (which they presumably have access to by legitimately obtaining them from the signer's oracle, or by already having forged one of those families earlier). A threshold-of-two scheme reduces the adversary's cost from "break three assumptions" to "break two assumptions," which cuts the security budget roughly in half (in rough terms; the formal analysis is subtle).

Second, an all-three rule produces a simpler security argument. "Substrate forgery requires breaking all three families" is one sentence. "Substrate forgery requires breaking two of three families in a threshold configuration" is harder to reason about, harder to reduce to the underlying assumptions cleanly, and harder to audit for exactly the failure modes we care about. Simple security arguments are easier to defend in front of a skeptical reviewer.

The cost of the all-three rule is that a complete loss of one family does invalidate historical substrates, because a historical substrate signed under the now-broken family has, by definition, been produced under a rule that required all three to verify, and the verification rule cannot retroactively relax. We accept this cost because it is the symmetric consequence of the security benefit. If we wanted graceful degradation under single-family failure, we would need a different verification rule, and that rule would open the attack surface a threshold scheme introduces.

The upgrade path

We are not locked into the specific three-family composition we ship today. The compact receipt's algorithm_flags byte is a bitfield with eight positions, one for each supported signature family. The current production bundle uses bits 0, 1, and 2 for ML-DSA-65, FALCON-512, and SLH-DSA-SHA2-128f. Bits 3 through 6 are reserved for ML-DSA-87, FALCON-1024, SLH-DSA-SHA2-192f, and SLH-DSA-SHA2-256f. Adding a new family or rotating to a higher security level is a matter of setting the appropriate bits in the flags byte and updating the verifier to check the signatures under the new parameter set.

The upgrade path we expect to take, when we take it, is to move from NIST Level 1 to uniform NIST Level 3. That means:

• ML-DSA-65 (Level 3) stays the same
• FALCON-512 (Level 1) upgrades to FALCON-1024 (Level 5)
• SLH-DSA-SHA2-128f (Level 1) upgrades to SLH-DSA-SHA2-192f (Level 3)

After the upgrade, the effective NIST security category of the bundle would be Level 3 (set by the weakest family, now SLH-DSA-SHA2-192f at Level 3). The upgrade approximately doubles the signing time and roughly doubles the ephemeral signature bundle size (FALCON-1024 is about 3× the size of FALCON-512, SLH-DSA-SHA2-192f is larger than SLH-DSA-SHA2-128f), which is an acceptable cost if the threat model justifies it.

We have not committed to the upgrade because the current bundle's effective security is adequate under all threat scenarios we can currently articulate. A deployment that specifically requires NIST Level 3 uniformity can opt into the upgraded bundle, and the wire format already supports it via the algorithm flags byte.

What to take away

The three-family structure of the substrate is a specific design choice with specific costs and specific benefits. The costs are: more signing time, more verification time, more ephemeral storage, more keygen time, more engineering complexity. The benefits are: forgery requires simultaneously breaking three mutually disjoint mathematical hardness assumptions, which is a stronger security posture against cryptanalytic surprise than any commercially available single-family alternative we are aware of.

The honest security level of the bundle is NIST Level 1, bounded by FALCON-512 and SLH-DSA-SHA2-128f. We do not inflate this to Level 3 or Level 5 in our marketing because doing so would undermine the independence claim we actually care about. Three Level 1 independent assumptions is stronger against cryptanalytic breakthrough than one Level 5 assumption alone, and stronger is the right word.

If a single-family scheme is sufficient for your threat model, the substrate is not the right tool for you. You should use whichever family best fits your cost and performance constraints. If your threat model requires insurance against the kind of cryptanalytic surprise that has historically killed NIST PQC candidates on a publication-to-publication basis, the substrate is the only post-quantum signing primitive we know about that gives you three-family independence in a single signing operation, with a single persistent commitment, and a single public key set to manage.

We built it because we thought that was a useful thing to have. We're shipping it because we're confident enough in the security argument to put our names on it and let the bitcoin-dev and cryptographic-research communities take a run at it.

The next post in this series is about three contended-lock bugs we found in our cache layer when we ran the substrate at 96 concurrent workers on a bare-metal Graviton4 instance, and what we learned about writing high-concurrency Rust observability code in the process. See you there.