Yael Tauman Kalai’s breakthroughs secure the digital world, from cloud computing to our quantum future.
Yael Tauman Kalai, a cryptographer at Microsoft’s New England Research and Development Center, focuses on ways to safeguard computations.
Katherine Taylor for Quanta Magazine
Introduction
Yael Tauman Kalai is a pioneering theoretical computer scientist who’s won impressive awards and changed the way people think about the internet. But as a kid, she wasn’t exactly a model student.
“I was a troublemaker,” she said. “I was basically — not quite, but basically — kicked out of high school.”
Kalai was born and raised in Tel Aviv, Israel, in an academic family. Her father, Yair Tauman, is an economist and game theorist. Her high school classes bored her — one report card documented something like 150 school absences, she recalls, as she preferred to spend her time water skiing and socializing. But her analytical skills were always there.
“When my parents didn’t let me go out, often the only way to get my dad to agree was to tell him, ‘OK, give me a math riddle. As hard as you want, but if I solve, I go.’” She usually went.
Her dormant love of math finally awakened in college, when she began to recognize its beauty. Eventually, she discovered she could put this math to use with computers and, specifically, securing information. Now, her work straddles the fields of math and computer science, and her ideas have been foundational to how we protect and verify computation in the digital age. For the past two decades, she has worked to ensure the integrity of our smartphones, cloud connections and even cryptocurrencies. Now a researcher at Microsoft and an adjunct professor at the Massachusetts Institute of Technology, she recently won the Association for Computer Machinery’s prestigious ACM Prize in Computing for “breakthroughs in verifiable delegation of computation and fundamental contributions to cryptography.” Her latest work also looks to the future, as she considers on how quantum computers may affect the security landscape.
Quanta spoke with Kalai about leaking secrets, verifying the cloud and the funkiness of quantum computing. The interview has been condensed and edited for clarity.
Introduction
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.
Kalai compares the power of interactive proofs to a game of chess: Rather than prove theoretically that you have a winning strategy, you can just consistently win.
Katherine Taylor for Quanta Magazine
Introduction
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.
Kalai was an indifferent student in her youth but later realized the power of math and computer science to solve important problems.
Katherine Taylor for Quanta Magazine
Introduction
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.
Kalai explains concepts of cryptography to doctoral students (from left) Spencer Peters, Surya Mathialagan and Lali Devadas.
Katherine Taylor for Quanta Magazine
Introduction
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.
Kalai has worked on ensuring the security of cloud computing and now studies how quantum computers affect that security.
Katherine Taylor for Quanta Magazine
Introduction
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.
“Cryptography was exactly what I was missing, because it deals with real-world problems,” Kalai said. “Today, cryptography is used everywhere.”
Katherine Taylor for Quanta Magazine
Introduction
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.
Next article
Does Nothingness Exist?
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/the-cryptographer-who-ensures-we-can-trust-our-computers-20230727/