The Cryptographer Who Ensures We Can Trust Our Computers

How did you go from high school troublemaker to an academic?

I always knew I loved math, but the math in high school wasn’t interesting in any way. Then I went to study math in undergrad, and I was blown away. It’s the first time in my life where I sat and studied nonstop, from morning to night. I was in euphoria. And I have to say, I was a bit upset, because I thought, “I can’t believe I could have enjoyed this when I was much younger!”

What was it about math that captivated you?

It’s very clean, elegant and abstract. And some concepts in math are counterintuitive; I remember feeling that studying it was changing me as a person. You learn to be humble, because over and over again you learn that your intuitions are wrong.

But when I was looking for a good research question, everything felt incremental. So I started moving toward computer science. And cryptography was exactly what I was missing, because it deals with real-world problems. Today, cryptography is used everywhere. It is used to ensure that the messages we send are confidential and authentic. When I text with someone, how do I know the message I received is the message that was sent? How do I know that the person who claims to have sent the message is the one who actually sent it? What does it mean to know that? The concepts are very philosophical, and the way we model it mathematically is really beautiful. It hit the spot for me, both the purity of the math and the applicability.

What kind of cryptographic problems did you work on?

My master’s thesis was titled “How to Leak a Secret.” Here’s the problem: We know how to digitally sign — to say, “This is me that wrote this message.” But say I want to sign something as an MIT professor, but I don’t want people to know it’s me? That way the secret does hold some water because you know an MIT professor signed it, but you don’t know who.

We solved this with something we called ring signatures, which were inspired by a notion in computer science called witness-indistinguishable proofs. Let’s say there’s a statement and two different ways to prove it. We say there’s two “witnesses” to the statement being correct — each of the proofs. A witness-indistinguishable proof looks the same no matter which you use: It hides which witness you started with.

Ring signatures are similar. In the group of potential secret-leakers, you can think of each person as having a secret key. And the ring signature is essentially proving that this message was signed by someone with one of the secret keys, but it doesn’t reveal which secret key they know. It hides whose secret key was used.

Would an institution ever actually use this system?

That’s the beautiful and scary thing about it — I can do it with nobody else being involved. I can sign as a member of the group without the group’s permission. It’s not clear if this is a feature or a bug, but it’s clear it is a scientific discovery. Ring signatures have been used — there’s a cryptocurrency called monero that says they use it for the privacy of transactions. But frankly, I don’t really know who’s using our work. The truth is, I’m too busy to follow it.

How did your work evolve into analyzing the security of our devices?

In the early 2000s I was at the end of my Ph.D., working with Shafi Goldwasser at MIT. People had just started talking about cloud computing, which now we use every day. Before, you had a huge desktop where everything was done. With the increase in large data collection, computations became more costly, and they started to be done remotely. The idea is there’s a powerful cloud that does computations for you. But you may not trust the cloud platform, so how do you know that they’re doing the computation correctly? Sometimes there may be an incentive to cheat because the computation can be very costly. And then in some settings you may be worried about random error. So you really want a proof that this computation is correct.

But typically proofs are very long, and weak devices can’t verify long proofs. Even for devices that can, it’s very costly. So is there a way we can shrink the proofs? Information-theoretically, no. But it turns out that by using cryptographic tools, we can instead generate succinct certificates that are very, very hard to fake. These are called succinct non-interactive arguments, or SNARGs. It’s not a proof, really. But as long as you cannot solve some problem that we cryptographers believe to be very hard, like factoring large numbers, then you cannot fake the succinct proofs.

How did these proofs come about?

It started in 1985 with Shafi Goldwasser, Silvio Micali and Charles Rackoff, who together introduced a notion of interactive proofs. Before, when people thought about proofs, they thought about writing lines of data, and you can read and check if they’re correct or not. Goldwasser, Micali and Rackoff introduced a completely different way of proving something: using interaction. There’s a prover and there’s a verifier, and they exchange messages back and forth. Then the verifier decides if they are convinced or not.

Let me give you an example of something that’s easier to do as an interactive proof than a classical proof. Suppose we are playing chess. Now suppose I want to prove to you that I have a winning strategy. No matter what moves you make, I will still win. How do I prove this to you?

Classically, it’s a huge proof, because I need to prove my strategy works against all possible combinations of moves. But, it turns out, through interaction I can do it very succinctly. If you don’t believe that I have a winning strategy, let’s just play. I’ll show you that I’ll win. Of course, that alone is not convincing — just because I can win once against you doesn’t mean I can win against anyone. So give me a grandmaster. I’ll win against a grandmaster. That starts to demonstrate the power of interaction.

But the downside of an interactive proof is that it’s not transferable. Let’s say you give me a hundred-dollar bill and prove, through interaction, that it is indeed worth $100. I want to be able to pass it on. I want to give it to someone else, who gives it to someone else. But if I only had an interactive proof, that means nothing; I can’t give it to anyone else. So the nice thing about SNARGs is that you can give them to someone else.

Like a certificate of authenticity?

Exactly. Blockchains are the main place that they’re used today, to verify transactions. When blockchain came about, I told my students we should send the developer of bitcoin, Satoshi Nakamoto, flowers and chocolates, because he really made our work so relevant.

So how do you remove the interaction to create these transferable certificates?

With cryptography. Let me try to give you an intuition for how this works. In our interactive proofs, the verifier usually just sends randomness to the prover — you could think of this as the verifier randomly spot-checking the proof. Then Amos Fiat and Adi Shamir had an idea: Why do you need this verifier if all he does is send randomness? Maybe we can replace this verifier with some function, like something called a hash function — it’s a function that looks random, and it’s a very important building block in cryptography.

And it turns out that yes, we can. Today, this is done all the time. If you have an iPhone or an Android, you’re using the Fiat-Shamir paradigm when your phone connects to remote servers, which may happen frequently throughout the day. And it’s this paradigm that we use to construct the succinct proofs that certify that remote computations are correct.

You’ve talked about machines needing to be “post-quantum secure.” What does that mean?

Quantum computers, if they actually come to exist on a large scale, will be much more powerful than classical computers. Classical computers work in bits, which are either 0 or 1. In quantum computers, you have quantum bits, which are in superposition between 0 and 1. And these qubits are entangled, which means that they influence each other. That’s what really gives quantum computers their power.

In the future, it may not be that everyone has a quantum desktop. There might be a few expensive quantum devices that do remote computations for you. Suppose you want to delegate an expensive computation to one of these quantum devices, and you need some certificate that verifies the output is correct — how do you certify the correctness of quantum computers? Now that we want to use quantum bits and not classical bits, everything changes, especially when I want the verifier to be a classical computer.

In 2018, there was a groundbreaking result by a Berkeley student, Urmila Mahadev. She was the first to show a classical, computationally secure proof for verifying quantum computations.

So you can use a classical computer to verify quantum computations? That sounds impossible!

Isn’t that amazing? I was on the program committee when Urmila published her paper, and I spent all night looking at it — the amount of caffeine I drank! I was mind-blown. At that point, I was a complete quantum dummy. I understood the crypto part, but it took me a while to understand how that sat together with the quantum part. And it was beautiful.

Moving from classical to quantum computing sounds like a steep learning curve.

I know. I actually know nothing about physics, and there’s a lot of quantum-physical intuition involved. I don’t understand the most basic concepts, like energy and temperature. Sometimes I work with students and as soon as we talk about quantum computing, I become the student. I’m starting to gain a little more intuition. And I have to say, I’m enjoying it so much, sitting there with a textbook on quantum information. There’s nothing better than being a student.