Cryptographers have solved a major theoretical challenge in quantum encryption, proving that secure quantum cryptography can exist without relying on the hard mathematical problems that underpin all classical encryption. The breakthrough could eventually lead to encryption methods that remain secure even if all current encryption schemes are broken.
The encryption protecting your digital life rests on a shaky foundation. Every secure message, digital signature, and private transaction depends on mathematical problems that seem hard to solve—but cryptographers can't actually prove they're unsolvable. If someone discovers a clever algorithm to crack these problems, the entire edifice of modern cryptography could collapse overnight.
Now, researchers at the University of Illinois and NTT Research have built what amounts to a mathematical escape hatch. In a new paper published this week, cryptographers Dakshita Khurana and her graduate student Kabir Tomer prove that quantum physics offers a radically different approach to encryption—one that could remain secure even if all classical encryption methods are broken.
"This paper is saying that if certain other conjectures are true, then quantum cryptography must exist," Fermi Ma, a cryptography researcher at the Simons Institute for the Theory of Computing, told Quanta Magazine. The work builds on earlier theoretical breakthroughs that seemed promising but relied on unrealistic assumptions about hypothetical computing devices.
The problem with today's encryption is architectural. Think of cryptography as a three-story tower: mathematical bedrock at the bottom made of hard problems, a foundation of "one-way functions" in the middle, and practical encryption protocols on top. The bedrock consists of NP problems—mathematical challenges that are seemingly difficult to solve but easy to verify once you have an answer.
That "seemingly" is the trouble. Computer scientists haven't been able to prove these problems are actually hard. If someone develops an efficient algorithm for the hardest NP problems, the entire cryptographic tower crumbles.
"It's one-way because you can encrypt messages, but you can't decrypt them," explains Mark Zhandry, a cryptographer at NTT Research. But those one-way functions can only sit on a bedrock of NP problems.
Khurana and Tomer's breakthrough centers on replacing classical one-way functions with quantum building blocks they call "one-way puzzles." These mathematical oddities have a perplexing characteristic: they can generate locks and keys that theoretically fit together, but the key is too unwieldy to actually open the lock efficiently.