# Post-Quantum Cryptography ## The Quantum Threat Modern public-key cryptography relies heavily on two computational assumptions: - factoring large integers is hard, - discrete logarithms are hard. RSA depends on factoring. Diffie-Hellman and elliptic curve cryptography depend on discrete logarithms. Quantum computation changes this landscape dramatically. entity["people","Peter Shor","American mathematician"] discovered algorithms showing that sufficiently powerful quantum computers could solve both problems in polynomial time. A large fault-tolerant quantum computer would therefore break much of current public-key infrastructure. Post-quantum cryptography studies cryptographic systems believed to remain secure even against quantum attackers. ## Classical and Quantum Complexity A classical computer manipulates bits taking values $$ 0 \quad\text{or}\quad 1. $$ A quantum computer manipulates quantum states that may exist in superpositions. Quantum algorithms can exploit interference and entanglement to solve certain problems much faster than known classical algorithms. The most important cryptographic quantum algorithms are: | Algorithm | Threatened Problem | |---|---| | Shor’s algorithm | Factoring and discrete logarithms | | Grover’s algorithm | Symmetric brute-force search | Shor’s algorithm is devastating for classical public-key systems. Grover’s algorithm gives a weaker square-root speedup against brute-force attacks. ## Goals of Post-Quantum Cryptography A post-quantum cryptosystem should satisfy several requirements: 1. resistance to known quantum attacks, 2. practical efficiency, 3. implementability on existing hardware, 4. well-understood security assumptions, 5. robustness against side-channel attacks. Unlike quantum cryptography, post-quantum cryptography does not require quantum hardware. It uses ordinary digital systems with different mathematical foundations. ## Lattice-Based Cryptography Lattice-based cryptography is currently one of the leading post-quantum approaches. Its security relies on problems such as: - learning with errors, - short integer solution, - shortest vector problems. No efficient quantum algorithms are known for solving these problems in the parameter ranges used by practical systems. Lattice systems are attractive because they provide: - efficient encryption, - efficient signatures, - strong theoretical foundations, - advanced functionality. Modern schemes such as Kyber and Dilithium are based on module-lattice constructions. ## Code-Based Cryptography Code-based cryptography relies on error-correcting codes. The classical example is the McEliece cryptosystem. A public generator matrix hides the structure of a special error-correcting code. Encryption introduces random errors. Decryption succeeds because the private key reveals an efficient decoding algorithm. The security depends on the difficulty of decoding random linear codes. Code-based systems have resisted cryptanalysis for decades, including quantum attacks currently known. Their main drawback is large public keys. ## Hash-Based Signatures Hash-based cryptography builds signatures from cryptographic hash functions. The simplest constructions use Merkle trees and one-time signatures. Security depends primarily on properties such as: - collision resistance, - preimage resistance, - second-preimage resistance. Hash-based signatures are among the most conservative post-quantum constructions because they rely on assumptions already central to symmetric cryptography. However, state management and signature sizes can be challenging. ## Multivariate Cryptography Multivariate cryptography is based on systems of multivariate polynomial equations over finite fields. The general problem of solving such systems is computationally difficult. Public keys are polynomial maps, while private keys provide hidden structure allowing efficient inversion. Although multivariate systems were once considered highly promising, many proposed schemes have been broken through algebraic attacks. Nevertheless, the area remains an important research direction. ## Isogeny-Based Cryptography Some post-quantum systems use isogenies between elliptic curves. An isogeny is a morphism preserving elliptic curve group structure. The security assumption is that finding an isogeny between certain supersingular elliptic curves is difficult. Isogeny systems were attractive because they offered extremely small public keys. However, several major proposals were broken by new attacks. This demonstrated the importance of conservative security assumptions and extensive cryptanalysis. Despite these setbacks, isogeny theory remains mathematically important and continues to be studied. ## Symmetric Cryptography and Quantum Attacks Quantum attacks affect symmetric cryptography differently. Grover’s algorithm provides approximately a square-root speedup for exhaustive key search. This means that doubling key sizes usually restores security margins. For example: | Classical Key Size | Approximate Post-Grover Security | |---|---| | 128-bit | about 64-bit | | 256-bit | about 128-bit | Thus symmetric cryptography requires parameter adjustments rather than complete redesign. ## Hybrid Cryptography Many real systems are transitioning gradually toward post-quantum security using hybrid approaches. A hybrid protocol combines: - a classical scheme, - a post-quantum scheme. The session remains secure if at least one component remains secure. This reduces migration risk while standards and implementations mature. Hybrid deployment is already appearing in secure communication systems. ## Standardization Efforts Large-scale standardization efforts have accelerated post-quantum adoption. The entity["organization","National Institute of Standards and Technology","United States standards agency"] conducted a multi-year process evaluating candidate algorithms for post-quantum standardization. Selection criteria included: - security, - efficiency, - implementation simplicity, - resistance to side channels, - maturity of analysis. The process led to standardization of several lattice-based and hash-based schemes. ## Performance Tradeoffs Post-quantum systems often involve different engineering tradeoffs than classical cryptography. Examples include: | Property | Classical ECC | Lattice Systems | |---|---| | Key size | Small | Larger | | Signature size | Small | Moderate | | Arithmetic | Elliptic curves | Polynomial rings | | Quantum security | No | Expected yes | No post-quantum family dominates every category. Protocol designers must balance efficiency, security margins, bandwidth, and implementation complexity. ## Side-Channel Resistance Post-quantum security is not only about mathematics. Implementations must resist: - timing attacks, - power analysis, - cache attacks, - fault injection, - leakage through decryption failures. Some lattice systems are particularly sensitive to implementation errors because noise distributions and rejection sampling may leak information. Careful constant-time implementations are therefore essential. ## Long-Term Security Post-quantum cryptography matters especially for long-lived secrets. An attacker may record encrypted traffic today and decrypt it later once quantum computers become practical. This is called a harvest-now-decrypt-later attack. Sensitive data with long confidentiality requirements therefore motivates early migration toward quantum-resistant systems. ## Mathematical Diversity One important lesson of post-quantum research is the value of mathematical diversity. Classical public-key cryptography relied heavily on two closely related problems: - factoring, - discrete logarithms. Post-quantum cryptography instead explores many unrelated mathematical domains: - lattices, - coding theory, - hash constructions, - polynomial systems, - isogenies. This diversity reduces the risk of a single mathematical breakthrough destroying all public-key systems simultaneously. ## Conceptual Importance Post-quantum cryptography represents a major transition in the history of applied mathematics. For decades, public-key cryptography relied on arithmetic problems from classical number theory. Quantum algorithms forced a reexamination of those foundations. The result is a new cryptographic landscape built from: - high-dimensional geometry, - noisy algebra, - coding theory, - combinatorics, - advanced algebraic structures. This transition illustrates how changes in computational models can reshape the mathematical foundations of security itself.