| Post-quantum cryptography | |
|---|---|
| Name | Post-quantum cryptography |
| Type | Cryptographic research and engineering |
| Introduced | 1990s–2010s |
| Related | Cryptography, Quantum computing, Information security |
Post-quantum cryptography
Post-quantum cryptography (PQC) comprises cryptographic algorithms designed to resist attacks by adversaries equipped with quantum computers. It matters within the context of Quantum physics because the development of scalable quantum hardware and quantum algorithms such as Shor's algorithm threaten widely used public-key primitives, motivating research in quantum-resistant alternatives and standards to protect long-term confidentiality and integrity.
Post-quantum cryptography sits at the intersection of practical cryptography and experimental quantum mechanics research. While traditional cryptography relies on classical computational hardness (e.g., integer factorization and discrete logarithm problems used in RSA and ECC), PQC focuses on problems believed to remain hard even for quantum devices. The field is driven by advances at organizations and laboratories such as IBM Research, Google Quantum AI, IonQ, and Rigetti Computing, and by theoretical work from researchers at institutions like Massachusetts Institute of Technology, University of California, Berkeley, and University of Waterloo. PQC integrates insights from computational complexity theory and experimental milestones in quantum error correction and fault-tolerant quantum computing.
Quantum algorithms pose concrete threats: Shor's algorithm can efficiently factor integers and compute discrete logarithms on an error-corrected quantum computer, undermining RSA and ECC. Grover's algorithm provides a quadratic speedup for unstructured search, affecting symmetric-key security parameters. The timeline for practical breaks depends on hardware scaling, coherence times, and error rates achieved by platforms like superconducting quantum computers and trapped-ion quantum computers. Nation-state programs, academic initiatives, and corporate efforts—such as the National Quantum Initiative in the United States and programs at Chinese Academy of Sciences—accelerate progress, creating policy urgency. The concept of "harvest now, decrypt later" elevates the risk for long-lived data, archives, and critical infrastructure.
PQ cryptography includes several families of primitives based on diverse hardness assumptions. Major families include: - Lattice-based cryptography (e.g., Learning with Errors (LWE), Ring-LWE, NTRU) used by proposals from researchers like Oded Regev and implemented in candidates such as CRYSTALS-Kyber and CRYSTALS-Dilithium. - Code-based cryptography (e.g., McEliece cryptosystem) with roots in work by Robert McEliece. - Multivariate quadratic equations (e.g., MQ schemes) stemming from research by Joan Daemen and others in public-key signatures. - Hash-based signatures (e.g., Merkle signature scheme) relying on collision-resistant hashes and used for stateful or stateless signatures. - Isogeny-based cryptography (e.g., Supersingular Isogeny Diffie–Hellman (SIDH) and subsequent variants) originating in work by researchers such as David J. Bernstein and Tanja Lange.
Primitives target functions including key exchange, public-key encryption, and digital signatures. Research communities coordinate through venues like CRYPTO (conference), EUROCRYPT, and the IACR.
Standardization efforts are led by organizations such as National Institute of Standards and Technology (NIST), which ran a multi-round competition producing selected algorithms (e.g., CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, SPHINCS+). International standards bodies like the Internet Engineering Task Force (IETF) and ISO/IEC are developing protocols and interoperability guidelines. Deployment challenges include performance trade-offs on constrained devices (e.g., Internet of Things endpoints), key size increases, backward compatibility with TLS/HTTPS, and supply-chain impacts on vendors like Cisco Systems and cloud providers such as Amazon Web Services and Google Cloud Platform. Transitional complexity also arises from legacy systems, certificate lifecycles, and the need for hybrid schemes combining classical and post-quantum algorithms during migration.
Security analyses of PQC rely on reductions to worst-case or average-case hardness assumptions, often in the classical or quantum random oracle model. Proof techniques incorporate lattice problems (e.g., shortest vector problem), coding-theory hardness, and multivariate algebraic assumptions. Some proofs consider adversaries with quantum access to oracles—linking work in quantum information theory and cryptographic indistinguishability. Notable theoretical contributions include reductions by Miklos Ajtai and Oded Regev for lattice problems, and frameworks for composable security under quantum adversaries developed in academic centers such as Microsoft Research and QuTech. Open questions remain about the exact quantum hardness of many assumptions and the impact of future algorithmic breakthroughs.
Transitioning to PQC has broad socioeconomic implications: nations, corporations, and civil society must coordinate to protect sensitive data and critical infrastructure while avoiding inequitable burdens on low-resource regions. Cryptographic migration risks creating digital divides if small businesses, hospitals, and municipalities lack resources to update systems. International policy actors—United Nations, national cyber agencies, and standards groups—debate timelines, export controls, and intellectual property issues. Privacy advocates and human-rights organizations emphasize the need to safeguard activists and journalists from retrospective surveillance enabled by quantum decryption. Equitable deployment requires funding, open standards, capacity-building for universities and NGOs, and transparent governance to ensure that advances in quantum computing and post-quantum cryptography serve public-interest goals rather than concentrating power.
Category:Cryptography Category:Quantum computing Category:Information security