1. Evidence with a thirty-year horizon

Most software systems sign for authentication: you prove who you are right now, the session lasts an hour, the signature is forgotten. Institutional infrastructure signs for the record: this board resolution was authorized, this compliance evaluation was performed, this sanctions check returned clean – and the proof must hold up decades later, in front of a tribunal that does not yet exist, under rules that have not yet been written.

Thirty years is longer than many deployed primitives have lasted. DES, MD5, SHA-1, RC4, and 512-bit RSA each entered and left service inside such a window. A design for archival signatures therefore cannot assume that any single cryptographic assumption survives the retention period; it must remain sound when some of its assumptions fail.

2. Threat model

The signatures in general institutional use – RSA, ECDSA, Ed25519 – rest on the hardness of factoring or of computing discrete logarithms. Shor’s algorithm solves both in polynomial time on a sufficiently large quantum computer (Shor, 1997). Estimates of when such a machine will exist range from ten to thirty years and are themselves contested – precisely the horizon over which institutional records must remain valid. Post-quantum schemes are beginning to deploy – stateful hash-based signatures are standardized for firmware signing (NIST SP 800-208, 2020), and ML-DSA is entering protocol stacks – but the installed base signing institutional records today remains overwhelmingly pre-quantum, RSA and elliptic-curve alike.

The adversary we defend against holds the public archive and unbounded time. The threat is not that a quantum computer will forge future signatures; new signatures can simply use new schemes. The threat is retroactive: forgery against a signature scheme requires only the public key and a target message, and an institutional archive – retained by design – supplies both, indefinitely. This is the signature analogue of harvest-now-decrypt-later, and it is structural rather than opportunistic: no interception is needed, because retention is the point of the system. For institutional retention periods, “later” falls squarely inside the window. The compliance archive is the attack surface.

Concretely: a compliance record signed in 2026 with Ed25519 attests that a specific entity passed a specific sanctions check on a specific date. The signature binds the attestation to the attester. If Ed25519 falls in 2040, an adversary can forge not only future signatures but that specific historical one. The proof that was valid for fourteen years suddenly proves nothing. Worse: the adversary can produce a different record, with a valid signature from the same key, attesting to whatever they like.

Mosca’s inequality frames the timing (Mosca, 2018): if the time records must stay valid, plus the time migration takes, exceeds the time until a cryptographically relevant quantum computer, then some records are exposed. Both terms on the left are measured in decades here.

Three exposures are out of scope. Compromise of a signing key defeats any signature scheme and is an operational-custody problem. Implementation side channels are orthogonal to scheme choice. And confidentiality is a different problem: harvest-now-decrypt-later against encrypted records is real and adjacent, but this paper is about signatures – whether the archive’s evidence survives, not whether its secrets do.

3. The hybrid construction

NIST’s post-quantum standardization has produced signature standards in two families. FIPS 204 standardizes ML-DSA (formerly Dilithium), a module-lattice scheme; FIPS 205 standardizes SLH-DSA (formerly SPHINCS+), a stateless hash-based scheme. Code-based and multivariate signatures remain under evaluation in NIST’s additional-signature process, and the competition’s own record is cautionary: candidates with rich algebraic structure, one of them a finalist, fell to classical attacks (Section 4). The two standardized families rest on different mathematical foundations, with different performance and different risk profiles. The conservative approach is to keep the classical scheme and add one of each.

A hybrid signature is an AND composition. Fix the component schemes – here Ed25519, ML-DSA-65, and SLH-DSA-SHA2-128s – and give the suite a name. To sign, encode the record together with a tag naming the suite in force, and sign that same encoding once with each component key. The composite verifies only if every component signature verifies against that encoding. The tag does two jobs: because every component signs it, a signature made under one suite cannot be presented as a signature made under another; and it is the hook on which verification policy and the retirement machinery of Section 6 hang – a verifier reads the tag to learn which components the policy in force when the record was signed requires. Forging the composite requires forging every component, so the combiner is existentially unforgeable if any one component is: for two components this is the concatenation-combiner theorem of Bindel, Herath, McKague, and Stebila (2017), and the three-component statement follows by iterating the pairwise combiner. We cite the reduction rather than prove it; the same framework treats key-substitution attacks and non-separability, and neither property is claimed here.

Why keep Ed25519 at all? Because it is fast, compact, and has been under public cryptanalysis since 2011, building on Curve25519 from 2006 (Bernstein, Duif, Lange, Schwabe, and Yang, 2012). Dropping it in favor of post-quantum-only schemes would sacrifice known-good classical security for algorithms that are newer and less battle-tested. The hybrid does not ask you to trust any single algorithm. It asks only that at least one of three holds.

Why both post-quantum families? Because they rest on genuinely different assumptions. ML-DSA-65’s unforgeability rests on two module-lattice assumptions – Module-LWE and a self-target variant of the module short-integer-solution problem (Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, and Stehlé, 2018). No efficient quantum algorithm is known for either, but both are algebraic, and neither has the maturity of the problems it replaces. SLH-DSA’s assumptions are properties of a hash construction built from SHA-256. They are not literally the properties the rest of deployed cryptography relies on – the scheme needs multi-target and truncated-output variants – but they are of the same kind: no algebra, no trapdoor, only the claim that a well-studied compression function resists generic attack. A thirty-year archive needs at least one component in that assumption class.

4. The hash-based anchor

Lattice-based cryptography is algebraic. There is structure – a lattice, a ring, a module – and security depends on that structure being hard to exploit. Algebraic structure is where attacks have historically landed. The number field sieve exploited the ring structure of algebraic number fields to cut the cost of factoring from the quadratic sieve’s L[1/2] to L[1/3]: it did not break RSA outright – RSA-250, at 829 bits, is the factoring record (Boudot, Gaudry, Guillevic, Heninger, Thomé, and Zimmermann, 2020), and RSA-2048 stands classically – but it collapsed the security margin and drove keys from 512 to 3,072 bits. The discrete logarithm on elliptic curves falls to Shor’s algorithm the day a cryptographically relevant quantum computer exists. And the post-quantum competition supplied the sharpest recent evidence: SIKE, an isogeny-based alternate candidate, fell to a classical key-recovery attack running in about an hour on a single core (Castryck and Decru, 2023), and Rainbow, a multivariate signature finalist, to a key-recovery attack running over a weekend on a laptop (Beullens, 2022). Whether module-lattice structure holds is an open question; an institutional archive cannot rest on it alone.

Hash-based signatures have no algebraic structure to attack. SLH-DSA is a stateless hash-based scheme: a Merkle tree of one-time signatures over a few-time signature layer (FORS). Its security reduces to properties of the underlying tweakable hash construction – multi-target second-preimage resistance, pseudorandomness, and, for the FORS layer, interleaved target subset resilience (Bernstein, Hülsing, Kölbl, Niederhagen, Rijneveld, and Schwabe, 2019). The scheme requires no collision resistance: a SHA-256 collision, the failure mode that retired MD5 and SHA-1 (Section 1), does not by itself yield a forgery. No lattice, no ring, no group; forging a signature requires defeating one of the hash properties above. FIPS 205 standardizes the “simple” instantiations, whose security analysis lives in the quantum random-oracle model; the original tweakable-hash proof contained a flaw, found and repaired in Hülsing and Kudinov (2022) – a useful reminder that even the conservative component’s guarantees are proofs about models, not facts about SHA-256.

The quantum arithmetic must be applied to the parameters the scheme exposes. SLH-DSA-SHA2-128s instantiates its internal functions with SHA-256 and truncates their outputs to sixteen bytes: the targets an attacker must defeat are 128 bits wide, not the 256-bit digest width. Grover’s algorithm gives a quadratic speedup for generic search (Grover, 1996), and quadratic is optimal in the black-box model (Bennett, Bernstein, Brassard, and Vazirani, 1997), so generic preimage search against these targets costs on the order of 2^64 sequential quantum hash evaluations, against 2^128 classical. NIST prices this as security category 1: as hard as quantum key search on AES-128. Two caveats run in the same direction and are stated plainly. The optimality bound is an oracle result; it does not by itself rule out an attack exploiting the concrete structure of SHA-256. And category 1 is the lowest standardized level: at this instantiation the hash-based component is the most conservative limb by assumption class and the lowest by numeric category, while the lattice limb, ML-DSA-65, sits at category 3. A deployment that wants matching numbers raises the anchor’s parameter set – SLH-DSA-SHA2-256s is category 5 at a 29,792-byte signature – a parameter choice, not a design change.

This is the role each component plays. The lattice-based signature is the pragmatic post-quantum layer: fast and reasonably compact. The hash-based signature is the last-resort layer: larger and slower, but resting on the most conservative assumption class available.

5. Cost

The hybrid is not free, and the price should be stated exactly. An Ed25519 signature is 64 bytes. The composite at the instantiation above is 11,229 bytes – 64 for Ed25519, 3,309 for ML-DSA-65, 7,856 for SLH-DSA-SHA2-128s – and the composite public key is 2,016 bytes. Verification rises from microseconds to low milliseconds. Signing is dominated by SLH-DSA: the small-signature “s” parameter sets cost hundreds of milliseconds of CPU per signature, and the “f” sets trade roughly twice the signature size (17,088 bytes for SLH-DSA-SHA2-128f) for an order of magnitude faster signing. Beyond size and time there is operational surface: each signer manages three key pairs – generation ceremony, custody, and rotation, tripled – and each verifier maintains three implementations at exact parameter sets, selected by the suite tag, for as long as the archive lives.

These costs would be prohibitive for a network protocol signing every packet. The signing contexts this design serves are institutional: compliance attestations stored alongside regulatory documents orders of magnitude larger; periodic digests of ledger state, signed once per synchronization interval; audit-trail entries, signed once per event in a pipeline that already commits a database transaction at ten to a hundred milliseconds. None of these is a high-frequency, size-constrained context. Eleven kilobytes and low-millisecond verification are noise in that budget.

6. Why migration starts now

The standard objection: quantum computers do not exist yet; defer migration until they do.

Migration takes years, and the archive is already accumulating – Section 2’s inequality is the general form of the problem. The specific form is what could later be done with an Ed25519-only archive. Re-signing it under a post-quantum scheme is not a software update. It requires the original attester, who may no longer exist as a legal entity; the original evidence, which may have been redacted under data-protection rules; and the original compliance evaluation, which was performed under rules that have since changed. For a significant fraction of a decades-deep archive, re-signing is impossible.

The archival literature has a better tool, and the companion Intelligent Assets paper builds its record-custody construction on it: a record can be re-anchored without being re-signed. Append a fresh witness over the digest of the old record, signed under the successor scheme, while the retiring scheme is still sound. The historical entry is untouched and its original signature stands as the artifact it always was; verification runs under the policy in force when the record was signed, read off the suite tag of Section 3; and a verifier who no longer trusts the retired scheme has a chain to one it does trust. The construction recurses, each generation anchoring the last, and it needs no original attester. This is the mechanism of timestamp renewal and evidence records (RFC 3161; RFC 4998) and of the ETSI long-term archive profiles (ETSI EN 319 122-1, 2016).

Re-anchoring has one hard constraint, and the constraint is the argument for starting now: the bridge must be laid while the retiring scheme is still sound, and the break date is not announced. An Ed25519-only archive stakes that deadline on a single assumption – a credible weakening of one scheme starts an emergency re-anchoring campaign over the entire archive, racing a date nobody will publish. The hybrid spreads the same bet across three unrelated assumptions. The day one limb falls, nothing in the archive needs triage: every record remains unforgeable through the surviving components, and the bridging pass that retires the fallen limb runs as scheduled maintenance. That is also the answer to what a verifier does that day – nothing; the record still verifies, and its unforgeability now rests on the components still standing.

The hybrid also buys what re-anchoring alone cannot: each record’s base security is self-contained in one signature block, dependent on no witness chain and no timestamp authority. What it does not buy is freedom from maintenance. Over thirty years the hybrid’s own components will retire, and each retirement is a re-anchoring pass; the construction turns retirement from emergency into calendar work, it does not eliminate it.

So the conservative move is to sign with the hybrid from day one. Every record is protected from the moment of creation: no retroactive migration, no re-signing campaign, no gap in the evidentiary chain. The construction does not depend on a forecast. It is correct whether a cryptographically relevant quantum computer arrives in 2035, in 2045, or never. If never, the cost was eleven kilobytes per signature. If on time, the archive’s evidence survives for as long as any one of three unrelated assumptions holds.

7. Assumptions and limitations

The combiner theorem is cited, not proved. Unforgeability of the verify-all combiner reduces to the unforgeable component (Bindel, Herath, McKague, and Stebila, 2017), extended from two components to three by iteration. Key-substitution resistance and non-separability are analyzed in that framework and are not claimed here.

The hash-based analysis lives in the random-oracle model. FIPS 205’s “simple” instantiations carry security proofs in the quantum random-oracle model, for multi-target properties over truncated outputs (Bernstein et al., 2019; Hülsing and Kudinov, 2022). The Grover-optimality bound is a black-box result and says nothing about the concrete structure of SHA-256.

The security categories are asymmetric. At the analyzed instantiation the hash-based anchor is NIST category 1 and the lattice component category 3. Matching them is a parameter choice paid in bytes (Section 4), not a design change; the asymmetry is stated rather than hidden.

The operational surface triples. Three key pairs per signer and three verifier implementations per archive, maintained at exact parameter sets for decades. AND composition cuts both ways: unforgeability composes up, availability composes down – a defect in any one verifier rejects valid records.

Maintenance is reduced, not eliminated. Components retire over a thirty-year horizon, and each retirement is a scheduled re-anchoring pass (Section 6). The construction schedules the work; it does not remove it.

Scope. The design is sized for records, not packets, and is unfit for high-frequency signing. Signing-key compromise, implementation side channels, and the migration of encrypted data are out of scope (Section 2).

References

Adams, C., Cain, P., Pinkas, D., and Zuccherato, R. (2001). “Internet X.509 Public Key Infrastructure Time-Stamp Protocol (TSP).” RFC 3161.

Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. (1997). “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing, 26(5), 1510-1523.

Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., and Yang, B.-Y. (2012). “High-Speed High-Security Signatures.” Journal of Cryptographic Engineering, 2(2), 77-89.

Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., and Schwabe, P. (2019). “The SPHINCS+ Signature Framework.” In Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2129-2146.

Beullens, W. (2022). “Breaking Rainbow Takes a Weekend on a Laptop.” In Advances in Cryptology – CRYPTO 2022.

Bindel, N., Herath, U., McKague, M., and Stebila, D. (2017). “Transitioning to a Quantum-Resistant Public Key Infrastructure.” In Post-Quantum Cryptography (PQCrypto 2017), Lecture Notes in Computer Science 10346.

Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., and Zimmermann, P. (2020). “Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment.” In Advances in Cryptology – CRYPTO 2020.

Castryck, W. and Decru, T. (2023). “An Efficient Key Recovery Attack on SIDH.” In Advances in Cryptology – EUROCRYPT 2023.

Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehlé, D. (2018). “CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme.” IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1), 238-268.

ETSI (2016). Electronic Signatures and Infrastructures (ESI); CAdES Digital Signatures; Part 1: Building Blocks and CAdES Baseline Signatures. EN 319 122-1.

Gondrom, T., Brandner, R., and Pordesch, U. (2007). “Evidence Record Syntax (ERS).” RFC 4998.

Grover, L. K. (1996). “A Fast Quantum Mechanical Algorithm for Database Search.” In Proceedings of the ACM Symposium on Theory of Computing (STOC), 212-219.

Hülsing, A. and Kudinov, M. (2022). “Recovering the Tight Security Proof of SPHINCS+.” In Advances in Cryptology – ASIACRYPT 2022.

Lorgat, R. Intelligent Assets. Companion paper in this series.

Mosca, M. (2018). “Cybersecurity in an Era with Quantum Computers: Will We Be Ready?” IEEE Security & Privacy, 16(5), 38-41.

NIST (2020). Recommendation for Stateful Hash-Based Signature Schemes. Special Publication 800-208.

NIST (2024). Module-Lattice-Based Digital Signature Standard. FIPS 204.

NIST (2024). Stateless Hash-Based Digital Signature Standard. FIPS 205.

Shor, P. W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing, 26(5), 1484-1509.