The original version of this story appeared in Quanta Magazine.
Hard problems are usually not a welcome sight. But cryptographers love them. That’s because certain hard math problems underpin the security of modern encryption. Any clever trick for solving them will doom most forms of cryptography.
Several years ago, researchers found a radically new approach to encryption that lacks this potential weak spot. The approach exploits the peculiar features of quantum physics. But unlike earlier quantum encryption schemes, which only work for a few special tasks, the new approach can accomplish a much wider range of tasks. And it could work even if all the problems at the heart of ordinary “classical” cryptography turn out to be easily solvable.
But this striking discovery relied on unrealistic assumptions. The result was “more of a proof of concept,” said Fermi Ma, a cryptography researcher at the Simons Institute for the Theory of Computing in Berkeley, California. “It is not a statement about the real world.”
Now, a new paper by two cryptographers has laid out a path to quantum cryptography without those outlandish assumptions. “This paper is saying that if certain other conjectures are true, then quantum cryptography must exist,” Ma said.
Castle in the Sky
You can think of modern cryptography as a tower with three essential parts. The first part is the bedrock deep beneath the tower, which is made of hard mathematical problems. The tower itself is the second part—there you can find specific cryptographic protocols that let you send private messages, sign digital documents, cast secret ballots, and more.
In between, securing those day-to-day applications to mathematical bedrock, is a foundation made of building blocks called one-way functions. They’re responsible for the asymmetry inherent in any encryption scheme. “It’s one-way because you can encrypt messages, but you can’t decrypt them,” said Mark Zhandry, a cryptographer at NTT Research.
In the 1980s, researchers proved that cryptography built atop one-way functions would ensure security for many different tasks. But decades later, they still aren’t certain that the bedrock is strong enough to support it. The trouble is that the bedrock is made of special hard problems—technically known as NP problems—whose defining feature is that it’s easy to check whether any candidate solution is correct. (For example, breaking a number into its prime factors is an NP problem: hard to do for large numbers, but easy to check.)
Many of these problems seem intrinsically difficult, but computer scientists haven’t been able to prove it. If someone discovers an ingenious algorithm for rapidly solving the hardest NP problems, the bedrock will crumble, and the whole tower will collapse.
Unfortunately, you can’t simply move your tower elsewhere. The tower’s foundation—one-way functions—can only sit on a bedrock of NP problems.
To build a tower on harder problems, cryptographers would need a new foundation that isn’t made of one-way functions. That seemed impossible until just a few years ago, when researchers realized that quantum physics could help.