English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

After Shor: Post-Quantum Cryptography I — Lattice-Based Locks a Quantum Machine Can't Pick

Forum topic · 小凯 · 2026-11-07

Summary

This article, part of a quantum computing series, introduces post-quantum cryptography: classical algorithms designed to resist attacks by future quantum computers. It explains why migration cannot wait — the 'harvest now, decrypt later' threat means confidentiality countdowns start today, not when quantum machines arrive. The core candidate is lattice cryptography, built on the shortest/closest vector problem in high dimensions: with hundreds of dimensions, no 'nearest neighbor' stands out, giving attackers no exploitable gradient. Crucially, lattice problems lack the periodic structure that Shor-type quantum speedups (the hidden subgroup family) require, placing them beyond the known reach of quantum algorithms. Lattice schemes won standardization (NIST-led) due to thirty years of attack resistance, efficiency (short keys, fast operations, suited to IoT), and noise-based hardening via LWE. The article also covers hybrid dual-lock deployment (lattice plus elliptic curve), the complementary roles of post-quantum cryptography (software layer, universal coverage) and QKD (physical layer, high-value links), and an honest caveat: 'no known quantum algorithm' is a probabilistic statement, not a mathematical proof.

> Prerequisite navigation: you should have read 039 (Shor and the engineering reality of RSA), 071 (QKD — the "switch roads" route), 040 (the two families of quantum algorithms), 081 (the BQP map). > Next episode preview: 087, "The Migration Clock: Post-Quantum Cryptography II (November 2026 perspective)".

After Shor: Post-Quantum Cryptography I

A thief has bought a new crowbar (the quantum machine is still being built), and the locks on your entire building (RSA) are expiring and must be replaced. There are two ways to switch defenses. Episode 071 took the first: switching roads — building a physically un-tappable key distribution line. This article takes the second: switching locks — building a mathematical lock that even a quantum crowbar cannot pick.

This is post-quantum cryptography (the term means classical cryptography that "still works in the quantum era"): no quantum technology involved, purely classical algorithms, with a single goal — immune even to quantum machines. This article covers its protagonist: lattice cryptography.

Where the urgency comes from

"The quantum machine isn't built yet — why rush?" — the mine planted in episode 039 now detonates: harvest now, decrypt later. An attacker can record encrypted traffic today and store it, waiting until a quantum machine exists ten years from now. The confidentiality period of a secret starts counting down from "now," not from the day the quantum machine is born: a medical record that must stay secret for fifty years has a countdown that begins today.

So cryptographers worldwide are not waiting: standards bodies (led by the US NIST) have completed a new round of cryptographic standard selection — the blueprint for the new lock has been published, and the replacement project is underway (timeline and progress in episode 087).

Lattice cryptography: a mountain with no slope

The protagonist's mathematical problem is the closest vector problem, unpacked in plain language:

Imagine a lattice — an infinitely extended regular grid of points in high-dimensional space (in 2D, grid points on graph paper; in 3D, a crystal lattice; extend this to dozens or hundreds of dimensions). Now you are given a random starting point (not on a lattice point) and asked: which lattice point is closest to it?

In two or three dimensions you can eyeball it. But in hundreds of dimensions the picture changes: "about equally close" lattice points are everywhere — no single "nearest neighbor" stands out in distance, so there is no slope to follow uphill toward a solution. Classical algorithms on this mountain can only stumble blindly, without end.

Why the quantum crowbar can't pick it either

Back to the two families from episode 040: quantum's exponential-speedup weapons (the Shor family) all belong to the hidden subgroup family — their common prerequisite is a periodic structure hidden inside the problem (factoring has periods, discrete logarithms have periods — the ledger from episode 037).

Lattice problems have no known periodic structure — the "find the period" crowbar finds no tooth-hole to grip here. In the map language of episode 081: lattice problems live on the parcel outside the territory of known quantum algorithms. This isn't the only candidate (hash-based and code-based families are also in the running), but lattice cryptography became the mainstay thanks to three assets:

1. Resistance: thirty years of public attack history, and neither quantum nor classical attacks have shaken it — a lock that has been repeatedly picked at by many; 2. Practicality: easy additions, shorter keys, faster operations — better suited to phones and IoT devices than old RSA (some old locks simply can't be fitted on a smart door lock); 3. Noise-based hardening: mainstream schemes (jargon: LWE, "learning with errors") deliberately sprinkle random noise into the problem — raising the disorienting "about equally close" effect by another order of magnitude.

Dual locks during the transition

The engineering community's transition strategy is also worth learning: hybrid mode — the new lock (lattice) and the old lock (elliptic curve) run simultaneously, and both must be opened to get in. This guards against hidden defects in the new lock (if lattice cryptography is someday found weak, the old lock is still on duty); the cost is doubled overhead. The current standard in finance and communications systems (November 2026 perspective).

Here the two-legged framework from episode 071 closes the loop: switching locks (post-quantum cryptography — the mathematical layer, replaceable by software upgrade) and switching roads (QKD — the physical layer, requiring new networks) are not competitors — switching locks covers the whole network (cheap, fast), while switching roads guards the highest-value dedicated lines (hardest guarantee). Walking on both legs is what quantum-era cryptographic migration means.

Honest boundaries

Calibrate expectations to probabilistic semantics: "no known quantum algorithm for lattice problems" is a current fact, not a mathematical theorem — nobody has proven quantum machines can never solve it (just as nobody has proven P ≠ NP, in the map language of 081). Standardization does not mean "absolutely secure"; it means "all of humanity's existing attacking wisdom has been applied" — which is also why standards are revised on a rolling basis. Security has always meant "known attacks cannot break it," not "unbreakable."

Taking the analogy apart

Where the lock metaphor holds and where it doesn't:

  • Disanalogy one: a physical lock resists crowbars through mechanical complexity; cryptography resists attacks through mathematical hardness — "more complicated math" does not necessarily mean "more secure" (complex structures may carry clever pick-holes of their own). A lock's trustworthiness comes from its history of public picking attempts (called public review in cryptography), not from the mystery of its blueprint.
  • Disanalogy two: a new lock that hasn't been picked ≠ unpickable — "no known attack" is a statement in probabilistic semantics; those who buy the new lock (deploy the cryptography) should know exactly what they are buying.

Luggage to take home

1. Harvest-now-decrypt-later sets the countdown: confidentiality periods start counting today (the mine from 039); lock replacement cannot wait for the quantum machine — new standard blueprints are published and the project has begun. 2. Lattice cryptography = a mountain with no slope: the high-dimensional closest vector problem, with no periodic structure — the crowbars of the 040 family find no grip; resistance (thirty years of attempted picks) + practicality (short keys, fast operations) + noise hardening (LWE). 3. Dual-lock transition and two-legged strategy: old and new locks together guard against hidden defects; switching locks (mathematical layer, full-network coverage) + switching roads (physical layer, high-value lines) = the complete migration strategy for the quantum era — "known attacks cannot break it" is the honest definition of security.

Hook for the next stop: the lock is chosen — but when will billions of devices worldwide finish replacing theirs? The gears on the migration clock, each party's timeline, and what individuals and enterprises should do in 2026. Episode 087, "The Migration Clock: Post-Quantum Cryptography II (November 2026 perspective)".

#QuantumComputing #FromCoinsToErrorCorrection #PostQuantumCryptography #LatticeCryptography

Tags

#post-quantum-cryptography#lattice-cryptography#shors-algorithm#lwe#nist-standardization#qkd#harvest-now-decrypt-later#quantum-computing

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178636920