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.
"What good is a key that you can never use?" the researchers wondered initially. But they proved in October 2023 that one-way puzzles combined with other quantum techniques could enable a wide range of cryptographic protocols. The inefficiency doesn't matter—just knowing a solution exists in principle is enough.
"Just knowing that there exists some algorithm that can be arbitrarily slow is sufficient," said William Kretschmer, whose 2021 paper first identified quantum problems that could replace one-way functions. "That is very surprising."
The breakthrough came during Khurana's pregnancy in July 2023, after months of being stuck. "I'm much more pessimistic than Dakshita," Tomer admits. "She's always the one who believes that things will work." They finished their proof on August 4—just days before Khurana's daughter was born.
By November, with baby in tow, Khurana tackled the next challenge: anchoring their quantum foundation to real mathematical bedrock. They identified the matrix permanent problem—calculating specific combinations of entries in numerical tables—as an ideal candidate. This problem is notoriously difficult for large matrices and has no simple way to verify solutions.
The matrix permanent problem connects to quantum computational advantages that researchers are still working to prove rigorously. If that proof materializes, it would automatically establish quantum cryptography on stronger theoretical ground than practically any classical approach.
"This would be a beautiful problem to base cryptography on," Khurana said. The work effectively reduces two open mathematical problems to one: prove quantum computers surpass classical ones at a specific task, and you automatically get secure quantum cryptography.
The implications extend beyond theoretical mathematics. While recent progress in quantum computing is encouraging, the technology isn't mature enough to implement these ideas practically. Other researchers have devised quantum cryptography methods that could be deployed sooner, though their security requires additional validation.
"We're just trying to understand this new landscape that really existed the whole time," Zhandry reflects. The landscape keeps revealing surprises as researchers explore quantum cryptography's possibilities.
While still years from practical implementation, this mathematical breakthrough represents a fundamental shift in how we think about digital security. By proving quantum physics can provide cryptographic foundations independent of classical hard problems, Khurana and Tomer have sketched a path toward encryption that could withstand even the most sophisticated future attacks. The work transforms quantum cryptography from theoretical curiosity into a viable long-term strategy for protecting digital communications in an uncertain computational future.
