What is Post-quantum cryptography?
Cryptography that bases its security on mathematical problems believed to be hard to solve efficiently even for quantum computers, such as lattice problems and hash functions. It runs on conventional computers and is used to replace RSA and elliptic-curve cryptography, which Shor's algorithm can break.
Japanese name: 耐量子計算機暗号
Post-quantum cryptography appears in 2 practice questions across 1 topic, including Quantum Computing Hardware.
Field: Quantum Computing Hardware
Why it is needed
RSA and elliptic-curve cryptography, which are widely used today, would be broken by Shor's algorithm on a large fault-tolerant quantum computer. Such quantum computers do not yet exist, but there is the risk of “harvest now, decrypt later”, in which ciphertext recorded today is decrypted in the future, and replacing cryptography takes many years. The migration therefore needs to begin before quantum computers arrive.
Main schemes and standards
In 2024 the US NIST published as standards the lattice-based key encapsulation mechanism ML-KEM (FIPS 203), the lattice-based signature scheme ML-DSA (FIPS 204) and the hash-based signature scheme SLH-DSA (FIPS 205). Their keys and signatures are larger than before: for example, an ML-KEM-768 public key is 1,184 bytes, far larger than the 32 bytes of the elliptic-curve key exchange X25519. An ML-DSA-65 signature is 3,309 bytes.
Hardware and migration
Because the keys and signatures are larger and the computations are different in nature, migration proceeds while checking the impact on embedded devices and smart cards with little memory, packet sizes in communication protocols and so on. Lattice-based schemes speed up polynomial multiplication with the number-theoretic transform (NTT), and acceleration with dedicated circuits is being studied. Implementations also need protection against side-channel attacks, which leak secrets through power consumption or timing. For now, migration proceeds step by step with hybrid schemes that combine conventional cryptography, and designs that make it easy to replace cryptography later (crypto agility) are emphasized.
FAQ
How does it differ from quantum key distribution (QKD)?
Post-quantum cryptography is based on the difficulty of mathematical problems and runs on ordinary computers and networks. Quantum key distribution shares keys using quantum properties of photons and the like and requires dedicated optical communication equipment. They are separate technologies, and post-quantum cryptography is at the center of the replacement effort.
Do symmetric-key ciphers such as AES need to be replaced too?
Against symmetric-key ciphers there is only the quadratic speed-up of Grover's algorithm, so it is thought that no change of scheme is needed and long enough keys are an adequate response. For example, AES-256 is considered to keep sufficient security even against quantum computers.