Post-Quantum Cryptography

Post-quantum cryptography develops public-key schemes whose security rests on problems believed hard even for quantum computers, replacing RSA and elliptic-curve cryptography that Shor's algorithm would break.

Definition

Post-quantum cryptography comprises classical (non-quantum) cryptographic algorithms designed to remain secure against adversaries equipped with large-scale quantum computers, by relying on problems for which no efficient quantum algorithm is known.

Scope

This topic covers the quantum threat (Shor's and Grover's algorithms), the main families of quantum-resistant schemes — lattice-based, code-based, hash-based, and multivariate — the NIST standardization effort and its selected algorithms (ML-KEM, ML-DSA, SLH-DSA), and migration concerns such as 'harvest-now-decrypt-later' and hybrid deployment. It excludes quantum cryptography proper (quantum key distribution), which uses quantum hardware rather than classical algorithms.

Core questions

• Why do quantum computers break RSA and elliptic-curve cryptography but not symmetric ciphers as severely?
• What hard problems (lattices, codes, hashes) are believed to resist quantum attack?
• What schemes did NIST select for standardization, and what are their trade-offs?
• What is the 'harvest-now-decrypt-later' threat and why does it create urgency?
• How are post-quantum and classical schemes combined in hybrid deployments during migration?

Key concepts

• Shor's algorithm
• Grover's algorithm
• lattice-based cryptography (learning with errors)
• code-based cryptography
• hash-based signatures
• ML-KEM (Kyber) and ML-DSA (Dilithium)
• harvest-now-decrypt-later
• crypto-agility
• hybrid key exchange

Key theories

The quantum threat from Shor's algorithm

Shor's quantum algorithm factors integers and computes discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and elliptic-curve cryptography; Grover's algorithm only quadratically speeds up brute force, so symmetric keys need merely be doubled.

Quantum-hard problem families

Post-quantum security is sought in problems such as learning-with-errors and shortest-vector problems in lattices, decoding random linear codes, and the security of hash functions — none of which have known efficient quantum algorithms.

Mechanisms

Lattice schemes such as ML-KEM (derived from CRYSTALS-Kyber) base key encapsulation on the hardness of the module learning-with-errors problem, adding small random 'errors' that only the private key can remove. Hash-based signatures (SLH-DSA/SPHINCS+) build signatures solely from the security of a hash function. Code-based schemes hide a decodable structure in a random-looking linear code. Migration typically uses hybrid constructions that combine a classical and a post-quantum scheme so security holds if either survives.

Clinical relevance

The migration is already underway in deployed systems: major browsers and TLS libraries have enabled hybrid ML-KEM key exchange, messaging apps (Signal's PQXDH) and SSH have added post-quantum handshakes, and standards bodies urge organizations to inventory cryptography and plan transitions. The 'harvest-now-decrypt-later' risk means data needing long-term confidentiality should be protected against quantum attack today.

Evidence & guidelines

NIST finalized its first post-quantum standards in 2024: FIPS 203 (ML-KEM) for key encapsulation, FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures. Guidance from NIST, NSA (CNSA 2.0), and national agencies sets migration timelines. Best practice during transition favors hybrid schemes combining post-quantum and classical algorithms.

History

Peter Shor's 1994 algorithm showed quantum computers could break the dominant public-key systems, motivating the search for alternatives. Lattice-based cryptography advanced through Ajtai's worst-case hardness results and Regev's learning-with-errors problem (2005). NIST launched a public standardization process in 2016; after multiple rounds it selected CRYSTALS-Kyber and others, publishing the first standards (FIPS 203-205) in 2024.

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

Do quantum computers already exist that can break RSA?

No. Current quantum computers are far too small and noisy to run Shor's algorithm on real-world key sizes. The concern is future machines, combined with the fact that data encrypted today could be stored and decrypted once such machines exist.

Does post-quantum cryptography require quantum hardware?

No. Post-quantum schemes run on ordinary classical computers; they simply rely on math problems believed hard even for quantum attackers. Quantum key distribution, which does use quantum hardware, is a separate approach.