Though their routes to computer science differed, ACM A.M. Turing Award recipients Shafi Goldwasser and Silvio Micali have forged a common path in the field since they met in graduate school. Goldwasser was born in Israel and got hooked on programming in college at Carnegie Mellon University. Micali was born in Italy and discovered his interest in the field at the University of Rome through courses in lambda calculus and logic. Now both at MIT (Goldwasser holds a joint appointment at the Weizmann Institute of Science in Israel), the two have revolutionized cryptography by working through fundamental questions and forging a link with computational complexity. Since their groundbreaking 1983 paper on probabilistic encryption, their work has transformed the scope of cryptography from encrypting private messages to strengthening data security, facilitating financial transactions, and supporting cloud computing.
What drew you both to the field?
SILVIO: I started in physics and switched to mathematics. Then, toward the very end, I took two courses in discrete mathematics. So I switched to theoretical computer science and went to Berkeley, and that’s where I met Shafi.
SHAFI: I went to college at Carnegie Mellon in applied mathematics. At the time, they didn’t have an undergraduate degree in computer science, but there was a way to minor in computer science. When I graduated, I went to California for an internship at Rand as I was interested in AI, and one weekend I drove up with a friend to see Berkeley on a very sunny day. It was beautiful—green hills, bright blue skies—so off I went to Berkeley. At first, I was taking general courses, but then I ran into a group of theory students, one of whom was Silvio, and they sort of took me into their midst. The subject matter was appealing, but it was also a social thing—the theory students were an excited and an exciting bunch.
SILVIO: By contrast, when I landed at Berkeley, it was raining, and I discovered that I couldn’t speak English. I knew there was a shuttle to campus, but I had to ask six people before they could grasp what I wanted. But things lightened up once we formed this band of brothers. This aspect Shafi mentioned about sociability, it’s very relevant, because at the end of the day we constructed a theory of interaction, so whatever attracted us to this interactive thing was going to grow into a professional interest, as well.
You ended up having a common advisor, Manuel Blum.
SHAFI: The turning point was a course by Blum on computational number theory. At the end of the course, Blum asked this question about tossing a coin over the telephone. And somehow the idea that the combination of randomness, interaction and complexity of number theory problems could be used to emulate simultaneity in communication—to make it seem like flipping a coin on one end of the telephone and revealing it on the other hand happened at the same time rather than in succession—seemed unbelievably profound and exciting to me. And I think it’s true about theoretical computer science in general… you use mathematics to solve real-world problems, but you’re not really bound by the rules and conventions of classical mathematics.
The coin toss problem sounds similar to the game of mental poker that led to your 1983 paper on probabilistic encryption.
SHAFI: Mental poker had been posed before, but in that protocol, partial information could leak about the cards. We were working on the problem of how to play poker so that all partial information is hidden. I’m not really a card player; it was all very abstract. We had this idea of using quadratic residuosity, a hard problem from number theory, to code cards. So say the card is a seven of spades; we can think of its name as a binary string and represent each bit of this string as either a quadratic residue or Q-non-residue chosen at random. We proved that all partial information about the cards was hidden by this representation. It was almost an afterthought to say, "Wait a minute, there’s a new public encryption scheme here where you can prove very strong security property; no partial information leaks."
"This often happens in mathematics—you start with something concrete and generalize, and in the end you get this beautiful theorem."
This often happens in mathematics—you start with something concrete and you generalize, and in the end you get this beautiful theorem. But you don’t start by saying, "Let’s think of a scheme that satisfies this security definition."
SILVIO: I agree that motivating examples are a big propeller for science. But we chose a very difficult problem that is a mixture of not only encryption, but also how you deal the cards after you encrypt them and how you make sure that the cards are getting a random shuffle. We were fearless, but we were also lucky.
SHAFI: In a sense, what people remember is probabilistic encryption. But there were also all these sub-contributions that made their way into later larger bodies of work on protocols and randomness.
One of the most powerful contributions was the notion of indistinguishability.
SILVIO: Computational indistinguishability roughly means that if you have limited computational power, being human, you cannot even distinguish between two things although they are very, very different from one another. In the context of encryption, this implies that if you are not the intended recipient of an encrypted message, not only can you not figure out the message in its entirety, but you don’t have any inkling about its contents.
SHAFI: Nor can you figure out relationships between different messages.
Indistinguishability also played a role in your later work on zero knowledge interaction proofs and zero knowledge computations, where the notion of being unable to distinguish one reality from another is the key to analyzing secure protocols.
SILVIO: Well, first of all, leaving zero knowledge aside for a moment, what we created is a new kind of proof. Proofs are the most frustrating things. They’re not fun to write and they’re not fun to read. They slow you down. So we transformed them into a game. Say I claim a certain theorem to be true. Then I convince you that the following game has the following special property: if the theorem is true, I can win all the time. If the theorem is false, you win at least half of the time. Now we play, and I win. We play again, and I win again. Assume I win 20 times in a row. Then suddenly this very esoteric, long, tedious process of verifying becomes, if not fun, at least quick and interactive.
This is a transformation in two senses. First, since the proof is interactive, what convinces you is that you really played this game with me and you lost every single time. Here we are already gesturing toward zero knowledge, because that doesn’t mean you can prove the theorem to somebody else. Second, there is this probability of error. We played 20 times, but maybe with a chance of one in a million, you would have not caught me if the theorem were false. But if we play 30 times, the chance is one in a billion. And if we play 300 times, the chance is one in the number of every elementary particle in the universe. So all of a sudden this probability is so miniscule that, for all practical purposes, it can be equated to zero.
"Proofs are the most frustrating things. They’re not fun to write and they’re not fun to read. They slow you down. So we transformed them into a game." How did that lead to zero knowledge?
SILVIO: Zero knowledge interactive proofs are a way in which you can prove a theorem to me so that I know the theorem is correct, but I have no idea why. To accomplish this, you interact with me in a way such that if I knew the theorem were true, I could construct a virtual interaction with you that would be indistinguishable to me from the true interaction.
SHAFI: It’s called the simulation paradigm. It was already in the probabilistic encryption paper as a proof method, but here it actually becomes part of the definition. If you think about this interview, the fact that you are talking to us convinces you of the fact that we are real. But beyond that, you could probably have surmised what we’ve said from all the papers we have written.
So a zero knowledge conversation is a conversation that could have been simulated so well that it would be indistinguishable from a real conversation.
SHAFI: That’s right. If you can’t distinguish between a true interactive proof and a simulated proof, you can conclude that the true interactive proof gave you nothing you couldn’t have obtained yourself, besides knowing that your questions were actually answered by a real prover. So, the fact that in a true interactive proof the real prover answers your questions convinces you that a proof is correct but gives nothing else.
Join the Discussion (0)
Become a Member or Sign In to Post a Comment