Shor's-algorithm threat to RSA/ECC, lattice-based Learning With Errors hardness, NIST FIPS 203/204 standardization, and "harvest now, decrypt later" migration for lifelong genomic data
Almost every piece of encrypted internet traffic, and every digital signature securing software updates and TLS certificates today, relies on the presumed classical hardness of integer factorization or the elliptic-curve discrete logarithm problem. Peter Shor's 1994 algorithm shows that a sufficiently large, fault-tolerant quantum computer solves both in polynomial time — converting a problem that would take classical computers longer than the age of the universe into one solvable in hours to days.
The mathematical target: • RSA security rests on integer factorization: given a large composite number N = p×q (p, q large primes), recovering p and q is classically believed to require sub-exponential time — the best classical method, the General Number Field Sieve (GNFS), takes roughly 10^9 years for RSA-2048 using all known computing resources • Diffie-Hellman key exchange and ECC (elliptic-curve cryptography, used in ECDSA signatures and ECDH key exchange) rest on the discrete logarithm problem — in a multiplicative group or on an elliptic curve, respectively — with similarly steep classical hardness
Shor's algorithm (1994): • Reformulates factoring as period-finding: N can be factored efficiently once the period of a particular modular exponentiation function is known • A quantum computer finds this period efficiently via the quantum Fourier transform, exploiting superposition to evaluate the function at exponentially many points simultaneously — something with no classical analogue • Runs in polynomial time (specifically O((log N)³) gate complexity in early formulations, improved further since) — converting a problem exponential for classical computers into one tractable for a large quantum computer • An analogous quantum period-finding approach breaks the discrete-logarithm problem underlying Diffie-Hellman and ECC equally efficiently — ECC is NOT a safe fallback from RSA against a quantum adversary; both fall to the same algorithmic family
Current hardware vs. requirement: • Gidney & Ekerå (2021, Quantum journal) estimated that breaking RSA-2048 would require roughly 20 million noisy physical qubits (surface-code error-corrected) running for about 8 hours — a dramatic reduction from earlier estimates in the billions, again illustrating how fast resource estimates fall with better algorithms • As of 2024–2026, the largest quantum processors (IBM, Google, IonQ, Quantinuum) have hundreds to a little over a thousand physical qubits and have only recently demonstrated the basic building blocks of error correction at small scale — meaning a cryptographically relevant quantum computer (CRQC) capable of running Shor's algorithm against RSA-2048 does not yet exist, with most expert timelines (RAND, NIST NCCoE, various national agencies) projecting a plausible arrival window sometime in the 2030s, with significant uncertainty in both directions
A cryptographically relevant quantum computer does not need to exist today for today's encryption to be at risk — an adversary only needs to intercept and store ciphertext now, and wait. This "harvest now, decrypt later" (HNDL) threat model reframes the urgency of post-quantum migration: it is not about protecting data from a threat that exists today, but about protecting data whose confidentiality requirement will still be active on the day a quantum computer capable of breaking it finally arrives.
The HNDL threat model in plain terms: • Nation-state and well-resourced adversaries are widely assessed (per US NSA, NIST, and allied cybersecurity agency guidance) to already be systematically collecting and archiving high-value encrypted traffic today, explicitly betting on future quantum decryption capability • For most data types, this is a manageable risk: a credit card number expires, a password can be rotated, a business contract's sensitivity often fades within years — by the time a quantum computer could decrypt archived 2026 ciphertext (plausibly the 2030s–2040s), much of the harvested data has lost its value
Why a genome breaks this "it'll be stale by then" assumption: • A human genome sequence is a lifetime-constant secret — it does not change, cannot be reissued, and remains medically and personally relevant for the entire lifespan of the individual, which for a person sequenced today may extend 60-80+ years into the future — squarely inside, or beyond, most quantum-threat timelines • Genomic data is inherently familial: an individual's genome reveals substantial information about their parents, siblings, and children (shared variants, disease-risk alleles, ancestry) — meaning a single harvested genome has decades-to-generations of downstream exposure for people who never separately consented • Re-identification risk is unusually severe and durable: genomic data, even when nominally "de-identified" in a research dataset, has been repeatedly demonstrated (Gymrek et al., Science 2013, using surname inference from Y-chromosome markers plus public genealogy databases) to be re-identifiable years after collection — meaning decrypted genomic data does not merely reveal old information, it can be actively weaponized for individual re-identification long after collection • Unlike a password or credit card, a genome offers no remediation path after exposure: there is no way to "reset" one's DNA — making the confidentiality failure permanent and irreversible in a way few other data categories share
Practical implication for genomic data custodians: • Any genomic data encrypted TODAY with only classical (RSA/ECC) protection, and transmitted or stored where interception is plausible, should be treated as already at risk of future decryption — meaning migration urgency is driven by the DATA'S sensitivity horizon, not by how soon a quantum computer is expected, since data encrypted years before a CRQC exists is exactly what HNDL targets
Replacing factoring and discrete logarithms requires a mathematical problem that is hard for BOTH classical and quantum computers. Lattice-based cryptography, and specifically the Learning With Errors (LWE) problem introduced by Oded Regev in 2005, has emerged as the leading foundation: LWE's hardness reduces to worst-case lattice problems for which, despite decades of dedicated cryptanalysis including quantum algorithm research, no efficient quantum algorithm is known.
What a lattice is: • A lattice is the set of all integer linear combinations of a set of basis vectors in n-dimensional space — an infinite, regularly repeating grid of points • Two classic hard problems on lattices: the Shortest Vector Problem (SVP — find the shortest nonzero vector in the lattice) and the Closest Vector Problem (CVP — given an arbitrary point, find the nearest lattice point) — both believed to require time exponential in the lattice dimension n for the best known algorithms, classical or quantum
The Learning With Errors (LWE) problem: • Given many noisy linear equations of the form: b_i = ⟨a_i, s⟩ + e_i (mod q), where a_i are known random vectors, s is a fixed secret vector, and e_i is small random "error" noise — recover the secret s • Without the error terms e_i, this is trivial linear algebra (solvable instantly by Gaussian elimination); the small random noise is precisely what makes recovering s computationally hard — analogous to trying to solve a system of equations where each equation has been slightly, randomly perturbed • Regev (2005) proved a worst-case-to-average-case REDUCTION: solving a randomly-sampled LWE instance is provably at least as hard as solving certain lattice problems (like a variant of SVP) in the WORST case — an unusually strong theoretical guarantee, since most classical cryptographic assumptions (like factoring) only have average-case hardness evidence, not worst-case reductions
Why LWE resists quantum attack specifically: • Shor's algorithm exploits deep ALGEBRAIC structure — periodicity — in factoring and discrete logarithms, structure that the quantum Fourier transform can detect efficiently • Lattice problems, despite over two decades of dedicated attack research (including quantum algorithm attempts), have not been shown to contain analogous exploitable algebraic structure — the best known quantum attacks on lattice problems (quantum-enhanced sieving algorithms) offer only modest polynomial speedups over classical lattice-reduction attacks (like the BKZ algorithm), not the exponential-to-polynomial collapse Shor's algorithm achieves against factoring
Structured variants for efficiency — Ring-LWE and Module-LWE: • Plain LWE requires large key sizes for adequate security; Ring-LWE (Lyubashevsky, Peikert, Regev 2010) and Module-LWE work over polynomial rings with algebraic structure that dramatically shrinks key and ciphertext sizes while preserving (with some additional, still-unbroken, structural assumptions) the underlying hardness • CRYSTALS-Kyber (Stage 4) uses Module-LWE specifically because it offers a tunable security/efficiency tradeoff via the module rank, without requiring the full unstructured-LWE key sizes
NIST launched its Post-Quantum Cryptography Standardization competition in 2016, soliciting and publicly evaluating submissions across multiple rounds of open cryptanalysis by the global research community. In August 2024, after eight years of scrutiny, NIST published the first three finalized standards — a milestone comparable in significance to the original AES and SHA competitions, and the formal starting gun for organization-wide migration planning.
ML-KEM / CRYSTALS-Kyber (FIPS 203) — key encapsulation: • Used wherever RSA or ECDH is used today for establishing a shared symmetric key over an untrusted channel (TLS handshakes, VPNs, secure messaging) • Based on Module-LWE; three parameter sets — Kyber-512, Kyber-768, Kyber-1024 — corresponding roughly to AES-128, AES-192, and AES-256 equivalent security • Kyber-768 (the commonly recommended default): public key 1,184 bytes, ciphertext 1,088 bytes — larger than a comparable ECC public key (~32-64 bytes) but small enough for practical TLS and VPN deployment • Selected as NIST's primary KEM in July 2022 (Round 3 announcement) for its strong balance of security confidence, small-ish key sizes, and fast implementation on both general CPUs and constrained hardware
ML-DSA / CRYSTALS-Dilithium (FIPS 204) — digital signatures: • Used wherever RSA-PSS or ECDSA is used today: code signing, TLS certificate signatures, document signing • Also lattice-based (Module-LWE and Module-SIS hardness combined); Dilithium2/3/5 parameter sets scale security level • Dilithium3 (common default): public key 1,952 bytes, signature 3,293 bytes — notably larger than ECDSA's ~64-byte signatures, a real bandwidth/storage cost that migration planning must budget for
SLH-DSA / SPHINCS+ (FIPS 205) — hash-based signature backup: • Deliberately based on an entirely DIFFERENT hardness assumption — the security of cryptographic hash functions — rather than lattices • Rationale: if an unforeseen cryptanalytic advance were ever found against lattice problems (undermining Kyber/Dilithium simultaneously, since both share the same mathematical foundation), SPHINCS+ provides an algorithmically independent fallback that would remain secure • Tradeoff: much larger signatures (tens of KB) and slower signing than Dilithium, so used more selectively — root-of-trust and firmware-signing scenarios where long-term algorithmic diversity outweighs the size cost
Why having two DIFFERENT hard-problem families standardized matters: • Cryptographic history includes real instances of algorithms believed secure being broken decades later (e.g., early elliptic-curve parameter choices, various hash function collisions) — NIST's explicit inclusion of a non-lattice-based backup (SPHINCS+) reflects lessons learned about not placing all post-quantum trust in a single mathematical assumption, however well-studied
Standardization is necessary but not sufficient — genomic data custodians (sequencing cores, biobanks, hospital genomics divisions, direct-to-consumer testing companies) must actually re-architect storage encryption, transmission protocols, and long-term archival key management. Given the HNDL threat from Stage 2, the practical migration strategy for most organizations today is hybrid deployment: combine a classical algorithm with a post-quantum algorithm so that breaking either alone is insufficient to compromise the data.
NIST IR 8547 (2024) — the formal deprecation schedule: • RSA and ECC (at the commonly used 112-bit-equivalent security levels, e.g. RSA-2048, ECC P-256) are to be DEPRECATED (discouraged, requiring risk justification to continue using) starting 2030 • The same algorithms are to be DISALLOWED entirely (prohibited in NIST-governed systems, including most US federal and federally-adjacent healthcare infrastructure via downstream compliance requirements) starting 2035 • This timeline is explicitly informed by HNDL reasoning: waiting until a cryptographically relevant quantum computer actually exists before migrating is, by definition, too late for any data that needed longer-than-that-wait confidentiality — genomic data being the paradigm case
Hybrid deployment as the practical interim architecture: • A hybrid key-establishment scheme combines a classical algorithm (e.g., X25519 elliptic-curve Diffie-Hellman) with a post-quantum KEM (ML-KEM/Kyber) — the final shared secret is derived from BOTH, typically via a key-derivation function combining both outputs • Security property: an adversary must break BOTH the classical AND the post-quantum component to recover the shared secret — protecting against the (currently more mature, more analyzed) classical algorithm being catastrophically broken by an implementation flaw, while also protecting against a hypothetical future weakness discovered in the newer, less battle-tested lattice-based algorithm • This hedge matters because ML-KEM, despite passing NIST's multi-round public cryptanalysis process, has had less real-world deployment scrutiny than RSA/ECC, which have withstood several decades of continuous attack — hybrid deployment lets organizations gain HNDL protection today without betting entirely on an algorithm family with a shorter track record
Applying this to genomic data infrastructure specifically: 1. Data in transit: sequencing instrument-to-cloud uploads, inter-institutional genomic data sharing (e.g., GA4GH-compliant federated genomic data networks), and researcher API access should move to hybrid TLS 1.3 configurations (already supported by major browsers and server stacks as of 2024-2026) as the near-term priority, since this data is most exposed to network-level HNDL interception 2. Data at rest: long-term archival storage of raw sequencing files (FASTQ), aligned reads (BAM/CRAM), and variant calls (VCF) — often retained for decades per biobank consent agreements and regulatory requirements — needs symmetric-key encryption (AES-256, itself only quadratically weakened by Grover's quantum algorithm and not considered urgently at risk) combined with PQC-protected key-wrapping for the keys themselves, since the KEY EXCHANGE and KEY STORAGE mechanisms, not the symmetric cipher, are what Shor's algorithm actually threatens 3. Digital signatures on genomic records: chain-of-custody signatures, consent attestations, and data-provenance signing (important for CLIA/CAP-regulated clinical genomic reporting) should migrate to ML-DSA/Dilithium or a hybrid classical+PQC signature scheme on the same 2030 deprecation timeline 4. Crypto-agility as an architectural requirement: given that lattice-based algorithms are newer and standardization is likely to continue evolving (parameter updates, potential future algorithm additions), genomic data systems should be built with replaceable cryptographic modules rather than hard-coded algorithm choices — allowing future algorithm swaps without re-architecting the entire data pipeline
Because a genome sequenced today may need to remain confidential for 80+ years — spanning both the individual's lifetime and their descendants' — genomic data custodians face one of the most urgent post-quantum migration timelines of any data category: under the "harvest now, decrypt later" threat model, genomic data encrypted with classical-only algorithms today should already be considered at risk, regardless of how many years remain before a cryptographically relevant quantum computer is built.