Simple Algorithm
Quantum Computing · Rydberg State · 24 min

Post-Quantum vs Quantum Cryptography

Two very different answers to the quantum threat.

A large fault-tolerant quantum computer would break RSA and elliptic-curve cryptography, which protect almost all key exchanges and digital signatures on the internet. There are two answers. Post-quantum cryptography keeps the classical model and replaces the math with problems no known quantum algorithm solves; quantum key distribution replaces the math with physics. This lesson compares them precisely: the threat model, the lattice math behind the 2024 NIST standards, and what each approach can and cannot guarantee.

What you’ll learn

  • Classify which primitives Shor's and Grover's algorithms break or weaken, and apply Mosca's inequality to harvest-now-decrypt-later risk.
  • Define LWE, state Regev's worst-case hardness theorem, and derive the correctness of Kyber-style encryption.
  • Describe the NIST standards ML-KEM (FIPS 203), ML-DSA (FIPS 204) and SLH-DSA (FIPS 205), their assumptions and costs.
  • Compare QKD and PQC on security basis, infrastructure, authentication and failure modes, and explain how they can be combined.

The quantum threat, precisely

PrimitiveRelies onBest known quantum attackStatus
RSA, finite-field Diffie–Hellman, DSAFactoring, discrete log in Zp∗\Z_p^*Shor: polynomial timeBroken by a large fault-tolerant quantum computer
ECDH, ECDSA, EdDSAElliptic-curve discrete logShor: polynomial time, fewer qubits than RSA at equal classical securityBroken likewise
AES-128 / AES-256No known structureGrover: about 2642^{64} / 21282^{128} sequential iterationsWeakened; AES-256 comfortably safe
SHA-2, SHA-3Preimage and collision resistanceGrover for preimages; no practical gain for collisionsSafe with standard output sizes
Grover parallelizes poorly: with pp machines the run time falls only as N/p\sqrt{N/p}, so its practical impact on symmetric cryptography is far smaller than the headline "halves the key length" suggests.

No cryptographically relevant quantum computer (CRQC) exists as of the mid-2020s, and estimates of when one might are uncertain. But estimates of what one would need have fallen fast: Gidney & Ekerå (2019) estimated that RSA-2048 could be factored in about eight hours with 20 million noisy physical qubits, and Gidney (2025) revised this to under a million qubits running for less than a week, assuming surface-code error correction at physical error rates around 10−310^{-3}.

The threat to confidentiality is already present: an adversary can record encrypted traffic today and decrypt it once a CRQC exists. This is harvest now, decrypt later.

Predict before you look

Health records must stay confidential for x=15x=15 years, the migration takes y=5y=5 years, and suppose a CRQC appears in z=12z=12 years. For how many years would some of these records be exposed, x+y−zx+y-z?

Show the answer

8 years

15+5−12=815+5-12=8. Records encrypted with quantum-vulnerable key exchange just before the migration completes (year 5) must stay secret until year 20, but could be decrypted from year 12 onward. Because zz is uncertain and xx is fixed by the data, long-lived secrets drive the urgency.

Lattices: hard problems Shor does not touch

Post-quantum cryptography (PQC) is classical cryptography built on problems believed hard even for quantum computers: lattices, error-correcting codes, hash functions, multivariate polynomial systems and isogenies. The workhorse is learning with errors.

DerivationWhy Kyber-style decryption works
  1. pk=(A, t=As+e),sk=s,A∈Rqk×k,  s,e small\text{pk}=(A,\ t=As+e),\qquad \text{sk}=s,\qquad A\in R_q^{k\times k},\ \ s,e\ \text{small}

    Work in the ring Rq=Zq[X]/(X256+1)R_q=\Z_q[X]/(X^{256}+1) ("module" LWE). ML-KEM uses q=3329q=3329 and module rank k=2,3,4k=2,3,4 for its three security levels.

  2. u=ATr+e1,v=tTr+e2+⌈q2⌋mu=A^{\mathsf T}r+e_1,\qquad v=t^{\mathsf T}r+e_2+\left\lceil\tfrac q2\right\rfloor m

    To encrypt a 256-bit message mm (one bit per coefficient), sample small r,e1,e2r,e_1,e_2.

  3. v−sTu=eTr+e2−sTe1+⌈q2⌋mv-s^{\mathsf T}u=e^{\mathsf T}r+e_2-s^{\mathsf T}e_1+\left\lceil\tfrac q2\right\rfloor m

    The terms sTATrs^{\mathsf T}A^{\mathsf T}r and (As)Tr(As)^{\mathsf T}r cancel exactly. What remains is the message plus a noise term w=eTr+e2−sTe1w=e^{\mathsf T}r+e_2-s^{\mathsf T}e_1 built from products of small polynomials.

  4. ∥w∥∞<q4 ⟹ m=round each coefficient to 0 or ⌈q2⌋\norm{w}_\infty<\tfrac q4\ \Longrightarrow\ m=\text{round each coefficient to } 0 \text{ or } \left\lceil\tfrac q2\right\rfloor

    Parameters are chosen so that decryption fails with probability below about 2−1382^{-138}. Security: (u,v)(u,v) looks uniform under decision-MLWE. The Fujisaki–Okamoto transform upgrades this CPA-secure scheme to the CCA-secure KEM standardized as ML-KEM.

Think first Shor's algorithm breaks factoring and discrete logs by finding a hidden period. Why doesn't the same idea break LWE?

Shor solves hidden subgroup problems over abelian groups. Lattice problems connect instead to the dihedral hidden subgroup problem (Regev, 2004), for which the best known quantum algorithm (Kuperberg, 2005) is subexponential, not polynomial, and does not yield an efficient lattice attack. Known quantum speedups for lattice reduction only improve the constant in the exponent of sieving algorithms. None of this is a proof: in April 2024 a preprint claimed a polynomial-time quantum algorithm for LWE in a parameter regime far from the standardized one, and a bug was found within about ten days.

The NIST standards

NIST opened a public competition in 2016 and received 82 submissions by the 2017 deadline. After three rounds of cryptanalysis it selected Kyber, Dilithium, Falcon and SPHINCS+ in July 2022, and in August 2024 published the first three standards. In March 2025 NIST also selected the code-based KEM HQC as a backup to ML-KEM, so that not all key establishment rests on lattices.

The competition was a lesson in humility: two promising candidates collapsed to classical attacks in 2022. The isogeny-based SIKE was broken in about an hour on a single core (Castryck & Decru), and the multivariate signature Rainbow "over a weekend on a laptop" (Beullens).

StandardFromAssumptionTypical sizes (bytes)Role
ML-KEM (FIPS 203)CRYSTALS-KyberModule-LWEML-KEM-768: public key 1184, ciphertext 1088Key encapsulation (key exchange)
ML-DSA (FIPS 204)CRYSTALS-DilithiumModule-LWE and Module-SISML-DSA-65: public key 1952, signature 3309General-purpose signatures
SLH-DSA (FIPS 205)SPHINCS+Security of hash functions onlypublic key 32–64, signature ≈ 7,900–50,000Conservative, stateless signatures
FN-DSA (planned FIPS 206)FalconNTRU latticesFalcon-512: public key 897, signature ≈ 666Compact signatures; tricky floating-point implementation
HQC (selected 2025)HQCDecoding quasi-cyclic codesa few thousandBackup KEM with a non-lattice assumption
For comparison: an X25519 public key is 32 bytes, an ECDSA P-256 signature 64 bytes and an RSA-2048 signature 256 bytes. PQC is fast, often faster than RSA, but bigger on the wire.
Check your understanding

A firmware-signing key must remain trustworthy for 30 years; signature size and signing speed hardly matter. Which standard is the most conservative choice?

  1. ML-KEM, since it is the primary NIST standard
  2. RSA-4096, since a longer key resists Shor's algorithm
  3. SLH-DSA, since its security rests only on properties of hash functions
  4. ML-DSA, since lattices have worst-case hardness reductions
Show the answer

C. SLH-DSA, since its security rests only on properties of hash functions

Hash-based signatures need no algebraic structure beyond a secure hash, the most battle-tested assumption in cryptography; their cost is large signatures, irrelevant here. ML-DSA is a fine general choice, but its assumption is newer.

QKD or PQC?

DimensionPost-quantum cryptographyQuantum key distribution
Security basisComputational; conjectured hardness of lattice, code or hash problemsInformation-theoretic, given the device model, quantum theory and authentication
Future breakthroughsRecorded traffic is exposed if the assumption fallsKeys stay secret ("everlasting") once the session ends unbroken
What it providesKey exchange and signatures, end to endKey growth only; authentication must come from elsewhere
InfrastructureSoftware update over existing networksDedicated fiber or free-space links, single-photon hardware
ReachGlobal, any networkPoint to point, roughly 100 km scale in fiber for practical rates; longer via trusted nodes or satellites
Typical failure modesCryptanalysis, side channels (e.g. timing leaks)Implementation attacks, trusted-node compromise, denial of service by cutting the link

The two are not simply rivals. QKD needs authentication, and authenticating it with post-quantum signatures creates a useful asymmetry: the signature only has to resist forgery during the session. If the signature scheme is broken years later, previously established QKD keys remain secret. PQC alone cannot offer that, since a later break exposes every recorded handshake.

In the other direction, QKD's guarantees hold only for links where its hardware can be deployed and trusted, and trusted relay nodes, used today for long distances, see every key in the clear. National security agencies, including the NSA, the UK's NCSC and several European agencies, have therefore recommended PQC as the primary migration path and regard QKD as a niche technology for specific high-value links.

Key takeaways

  • Shor breaks RSA, finite-field DH and elliptic-curve cryptography; Grover only weakens symmetric primitives. Harvest-now-decrypt-later makes key exchange the urgent case (Mosca: worry if x+y>zx+y>z).
  • LWE: recover ss from (A,As+e)(A,As+e). Regev reduced worst-case lattice problems to it (quantumly), and no known quantum algorithm solves it efficiently.
  • NIST published ML-KEM (FIPS 203), ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) in August 2024; FN-DSA and the code-based backup KEM HQC follow. Deployments use hybrids and crypto-agility.
  • PQC is software-deployable and provides signatures but rests on conjectures; QKD offers everlasting, information-theoretic key secrecy but needs special hardware, short links and separate authentication. Combined, PQ-authenticated QKD keys survive a later break of the signature scheme.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which system most urgently needs a migration to post-quantum cryptography because of harvest-now-decrypt-later?

  1. Signatures on web-server certificates that expire within a year
  2. Backups encrypted with AES-256 under a key that never leaves the data center
  3. TLS sessions whose key exchange uses ECDH and which carry medical records that must stay confidential for decades
  4. Password hashes stored with a modern memory-hard function
Show the answer

C. TLS sessions whose key exchange uses ECDH and which carry medical records that must stay confidential for decades

Recorded ECDH handshakes can be broken retroactively by a future CRQC, revealing the session keys and hence the long-lived data. Short-lived signatures must only resist forgery now, and symmetric primitives with 256-bit keys are not threatened by Shor.

Question 2

Why is AES-256 considered quantum-safe even though Grover's algorithm speeds up key search?

  1. Grover still needs about 21282^{128} sequential quantum iterations, and parallelization helps only as the square root of the number of machines
  2. Grover's algorithm does not apply to block ciphers
  3. AES-256 is based on a lattice problem
  4. Quantum computers cannot evaluate AES
Show the answer

A. Grover still needs about 21282^{128} sequential quantum iterations, and parallelization helps only as the square root of the number of machines

Grover gives a quadratic speedup, 2256→21282^{256}\to2^{128} evaluations, which remains far out of reach. Splitting the search across pp machines cuts the time only by p\sqrt p.

Question 3

A QKD link is authenticated with ML-DSA signatures. Twenty years from now ML-DSA is broken. What happens to keys established today?

  1. They are exposed, because the authentication transcript can be replayed
  2. They are exposed, because QKD keys are derived from the signatures
  3. Nothing changes, but only if the quantum channel was free of noise
  4. They remain secret: authentication only had to resist forgery during the session, and the key itself is information-theoretically secure
Show the answer

D. They remain secret: authentication only had to resist forgery during the session, and the key itself is information-theoretically secure

An attacker who breaks the signature scheme later cannot go back and impersonate Alice or Bob in a session that is already over. This "everlasting security" is something purely computational key exchange cannot provide.

Question 4

In Kyber-style decryption, v−sTu=⌈q/2⌋m+wv-s^{\mathsf T}u=\lceil q/2\rfloor m+w. What guarantees that mm is recovered correctly?

  1. The secret ss is uniformly random modulo qq
  2. Every coefficient of the noise w=eTr+e2−sTe1w=e^{\mathsf T}r+e_2-s^{\mathsf T}e_1 is smaller than q/4q/4 in absolute value
  3. The modulus qq is prime
  4. The matrix AA is invertible
Show the answer

B. Every coefficient of the noise w=eTr+e2−sTe1w=e^{\mathsf T}r+e_2-s^{\mathsf T}e_1 is smaller than q/4q/4 in absolute value

Rounding each coefficient to the nearer of 00 and ⌈q/2⌋\lceil q/2\rfloor recovers the bit whenever the noise stays below q/4q/4. Because s,e,r,e1,e2s,e,r,e_1,e_2 are all small, ww is small except with negligible probability.

Further reading

  • NIST, FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard; FIPS 204: Module-Lattice-Based Digital Signature Standard; FIPS 205: Stateless Hash-Based Digital Signature Standard (August 2024).
  • O. Regev, "On lattices, learning with errors, random linear codes, and cryptography", Journal of the ACM 56(6), 34 (2009); conference version STOC 2005.
  • D. J. Bernstein & T. Lange, "Post-quantum cryptography", Nature 549, 188 (2017).
  • M. Mosca, "Cybersecurity in an era with quantum computers: will we be ready?", IEEE Security & Privacy 16(5), 38 (2018).
  • C. Gidney & M. Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, 433 (2021).