Post-Quantum Cryptography
Post-quantum cryptography replaces RSA and ECC with lattice-based algorithms secure against classical and quantum attack
Source: mortalapps.com- Post-Quantum Cryptography (PQC) consists of classical algorithms secure against both classical and quantum attacks.
- Shor's algorithm threatens RSA and ECC, while Grover's algorithm merely requires doubling symmetric key sizes (e.g., AES-256).
- Lattice-based cryptography, such as the Learning With Errors (LWE) problem, forms the foundation of modern PQC.
- NIST finalized its first official PQC standards in August 2024: ML-KEM (FIPS 203, encryption), ML-DSA (FIPS 204, signatures), SLH-DSA (FIPS 205, hash-based signatures), and FN-DSA (FIPS 206, NTRU-lattice signatures).
- The 'Harvest Now, Decrypt Later' threat makes migrating to PQC an urgent priority today.
- Mosca's Theorem states that we must migrate before the time to build a quantum computer is less than our data security shelf-life plus migration time.
Why This Matters
While quantum cryptography uses quantum hardware to secure communications, Post-Quantum Cryptography (PQC) takes a different approach. PQC refers to classical mathematical algorithms designed to secure our existing digital infrastructure against attacks by future quantum computers. These algorithms run on standard classical hardware (like your phone or laptop) but rely on mathematical problems that are incredibly difficult for both classical and quantum computers to solve.
Core Intuition
To understand the difference, imagine you want to protect a treasure chest. Quantum cryptography (QKD) is like building a magical chest that vanishes if anyone other than the owner touches it. It is incredibly secure, but you need to buy a completely new, expensive chest and transport system.
Post-Quantum Cryptography (PQC) is like replacing the standard lock on your existing wooden chest with a highly complex, multi-dimensional combination lock. The chest is still classical, but the lock is based on a maze so complex that even a quantum computer, with all its parallel processing power, cannot find the way through. This allows you to keep using your existing chests and transport routes while upgrading your security.
Visualization
Technical Explanation
The primary threat to modern cryptography is Shor's algorithm, which can factor large integers and solve discrete logarithms in polynomial time, breaking RSA and Elliptic Curve Cryptography (ECC). PQC replaces these vulnerable systems with algorithms based on different mathematical structures, most notably lattice-based cryptography.
Lattice-based cryptography relies on the hardness of high-dimensional geometric problems, such as the Shortest Vector Problem (SVP) or the Learning With Errors (LWE) problem. In LWE, we are given a set of linear equations with a small amount of added noise. For a secret vector $s$ and a public matrix $a$, we compute:
$$b = s \cdot a + e \pmod q$$
where $e$ is a small error vector. Finding $s$ given $a$ and $b$ is extremely difficult because the added noise prevents standard Gaussian elimination. While a quantum computer can easily solve structured algebraic problems like factoring, it has no known advantage for solving these noisy, high-dimensional geometric lattice problems.
In 2024, the National Institute of Standards and Technology (NIST) finalized its first set of post-quantum cryptographic standards. These include CRYSTALS-Kyber (now standardized as ML-KEM) for general encryption, and CRYSTALS-Dilithium (ML-DSA) and SPHINCS+ for digital signatures. Transitioning the global internet to these standards is an urgent priority due to the 'Harvest Now, Decrypt Later' threat, where adversaries intercept and store encrypted data today, waiting to decrypt it once they possess a sufficiently powerful quantum computer.