Post-Quantum Cryptography Explained: Shor’s Algorithm, Lattices, and the Race to Secure the Internet
Post-quantum cryptography replaces classical public-key systems—broken by Shor's algorithm—with lattice-based math that runs on ordinary hardware. Symmetric encryption needs only a key-size upgrade to AES-256. Governments are migrating now because adversaries harvest encrypted data today to decrypt it once quantum hardware matures.
Post-quantum cryptography is the field of designing encryption algorithms that resist attacks from both classical and quantum computers. It matters right now—not in some distant sci-fi future—because adversaries are already collecting encrypted data today, banking on breaking it once quantum hardware catches up. This article walks through how the threat works, which algorithms survive, and what “crypto-agility” actually means in practice.
What Does Post-Quantum Cryptography Actually Protect Against?
Post-quantum cryptography protects the three core jobs of modern encryption—confidentiality, key establishment, and digital signatures—against an attacker wielding a large-scale quantum computer. Each job relies on a different mathematical puzzle, so the quantum threat hits each one differently, and the defence for each is different too.
Think of confidentiality as a locked box keeping data hidden. Key establishment lets two distant devices agree on the key to open that box without ever meeting in person. Digital signatures work like a tamper-evident wax seal: they prove who sent a message and confirm it was not altered in transit.
Because these three functions rest on different mathematical foundations, a quantum computer does not threaten them all equally. That distinction is the heart of the whole migration problem.
Why Is the Deadline Not Tied to When a Quantum Computer Gets Built?
The real deadline for post-quantum cryptography migration is set by the lifespan of secrets—not by the date quantum hardware becomes capable. Adversaries are already running a strategy called Harvest Now, Decrypt Later: they sweep up large volumes of encrypted traffic today and store it, planning to decrypt it once a sufficiently powerful quantum machine exists.
State secrets, military intelligence, and long-term financial records captured now could be exposed 10 or 20 years from now. That means any data that must stay confidential for a decade or more is already at risk. The migration clock started the moment adversaries began harvesting—which security agencies believe is already underway.
How Does Shor’s Algorithm Break Public-Key Encryption?
Shor’s algorithm breaks public-key encryption by exploiting a hidden repeating mathematical structure inside the factoring and discrete-logarithm problems that RSA and elliptic-curve systems rely on. A quantum computer running Shor’s algorithm does not try every possible key in parallel—it uses quantum interference to amplify the correct answer and cancel out all incorrect paths.
Here is the key intuition. An ordinary computer bit is either 0 or 1. A qubit exists as a combination of both states simultaneously. Quantum algorithms are engineered so that wrong computational paths interfere destructively—like two sound waves cancelling each other in noise-cancelling headphones—while the correct path interferes constructively and grows in probability until measurement locks it in.
This only works on problems with a specific hidden periodic structure. Multiplying two large prime numbers to form an RSA public key is easy; factoring the result back is hard for classical computers because it seems random. But the math actually contains a repeating cycle. Shor’s algorithm walks directly onto that cycle.
The critical implication: you cannot patch RSA by making the key bigger. Double the key size, and a quantum computer running Shor’s algorithm breaks it just as easily, because the underlying periodic structure scales with the algorithm, not with the key length. The only fix is to replace the mathematical problem entirely.
Why Does Symmetric Encryption Survive a Quantum Attack More Easily?
Symmetric encryption survives the quantum threat far better than public-key systems because it does not rely on any structured algebraic cycle—it behaves more like a purely randomised combination lock, giving quantum algorithms nothing specific to exploit. The relevant quantum attack, Grover’s algorithm, can speed up a blind search through all possible keys, but only by a square-root factor.
In concrete terms: a 128-bit symmetric key effectively becomes 64 bits of security against a quantum adversary running Grover’s algorithm. The defence is straightforward—upgrade to a larger key. AES-256 provides 128 bits of post-quantum security, which is widely considered sufficient. No mathematical overhaul is required; just thicker armour.
The contrast is stark:
- Public-key systems (RSA, ECC): Completely broken by Shor’s algorithm. Key-size increases offer no protection. Must be replaced.
- Symmetric systems (AES): Weakened but not broken by Grover’s algorithm. Upgrading to AES-256 neutralises the threat.
- Hash functions: Similarly weakened by Grover, but doubling output length restores security margins.
What Mathematical Problems Does Post-Quantum Cryptography Use Instead?
Post-quantum cryptography replaces the integer-factoring and discrete-logarithm problems with entirely different classical math problems that neither quantum nor classical computers can solve efficiently. The leading family, now standardised by NIST, uses lattice-based cryptography.
A lattice is a grid of points in very high-dimensional space—think of a 500-dimensional chessboard. The hard problem is finding the shortest path between two points on that grid. No known quantum algorithm exploits a periodic structure here, because there is none to exploit. The difficulty scales with the dimension, and high-dimensional lattice problems remain hard even for quantum machines.
Crucially, post-quantum cryptographic algorithms are designed to run on conventional hardware—the phones, laptops, and servers already in use. This distinguishes them from quantum key distribution (QKD), a different approach that uses specialised physical lasers and fibre-optic links to transmit secrets encoded in photon states. QKD is theoretically elegant but practically limited: it requires dedicated physical infrastructure and cannot scale across the global internet the way software-based PQC can.
In our experience teaching cryptography concepts to contest students at Intellia Academy, the lattice-based mental model—shortest vector in high-dimensional space—is the one that clicks fastest, because it converts an abstract security claim into a geometric picture.
How Is the Migration to Post-Quantum Cryptography Actually Carried Out?
The migration to post-quantum cryptography requires three sequential phases: inventory, prioritisation, and crypto-agile redesign—and each phase is more operationally complex than it sounds. Simply having new algorithms available does not mean systems are protected; the vulnerable algorithms are buried inside thousands of layers of legacy software, hardware, digital certificates, and third-party vendor products.
- Inventory: Organisations map every location where RSA, ECDSA, or Diffie-Hellman appears—TLS handshakes, code-signing pipelines, firmware update mechanisms, VPN endpoints, and more.
- Prioritise by data lifespan: Systems protecting data that must remain confidential for 15+ years get upgraded first. Shorter-lived data can wait.
- Build crypto-agility: System architects design networks so that algorithms can be swapped without rebuilding the entire IT stack. The goal is a modular security layer where changing the underlying math is a configuration update, not a reconstruction project.
This migration is not theoretical. The U.S. National Institute of Standards and Technology (NIST) finalised its first set of post-quantum cryptographic standards in 2024, selecting algorithms including CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures, both lattice-based. Federal agencies in several countries have issued directives requiring migration timelines.
For students interested in the algorithmic side of this transition, understanding the stack data structure and time complexity trade-offs in competitive programming builds the same kind of asymptotic reasoning that cryptographers use when comparing classical and quantum algorithm costs.
The social engineering side of security—understanding how algorithms and game theory interact—connects naturally to topics like tariff game theory and Nash equilibria in strategic decisions, since national decisions about when to migrate involve exactly the same incentive structures.
What Should Students and Parents Know About Post-Quantum Cryptography in Olympiad Contexts?
Post-quantum cryptography appears at the intersection of number theory, linear algebra, and algorithm analysis—all active areas in olympiad mathematics and computing competitions. Understanding the problem requires fluency in modular arithmetic, probability, and computational complexity, making it ideal preparation for contests that test applied mathematical reasoning.
For students preparing for the AI Olympiad or computing competitions, the conceptual arc from classical algorithms to quantum speedups is directly testable. Shor’s algorithm illustrates the power of quantum Fourier transforms; Grover’s algorithm illustrates the square-root speedup from quantum search. Both appear in competition problem sets and research-level discussions.
Students curious about how algorithms reshape industries—from encryption to social platforms—can explore how social media algorithms use vector scoring and probability-weighted ranking to see another high-stakes application of the same mathematical tools.
Parents asking whether this topic is “too advanced” should note that the core ideas—periodic functions, search complexity, geometric hardness—sit comfortably within a Grade 11 or 12 mathematics curriculum when taught with concrete worked examples rather than abstract formalism. Intellia Academy’s AI Olympiad preparation programme covers algorithmic foundations including the complexity-theoretic ideas that underpin both classical and post-quantum security.
| Encryption type | Quantum algorithm threat | Severity | Defence |
|---|---|---|---|
| RSA / ECC (public-key) | Shor’s algorithm | Catastrophic — key size irrelevant | Replace with lattice-based PQC |
| AES-128 (symmetric) | Grover’s algorithm | Moderate — security halved | Upgrade to AES-256 |
| SHA-256 (hash) | Grover’s algorithm | Moderate — collision resistance reduced | Upgrade to SHA-384 or SHA-512 |
| Lattice-based (CRYSTALS-Kyber) | None known | Resistant | Already post-quantum secure |
Frequently Asked Questions About Post-Quantum Cryptography
Does post-quantum cryptography require a quantum computer to use?
No. Post-quantum cryptography runs entirely on conventional classical hardware—the same phones, laptops, and servers in use today. The “quantum” in the name refers to the threat it resists, not the hardware it needs. Algorithms like CRYSTALS-Kyber are software libraries that integrate into existing systems without any specialised hardware.
Is AES-256 already post-quantum secure?
Yes, for practical purposes. Grover’s algorithm reduces AES-256’s effective security from 256 bits to 128 bits of quantum security. Security experts consider 128 bits of quantum security sufficient against foreseeable quantum hardware. No upgrade beyond AES-256 is currently required for symmetric data encryption.
When does the post-quantum migration need to be complete?
There is no single universal deadline, but the rule of thumb is: any data that must stay secret beyond 2035 should be protected by post-quantum algorithms now, because adversaries may be harvesting it already. NIST finalised its first PQC standards in 2024, and several governments have issued migration mandates targeting federal systems by 2030.
Sources
National Institute of Standards and Technology (NIST) — post-quantum cryptography standardisation programme
Wikipedia — Post-quantum cryptography: overview of lattice, hash, and code-based approaches
- Shor's algorithm breaks RSA and ECC completely by exploiting a periodic mathematical structure—doubling the key size provides no protection, so these systems must be replaced entirely.
- Grover's algorithm only weakens symmetric encryption by a square-root factor, meaning upgrading to AES-256 is sufficient to neutralise the quantum threat to confidential data.
- The Harvest Now, Decrypt Later strategy means adversaries are already collecting encrypted traffic today, making the migration deadline contingent on data lifespan rather than quantum hardware timelines.
- Post-quantum cryptography runs on conventional classical hardware using lattice-based mathematics, making it far more scalable than quantum key distribution, which requires physical fibre-optic infrastructure.
- Crypto-agility—designing systems so that underlying algorithms can be swapped modularly—is the engineering principle that allows organisations to upgrade security without rebuilding their entire infrastructure.
Full video transcript
Let's start with a comforting fact. Right now, there is no publicly known quantum computer stable enough to break internet encryption. But if that's true, why are governments and major tech companies actively scrambling to rip out and replace the digital locks that protect our global infrastructure today?
To understand the rush, we have to look at what those digital locks actually do. Modern cryptography handles three distinct jobs. Confidentiality acts like a locked box, keeping data hidden. Key establishment allows two distant devices to securely agree on the right key to open that box. And digital signatures act like a tamper-evident wax seal, proving who sent the message and that it hasn't been altered. Because these locks rely on very different mathematical puzzles, a future quantum computer won't interact with all of them the exact same way. We have to look at where the specific vulnerabilities lie.
Attackers are not waiting for quantum hardware to arrive before targeting our infrastructure. They are currently executing a strategy known as Harvest Now, Decrypt Later, sweeping up and storing massive amounts of encrypted information they cannot yet read. They can capture state secrets, steal military intelligence, or long-term financial records today, and simply sit on them for 10 or 20 years until the technology catches up. That means the deadline to upgrade our security isn't based on when a fully capable quantum computer finally gets built. The clock is set by the expiration date of our most enduring secrets.
So how does that future hardware actually threaten these locks? An ordinary computer bit operates strictly as a 0 or a 1. A quantum bit, or qubit, exists as a combination of both states. People often assume this means a quantum computer works by branching into millions of parallel timelines to test every possible password at once, but that approach quickly collapses into noise. Instead, quantum algorithms use entanglement and interference. They are programmed so that unhelpful computational paths physically intersect and cancel each other out, much like overlapping sound waves deleting each other in noise-canceling headphones. By carefully controlling this interference, the incorrect paths fade away, while the correct result mathematically amplifies until it is the most likely answer upon measurement. Because this only works on problems with a very specific, hidden structural pattern, quantum computers aren't universally faster replacements for your laptop. They are highly specialized calculation engines.
To share keys and create digital signatures, our public key systems rely on complex algebra, like multiplying massive prime numbers. While factoring those numbers is nearly impossible for ordinary computers, the math contains a hidden repeating structure. Shor's algorithm uses quantum interference to walk onto that exact repeating cycle, easily solving the factoring problems that hold our public keys together. Because of how Shor's algorithm scales against that underlying structure, patching the problem is mathematically impossible. You can double the size of an RSA public key, and a sufficiently powerful quantum computer will chew through it just as easily.
The situation changes completely for symmetric encryption, which we use to lock the actual data. Symmetric keys do not rely on structured algebraic cycles. They operate more like a purely randomized combination lock. An approach called Grover's algorithm can speed up a blind search for that secret key, but without a mathematical shortcut to exploit, the attack is far less destructive. Because Grover's algorithm offers a much milder speedup, we can defend our symmetric data simply by adding thicker armor. Upgrading to a larger key size, like AES-256, provides enough mathematical density to neutralize the threat.
The quantum threat splits our defenses in two. Symmetric encryption requires only a size upgrade, while our public key systems require an entirely new mathematical approach. That new approach is post-quantum cryptography, or PQC. Despite the futuristic name, PQC does not require you to own a quantum computer. These new algorithms are designed to run perfectly on the conventional phones, laptops, and servers we already use. Rather than relying on quantum physics, newly finalized PQC algorithms utilize completely different classical math, such as lattice-based structures, which resist both classical and quantum attacks. This makes it far more practical than quantum key distribution, a separate technology that requires specialized physical lasers and fiber optics to transmit secrets, making it difficult to scale across the global internet.
The strongest defense we have against a quantum physics attack turns out to be a major upgrade to our classical mathematics. But having the math ready doesn't mean the work is done. Upgrading our infrastructure will take years. The vulnerable algorithms are buried deep within thousands of layers of legacy software, hardware, digital certificates, and third-party vendor products. Organizations have to start by mapping out exactly where these old algorithms are hiding. Then they must prioritize upgrading the systems that protect the data needing the longest lifespan of secrecy. This process demands crypto-agility. System architects are designing networks so that algorithms can be smoothly swapped out or upgraded in the future, without having to tear down and rebuild the entire IT infrastructure.
We are changing the digital locks today because replacing cryptography across complex global systems takes time. By executing a massive adaptable migration now, we ensure that decades of confidential data remain secure, long before the first capable quantum machines ever power on.