Welcome to the Quanta Science Podcast. Each episode, we bring you stories about developments in science and mathematics. I'm Susan Vallett. Researchers have proved that secure quantum encryption is possible in a world without hard problems. That's next.

It's season three of The Joy of Why, and I still have a lot of questions. Like, what is this thing we call time? Why does altruism exist? And where is Jan Eleven? I'm here, astrophysicist and co-host, ready for anything. That's right. I'm bringing in the A-team. So brace yourselves. Get ready to learn. I'm Jan Eleven. I'm Steve Strogatz. And this is... Quantum Magazine's podcast, The Joy of Why. New episodes drop every other Thursday.

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. That's why 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 theorists

System theory was originally developed to understand the physics of atoms, but it also 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. However, 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. Henry Yuen is a quantum information theorist at Columbia University. There's things that are like what I call low tech going up to really high tech primitives. And over the years, people have sort of built some understanding that these things are really separated from each other. Like if I give you a low tech thing, you can't generically obtain a high tech thing.

Now we're sort of looking at things from the quantum angle and we're saying, if you allow the parties in the cryptographic protocol to transmit qubits to each other, what is the organization between the low tech and high tech things? And it seems like the landscape is pretty different. Like things that we thought were higher tech actually are pretty low tech. That's a good thing. It means that you have more trust and more faith in their security.

And so there's just been like this rearrangement of what we believe is possible with quantum cryptography. 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.

Fermi Ma is a quantum cryptographer at the Simons Institute for the Theory of Computing in Berkeley, California. The most exciting thing is this idea that the assumptions you need can be way, way, way weaker. Because at the end of the day, everything will be built on the assumptions. Crypto, even in the quantum world, I think is still about combining assumptions, combining computational hardness with quantum information and doing interesting things with that. And what's getting me so excited about it is like, not only are you getting all these new functionalities, but it's like,

actually trying to do this is like giving us new insights into computational hardness itself. 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 took an unorthodox, information-centric view of quantum theory. He 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 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 computer scientist Jill Broussard 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. Here's Ma. In the 80s, when people were first starting to understand how quantum information worked...

One thing we realized is that just the very nature of quantum information seems somewhat cryptographic.

Like you can't just clone quantum states. There's something there, like that's something about quantumness is like just, it's like nature protecting information. Bennett and Brazard'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, Yuan says imagine a two-player game in which you must make a secret decision that later gets revealed. So the idea of a bit commitment is it's like cryptographic equivalent of putting a message in a sealed envelope that they can't immediately read.

And then later at some designated point, you say, all right, we can open the envelope and verify that I have like put in a bid or a vote. A bid commitment scheme is a cryptographic equivalent of that. It's like very, very useful for voting protocols or multi-party computation or like even in blockchain, it's very useful.

So first, when you give the envelope to the receiver, you don't want them to be able to read what's inside of it. Digitally speaking, like you give them some piece of information, it should be like encrypted somehow for them. And so that's one part of it. And then the second part of the security is that later in the second phase, when we all agree to reveal what's in the envelope, I shouldn't have been able to change my mind. 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, 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. The defining feature of NP 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.

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. 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. His descriptography wasn't even on his radar at that point. 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 zeros and ones. 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.

Here's Ewan. Somehow the language with which we've

Described quantum computations in traditional complexity theory can't directly talk about these problems that people are interested in. At first, Kretschmer thought he might need to translate the problem into more standard language, but he couldn't figure out how. I thought like, you know, I was just not being clever enough. Like, there's probably some more clever way that you can like reduce this to something simple. And eventually I realized you couldn't. 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. Luo Wenjian is a graduate student studying cryptography at Boston University. I was really fascinated by William's paper.

I actually thought it had to be wrong. It's so counterintuitive. Qian, Yuan, and others 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. 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? Here's Chun. In the real world, how do we actually get such a magic product? Like, how do we actually instantiate that?

In this quantum cryptography paper where we instead use a random oracle, this actually gives you a way, a potential way, a more concrete, a more feelable way of actually instantiating these quantum cryptographic objects instead of saying, first get a magic button.

In 2022, Kretschmer and Shon 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. Here's Kretschmer. I would say it's just a less studied model. Like, random classical oracles are, it's an assumption that people have been studying for decades, maybe 40 years at this point or something.

We have like a pretty good understanding of when these things are secure, I think. For this quantum oracle, like, yes, you know, this quantum random oracle looks natural in a certain sense, but it's not something that people have studied for four years. It's not something that people have studied for four years. I mean, I think it's just less known about it. Kretschmer soon realized that the state discrimination problem was mathematically related to a superficially different problem in quantum complexity theory. So

So we enlisted the help of two experts in the area, complexity theorists Avishai Tal and Makran Sinha.

Tal remembers that time. William was really like a manager and we were like contractors. We were like, okay. And after I came to him with some ideas and then he told me about the big picture. 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

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?

Dakshita Khurana is a cryptographer at the University of Illinois Urbana-Champaign. Problems in NP are not the hardest classical problems one can think about. There's hardness beyond that.

So 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. And it was just so fascinating and so kind of mind-bending that I was just immediately hooked.

So, and then I was just like, "Fermi, Alex, you guys want to add me to a project sometime?" That's how I got into it. 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. Here's Lombardi on that. It sounded a little bit insane to me when we asked the question. We still don't actually know the answer, but I don't think I expected even the one query result that we were able to prove. So 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 determine 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 complexity theorist Scott Aronson and mathematician Greg Kuperberg. It's about the difficulty of transforming one quantum state into another. The new paper was the first significant step toward settling that question.

Tomoyuku Morimai is a quantum cryptography researcher at the Yukawa Institute for Theoretical Physics in Kyoto. He calls this a very strong result and also a very surprising result.

The string of recent results suggests that the innocuous-sounding problem of distinguishing two quantum states is not just hard, but almost inconceivably hard. It's 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. Or in the words of Andrea Coladangelo, a quantum cryptographer at the University of Washington: It feels that there's something fundamentally different about how quantum information behaves from the classical. It's bound to have connections that are also beyond cryptography.

Arlene Santana helped with this episode. I'm Susan Vallett. For more on this story, read Ben Brubaker's full article, Cryptographers Discover a New Foundation for Quantum Secrecy, on our website, quantummagazine.org. Just a quick note, Scott Aronson is a member of Quantum Magazine's advisory board. His work was mentioned in this podcast, but he played no part in the editorial process.

Also, 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. Make sure to tell your friends about the Quantascience podcast and give us a positive review or follow where you listen. It helps people find this podcast.