Three Math Families, One Attestation: Why We Don't Bet on a Single Algorithm

The History of "Unbreakable"

In 1977, RSA's inventors publicly challenged anyone to factor a 129-digit number. They estimated it would take 40 quadrillion years. It was factored in 1994—17 years later, not 40 quadrillion.

In 2001, the National Institute of Standards and Technology certified SHA-1 as a federal standard for digital signatures. In 2005, theoretical attacks were published. In 2017, Google produced the first practical collision. SHA-1 went from "standard" to "deprecated" to "actively dangerous" in about 15 years.

RSA with 512-bit keys was considered adequate security in 1999. By 2009, a team factored a 512-bit RSA key in 73 days. The entire class of RSA keys that governments and banks relied on for a decade became insecure in less time than a mortgage term.

The pattern is consistent: a mathematical assumption is believed to be hard, systems are built on that assumption, and then a breakthrough (algorithmic, computational, or both) undermines the assumption. The systems that survive are the ones that don't depend on a single assumption.

The Three NIST Families

NIST standardized three post-quantum signature algorithm families specifically because they recognized this risk. Each family relies on a fundamentally different mathematical hardness assumption.

ML-DSA (Dilithium): Module Learning With Errors

Dilithium's security is based on the difficulty of solving the Module Learning With Errors (MLWE) problem. Given a matrix A and a vector b = As + e (where s is a secret vector and e is a small error vector), recovering s from (A, b) is believed to be computationally infeasible, even for quantum computers.

MLWE is a structured variant of the general Learning With Errors (LWE) problem, which has been studied extensively since Oded Regev's seminal 2005 paper. The structure (polynomial rings) makes it efficient but also introduces algebraic properties that might eventually be exploitable. No one has demonstrated such an exploit, but the algebraic structure is richer than the unstructured version, which is a theoretical concern.

Dilithium is NIST's primary recommendation. It has good all-around performance, reasonable key and signature sizes, and straightforward implementation. It's the obvious first choice for anyone adding post-quantum signatures to their system.

It is also, by itself, a single point of failure.

FALCON: Short Integer Solution over NTRU Lattices

FALCON's security is based on the Short Integer Solution (SIS) problem over NTRU lattices. NTRU is a different lattice construction from the module lattices used by Dilithium. While both are "lattice-based," the specific mathematical structure is distinct.

The analogy: Dilithium and FALCON are both "lock-based" security, but one uses a pin tumbler lock and the other uses a disc detainer lock. A lockpick designed for pin tumblers doesn't work on disc detainers. Similarly, an algorithm that efficiently solves MLWE doesn't automatically solve SIS-over-NTRU.

That said, they share the broad category of lattice cryptography. A sufficiently general breakthrough in lattice mathematics—one that undermines the hardness of lattice problems across all constructions—could theoretically weaken both. This is why a third family from an entirely different mathematical foundation matters.

SLH-DSA (SPHINCS+): Hash Function Security

SPHINCS+ relies on nothing except the security of hash functions. No lattice assumptions. No algebraic structure. No number theory. If SHA-256 (or SHA-3, or SHAKE) is a secure hash function—meaning it's collision-resistant, preimage-resistant, and second-preimage-resistant—then SPHINCS+ is secure.

Hash-based signatures are the oldest known construction for post-quantum security. Lamport signatures (the conceptual ancestor of SPHINCS+) were described in 1979. The security proof has been refined over four decades. It is the most conservative, most studied, and most mathematically minimal of the three families.

The tradeoff is size. SPHINCS+ signatures at the fastest parameter set are 17,088 bytes. This is why most systems skip it. It's too large for on-chain use, too slow for real-time signing, and seemingly unnecessary when Dilithium works fine.

Until the day it doesn't.

The Independence Argument

The reason to use all three families is not that any one of them is weak. All three are believed to be strong. The reason is that mathematical beliefs change, and the cost of being wrong is total.

Consider the probability spaces:

Single-family (Dilithium only): If MLWE is broken, 100% of attestations are compromised. Every transaction. Every document. Every identity credential. Retroactively. There is no fallback.

Two-family (Dilithium + FALCON): If MLWE is broken, FALCON's SIS-over-NTRU still holds. The attestation degrades but survives. However, if the breakthrough is broad enough to affect all lattice constructions, both families fall. The two families are correlated—not identical, but correlated.

Three-family (Dilithium + FALCON + SPHINCS+): If both lattice families break, the hash-based family survives. An attacker would need to break structured lattices AND hash function security to forge an attestation. These are not correlated problems. A breakthrough in algebraic geometry (which might undermine lattices) has no bearing on hash function security (which depends on combinatorial properties of bit transformations).

The probability of all three families being broken simultaneously is not the sum of individual probabilities—it's closer to the product. If each family has a 1-in-1,000 chance of being fundamentally weakened in the next 30 years (an extremely conservative estimate), the chance of all three failing is 1-in-1,000,000,000. Single-family: 1-in-1,000. Three-family: 1-in-a-billion.

The Cost Misconception

The conventional argument against multi-family signing is cost. Three signatures are three times the size, three times the computation, three times the verification time. For systems that put signatures on-chain, this is a real barrier. Dilithium alone is 3,309 bytes. Adding FALCON adds 657 more. Adding SPHINCS+ adds 17,088 on top. The total is 21,054 bytes, and no blockchain can absorb that per transaction.

This cost argument is based on the assumption that all three raw signatures need to persist. They don't.

We built a system where the three signatures exist in memory for approximately 15 milliseconds while being independently verified. After verification, the results are compressed into a 42-byte receipt and the raw signatures are securely erased. Combined with a 32-byte on-chain hash, the total persistent footprint is 74 bytes.

74 bytes for three families. That's 16 bytes more than a single Schnorr signature. The on-chain cost is lower than Dilithium alone would be. The computational cost is about 15 milliseconds at attestation time (dominated by SPHINCS+ signing), but verification is a sub-microsecond lookup thereafter.

The cost of three families is not three times anything. It's 74 bytes.

What Breaks and What Survives

Let's walk through specific failure scenarios.

Scenario 1: MLWE breakthrough (Dilithium falls)

A new algorithm is published that efficiently solves the Module Learning With Errors problem for the parameter sizes used by Dilithium. All Dilithium signatures become forgeable.

Single-family system: Every attestation ever produced is now worthless. All historical transactions, all archived documents, all identity credentials signed with Dilithium can be forged retroactively.

Three-family system: The verification receipt records that Dilithium, FALCON, and SPHINCS+ all verified. With Dilithium compromised, verifiers can check whether FALCON and SPHINCS+ are still intact. If the MLWE breakthrough doesn't extend to NTRU lattices (which is likely, given the structural differences), FALCON still holds. SPHINCS+ holds unconditionally (no lattice dependence). The attestation is weakened but still carries two valid proofs from two independent families.

Scenario 2: Broad lattice breakthrough (Dilithium and FALCON fall)

A breakthrough affects all lattice-based cryptography—both MLWE and SIS-over-NTRU. Both Dilithium and FALCON are compromised.

Two-family system (Dilithium + FALCON): Total failure. Both families are from the lattice category. Both fall.

Three-family system: SPHINCS+ survives. It has zero lattice dependence. The attestation still carries one valid proof from a mathematically independent family. The verifier can distinguish "both lattice families compromised, hash-based intact" from "all families compromised" because the receipt records which families verified.

Scenario 3: Hash function breakthrough (SPHINCS+ falls)

A fundamental weakness is found in SHA-256 or SHA-3, undermining the hash function assumptions that SPHINCS+ depends on.

Three-family system: Both lattice families (Dilithium and FALCON) still hold. Hash function weaknesses don't affect lattice problems. Two of three families survive.

Scenario 4: All three fall simultaneously

A single breakthrough undermines structured lattices AND hash function security.

This would require a mathematical result so fundamental that it invalidates both algebraic hardness assumptions (lattices) and combinatorial hardness assumptions (hash functions). Such a result would essentially mean that P = NP or something equivalently catastrophic for computational complexity theory. If this happens, post-quantum cryptography is the least of the world's problems—every secure system ever built, classical or quantum, would also be broken.

Graceful Degradation

The three-family approach doesn't just provide backup. It provides information about the nature of a compromise.

The 42-byte verification receipt includes a bitmask recording which families verified the attestation. A verifier checking an attestation years after it was created can assess its current trustworthiness:

• All three families intact: Maximum confidence. The attestation is as strong as the day it was created.
• Two families intact, one weakened: High confidence. The attestation is degraded but still backed by two independent proofs. Consider re-attesting with a replacement algorithm if available.
• One family intact, two weakened: Moderate confidence. The attestation is backed by a single proof. Priority re-attestation recommended.
• All three weakened: Low confidence. The attestation should be considered unverifiable. But this scenario requires three independent mathematical breakthroughs.

This is graceful degradation. The system doesn't go from "secure" to "broken" in a single event. It degrades in steps, giving organizations time to respond, re-attest, and adapt. A single-family system has exactly two states: working and broken. A three-family system has a gradient.

Why Not Four? Why Not Five?

There's a reasonable question about where to stop. If three is better than one, why not use every post-quantum algorithm available?

The answer is diminishing returns and practical coverage.

NIST standardized three families because they represent the three major categories of post-quantum hardness assumptions: structured lattices (MLWE), unstructured lattices (NTRU/SIS), and hash functions. These three categories cover the known landscape of post-quantum mathematics. Adding a fourth family would mean adding a fourth mathematical assumption, and no established fourth assumption exists with the same level of study and confidence.

Code-based cryptography (McEliece) is a candidate, but it has enormous key sizes and no standardized signature scheme. Multivariate cryptography has had multiple schemes broken during the NIST process. Isogeny-based cryptography (SIDH/SIKE) was catastrophically broken in 2022.

Three families is not an arbitrary number. It's the number of well-studied, independently-founded mathematical frameworks available for post-quantum signatures. Using all three is comprehensive coverage. Using fewer is accepting unnecessary risk.

The Implementation Cost

Multi-family attestation sounds expensive. It isn't.

At attestation time (once per event):

• Dilithium signing: ~180 microseconds
• FALCON signing: ~150 microseconds
• SPHINCS+ signing: ~14.5 milliseconds
• Verification (all three): ~1 millisecond
• Receipt compression: <1 microsecond
• Total: ~16 milliseconds

At verification time (every subsequent check):

• Receipt lookup: 0.059 microseconds

The 16-millisecond attestation cost is a one-time event. Every subsequent verification is a sub-microsecond lookup. For a system that processes millions of verifications per second, the amortized cost of three-family attestation is effectively zero.

And the persistent storage cost—74 bytes—is the same whether you use one family or three. The on-chain hash (32 bytes) and the receipt (42 bytes) don't grow with the number of families. The additional families add to the ephemeral attestation-time cost only. The persistent footprint is constant.

The Single-Family Trap

Most organizations adopting post-quantum cryptography today are choosing Dilithium and stopping. It's the NIST primary recommendation. It's well-supported in libraries. It's fast. It's "good enough."

Every RSA deployment in the 1990s was also "good enough." Every SHA-1 deployment in the 2000s was also "good enough." The organizations that survived the transitions were the ones that had planned for algorithm agility—the ability to swap in a new algorithm without rebuilding the system.

Multi-family attestation is the strongest form of algorithm agility. You don't need to swap anything if a family breaks. You still have two others. The system continues to function with reduced but non-zero security. You have time to add a replacement family when one becomes available, without the panic of a single-point-of-failure compromise.

74 bytes. Three families. One attestation. The cost of being wrong with one family is catastrophic. The cost of being right with three is twenty-six extra bytes.