Cryptographers Discover a New Foundation for Quantum Secrecy
Eliot Wyatt for Quanta Magazine
Introduction
Say you want to send a private message, cast a secret vote or sign a document securely. If you do any of these tasks on a computer, you’re relying on encryption to keep your data safe. That encryption needs to withstand attacks from codebreakers with their own computers, so modern encryption methods rely on assumptions about what mathematical problems are hard for computers to solve.
But as cryptographers laid the mathematical foundations for this approach to information security in the 1980s, a few researchers discovered that computational hardness wasn’t the only way to safeguard secrets. Quantum theory, originally developed to understand the physics of atoms, turned out to have deep connections to information and cryptography. Researchers found ways to base the security of a few specific cryptographic tasks directly on the laws of physics. But these tasks were strange outliers — for all others, there seemed to be no alternative to the classical computational approach.
By the end of the millennium, quantum cryptography researchers thought that was the end of the story. But in just the past few years, the field has undergone another seismic shift.
“There’s been this rearrangement of what we believe is possible with quantum cryptography,” said Henry Yuen, a quantum information theorist at Columbia University.
In a string of recent papers, researchers have shown that most cryptographic tasks could still be accomplished securely even in hypothetical worlds where practically all computation is easy. All that matters is the difficulty of a special computational problem about quantum theory itself.
“The assumptions you need can be way, way, way weaker,” said Fermi Ma, a quantum cryptographer at the Simons Institute for the Theory of Computing in Berkeley, California. “This is giving us new insights into computational hardness itself.”
This Message Will Self-Destruct
The story begins in the late 1960s, when a physics graduate student named Stephen Wiesner started thinking about the destructive nature of measurement in quantum theory. Measure any system governed by the rules of quantum physics, and you’ll alter the quantum state that mathematically describes its configuration. This quantum measurement disturbance was a hindrance for most physicists. Wiesner, who took an unorthodox information-centric view of quantum theory, wondered whether it could be made useful. Perhaps it could serve as a form of built-in tamper protection for sensitive data.
But Wiesner’s ideas were too far ahead of their time, and he left academia after graduate school. Fortunately, he’d discussed his ideas with his friend and fellow physicist Charles Bennett, who unsuccessfully tried to interest others in the subject for a decade. Finally, in 1979, Bennett met the computer scientist Gilles Brassard while swimming off the coast of Puerto Rico during a conference. Together, they wrote a groundbreaking paper describing a new approach to an important cryptographic task. Their protocol was based on quantum measurement disturbance, and needed no assumptions about the difficulty of any computational problems.
“The very nature of quantum information seems somewhat cryptographic,” Ma said.
In the 1980s, Charles Bennett (top) and Gilles Brassard pioneered a new approach to cryptography based on quantum physics.
In the 1980s, Charles Bennett (left) and Gilles Brassard pioneered a new approach to cryptography based on quantum physics.
BBVA Foundation; Lëa-Kim Châteauneuf
Bennett and Brassard’s breakthrough made researchers optimistic that similar quantum tricks could yield perfect security for other cryptographic tasks. Researchers focused mainly on a task called bit commitment, which is useful on its own and is also a key component of most advanced cryptographic protocols.
To understand the basic idea behind bit commitment, imagine a two-player game in which you must make a secret decision that later gets revealed. One way to do this is to write the decision down on a slip of paper and put it in a sealed envelope. That way, you can’t change your decision later on, and your opponent can’t prematurely peek at the result.
Now imagine you’re playing the same game online. To make cheating impossible, you need to seal the decision in a sort of digital envelope that neither player can open alone. That’s where cryptography comes in. In 1981, the pioneering computer scientist Manuel Blum constructed the first bit commitment protocol — a way to build effectively unhackable envelopes out of hard computational problems.
But how hard is hard? Researchers in the field of computational complexity theory study many different kinds of hard problems, and not all of them are useful for cryptographers. Bit commitment and all other cryptographic protocols rely on problems in a class that complexity theorists call “NP,” whose defining feature is that it’s easy to check whether a candidate solution is correct.
Unfortunately, researchers haven’t been able to prove that any NP problems are truly hard. There could still be some clever undiscovered procedure, or algorithm, for solving even the ones that seem hardest. If there is, then all of classical cryptography would break.
Such considerations animated the search for quantum-based security guarantees. But in 1997, two papers proved that bit commitment schemes could never be completely secure if they were based solely on the laws of quantum physics. The papers implied that some kind of computational hardness would be necessary for almost all cryptographic tasks.
William Kretschmer’s work on distinguishing certain quantum states led researchers to rethink the foundations of quantum cryptography.
Justin DuRant
That was the last word on the theoretical foundations of quantum bit commitments for nearly 25 years. Then, in 2021, a paper by a graduate student named William Kretschmer prompted researchers to confront a question that nobody had thought to ask. Computational hardness was clearly necessary for bit commitments and most other forms of cryptography, but precisely what kind of hardness?
The answer would turn out to be weirder than anybody had anticipated.
Consulting Oracles
The 2021 paper came out of Kretschmer’s struggle to understand a specific version of a problem that sounds conceptually straightforward: How hard is it to distinguish, or discriminate between, two quantum states that look superficially similar? Kretschmer, who’s now a postdoctoral researcher at the Simons Institute, was initially interested in the problem for reasons that had nothing to do with bit commitment.
“Cryptography was not even on my radar,” he said.
The discrimination problem was interesting in part because it wasn’t even clear how to describe it using familiar mathematical language. Complexity theorists traditionally study problems with different possible inputs represented by strings of bits, or 0s and 1s. For the problem of decomposing large numbers into their prime factors, for instance, this string represents the number to be factored.
Even after researchers started studying how quantum physics might be harnessed for computation, they continued to focus on such “classical-input” problems. Typical quantum algorithms start with an ordinary classical bit string and then process it using quantum trickery. But in “quantum-input” problems like Kretschmer’s, the inputs aren’t bit strings — they’re quantum states that are as easily disrupted by computation as by measurement.
“The language with which we’ve described quantum computations in traditional complexity theory can’t directly talk about these problems,” Yuen said.
At first, Kretschmer thought he just needed to translate the problem into more standard language, but he couldn’t figure out how. So he did what complexity theorists often do when they’re desperate: He turned to an oracle.
In complexity theory, the term “oracle” refers to a hypothetical device that can solve a specific problem instantly. A computer with access to an oracle might be able to solve other problems more easily by consulting the oracle as an intermediate step in an algorithm. Of course, oracles don’t actually exist in the real world, but studying them helps complexity theorists understand the relationships between the difficulty levels of different problems.
Kretschmer wondered what kind of oracle could make it easy to distinguish two quantum states — the so-called state-discrimination problem. He decided to start with a special oracle that would boost the power of normal quantum algorithms, the ones that use quantum tricks to solve problems with classical bit string inputs. Such algorithms can solve some problems too hard for classical ones, like factoring large numbers, but they’re not omnipotent — many other problems lie beyond their reach.
Access to Kretschmer’s oracle would enable such algorithms to solve certain classical-input problems too hard for real quantum computers. Kretschmer assumed that it would be overkill, but to his surprise, he proved that the state-discrimination problem could still stump these souped-up quantum algorithms.
“I was really fascinated by William’s paper,” said Luowen Qian, a graduate student studying cryptography at Boston University. “I actually thought it had to be wrong, because it’s so counterintuitive.”
Luowen Qian (left), Avishay Tal (center) and Makrand Sinha teamed up with Kretschmer to prove that many quantum cryptography techniques could still be secure even if classical cryptography is impossible.
Xichen Li; Herve Attia/TerrificShot Photography; Heather Coit/Grainger Engineering
Qian, Yuen and others soon proved that if Kretschmer’s state discrimination problem really was hard, secure quantum bit commitment schemes would be possible. That would in turn imply security for a slew of more advanced cryptographic protocols. The scope of quantum cryptography was far broader than researchers in the 1990s had realized, and it all came down to the hardness of one problem.
How Hard Could It Be?
Kretschmer’s result came with one big caveat — to make the proof work, he had to rely on an unusual oracle that only quantum algorithms could consult. Perhaps a more familiar oracle would make his state discrimination problem easy, and therefore make secure quantum bit commitments impossible? In 2022, Kretschmer and Qian began working together to see what they could prove about an oracle everybody could understand: one that could solve any NP problem instantaneously. In a world with such oracles, all classical cryptography would be impossible.
Kretschmer soon realized that the state discrimination problem was mathematically related to a superficially different problem in quantum complexity theory, and he enlisted the help of two experts in the area, the complexity theorists Avishay Tal and Makrand Sinha. “William was really like a manager, and we were contractors,” Tal said.
Working together, the four researchers quickly proved that Kretschmer’s state discrimination problem could still be intractable even for computers that could call on this NP oracle. That means that practically all of quantum cryptography could remain secure even if every problem underpinning classical cryptography turned out to be easy. Classical cryptography and quantum cryptography increasingly seemed like two entirely separate worlds.
The result caught Ma’s attention, and he began to wonder just how far he could push the line of work that Kretschmer had initiated. Could quantum cryptography remain secure even with more outlandish oracles — ones that could instantly solve computational problems far harder than those in NP? “Problems in NP are not the hardest classical problems one can think about,” said Dakshita Khurana, a cryptographer at the University of Illinois, Urbana-Champaign. “There’s hardness beyond that.”
Fermi Ma (left), John Wright (center) and Alex Lombardi proved that quantum cryptography could still be secure even with an oracle that could instantly solve any computational problem that had classical inputs.
Xinyu Tan; Soya Park; Jessica Xu
Ma began brainstorming how best to approach that question, together with Alex Lombardi, a cryptographer at Princeton University, and John Wright, a quantum computing researcher at the University of California, Berkeley. “It was just so fascinating and so mind-bending that I was immediately hooked,” Wright said.
After thinking about the question for a while and getting nowhere, Ma suggested that they consider the most extreme case possible: an oracle that could instantly solve any computational problem with classical inputs. That would include all the problems complexity theorists have traditionally studied, even those known to be unsolvable in the real world.
“It sounded a little bit insane to me,” Lombardi said.
But the question turned out to be remarkably fruitful. After working on it for nearly a year, they finally published a striking result. No algorithm allowed to consult that all-powerful oracle exactly once can distinguish the two quantum states, as is required to undermine a quantum bit commitment scheme.
Limiting algorithms to a single query is less of a constraint than it may sound, because quantum algorithms can effectively ask the oracle to solve multiple problems simultaneously by exploiting the phenomenon called superposition. Algorithms that can make multiple queries sequentially could be more powerful, because they can use the oracle’s answers to previous queries to decide what to ask next. Whether these algorithms are similarly limited remains an open question.
Ma, Lombardi and Wright’s paper was also significant for another reason. While the three researchers were wrestling with their problem, they realized it was closely linked to a major open problem posed 16 years earlier by the complexity theorist Scott Aaronson and the mathematician Greg Kuperberg, about the difficulty of transforming one quantum state into another. The new paper was the first significant step toward settling that question.
“It’s a very strong result and also a very surprising result,” said Tomoyuki Morimae, a quantum cryptography researcher at the Yukawa Institute for Theoretical Physics in Kyoto.
The string of recent results suggests that the innocuous-sounding problem of distinguishing two quantum states is not just hard, but almost inconceivably hard — far beyond the reach of normal quantum algorithms and even more exotic ones. That’s good news for cryptography, but it also has broader implications for computational problems whose inputs are quantum states. Traditional complexity theory seems unable to address these problems. Truly understanding them might require a radically new theoretical framework.
“It feels like there’s something fundamentally different about how quantum information behaves,” said Andrea Coladangelo, a quantum cryptographer at the University of Washington. “It’s bound to have connections that are also beyond cryptography.”
Editor’s note: Scott Aaronson is a member of Quanta Magazine’s advisory board. His work was mentioned in this article but he played no part in the editorial process. Further, the Simons Institute for the Theory of Computing was established with a grant from the Simons Foundation, which also funds this editorially independent publication. Simons Foundation funding decisions have no influence on our coverage.
