How Shafi Goldwasser Co-Invented Zero-Knowledge Proofs

Transcript

The definition of zero knowledge is in some sense that at the end you will believe what I claim, but you will discover nothing else. In the beginning when we were trying to define these interactive proofs, we wanted to make sure that we talked about the prover as all powerful. And over the years the prover was assumed to actually not have much computational power. Part of the reason why you knew he couldn't cheat you is because he wasn't smart enough to do so because he was computationally limited. >> I've always kind of wondered why the notions of zero knowledge and interactive proofs kind of came together. >> The answer is privacy. The reason for introducing the interaction and the randomness was because this was the way to obtain privacy. [music] And only later, this was a paper by Goldreich, Micali, and Wigderson where they showed that you could actually prove more using

interaction and probabilism. >> Do you think cryptography currently is rigorous enough? >> So, in terms of the role of rigor, I think that >> Hi everyone, and welcome to First Principles, a series by the team at a16z crypto. I'm Tim Roughgarden, I'm the head of research at a16z crypto, and today we're talking about a fundamental breakthrough in cryptography. How you can prove something is true without revealing why it's true. So, this insight gave rise to zero knowledge proofs, one of theoretical computer science's most powerful concepts. What began as a theoretical advance is now

one of the fastest moving areas in crypto powering everything from privacy preserving systems to rollups to verifiable computation. Our guest today is Shafi Goldwasser, a Turing Award winning cryptographer who, along with Silvio Micali and Charles Rackoff, invented zero knowledge proofs. Joining us is Justin Taylor, a16z crypto research partner and associate professor of computer science at Georgetown University. Together, we explore how seemingly toy problems like mental poker, led Dr. Goldwasser and her co-authors to define interactive proofs and zero knowledge, and how that work in turn opened the door to deeper results about what can be

efficiently verified, including surprising theorems like IP equal Pspace and probabilistically checkable proofs, which show that complex computations can be checked by inspecting just a few random locations of a proof. And ultimately, we'll talk about modern blockchain systems powered by SNARKs. Here's our conversation. >> So, Shafi, welcome and thanks so much for uh taking some time to speak with us today. So, there's um two things you hear a lot about when people discuss blockchain technology these days are, on the one hand, SNARKs and on the other hand, privacy in the sense of zero knowledge. These two ideas share uh to a large extent the same intellectual

roots, uh which is work on interactive proof systems. And so, I thought maybe that would be a good place to start the conversation. So, for example, there's the famous GMR paper, Goldwasser, Micali, and Rackoff. And would love to just hear a little bit about, you know, what was the milieu like at that time? Like, why ask those questions? Why work on those problems? How you came to them and how it came about. >> So, certainly there were no um SNARKs. There were no contracts or blockchains or clouds or even the World Wide Web. I was a graduate student at Berkeley, and um my advisor gave a talk uh class actually on cryptography and and number theory. And it was mostly about number theory, and the last two lectures were about cryptography.

And he um talked about the RSA, which is is public key encryption scheme at the time was essentially the only one. And he also talked about this paper, which was how to play mental poker. Which was essentially by the same RSA guys, maybe in a different order. And they were considering the following problem. There are people two people sitting in different parts of the world and uh over the phone a they were going to play cards, but they didn't have any cards. So, how were they going to do that? How were they going to deal a deck of cards? And um after the class, you know, me and Silvio we were got kind of excited about this question. I don't know why because I I don't think either one of us was much of a >> [gasps] >> a card player. The truth is I didn't

even know there were 52 cards >> [laughter] >> cuz where I came from nobody played cards at the time, at least. What does this have to do with zero knowledge and with interactive proofs? There was a an idea for protocol for how you define a deck encrypted cards and how do you deal a card and that there was some interaction in it. It was a nice protocol. There were definitions of what it means to play securely and according to the rules of mental poker, but the way that you verified at the end that you followed the rules was that both players had to open everything up. So, they show what they really encrypted, each move, the messages they sent, what do they correspond to in the real game and so forth. And then somebody told us that that's not really the way poker is played and in a sense you play, but

nobody knows necessarily the you know, when the cards were face down, what was going on. So, the question came up, how do you prove that you've done the right thing even though you don't reveal the cards? So, how do you prove that you're dealing cards properly a even though you haven't, you know, in some sense revealed everything about what you've encrypted and the randomness used to encrypt and so forth. So, we came up with a protocol for a very specific problem which was to prove that the card was properly opened and that used number theory. So, it wasn't like a general showing that everything can be done in zero knowledge, but there was a specific language, you know, a specific problem, but in order to do that, we

realized that first of all we needed interaction in order to be able to prove something without revealing everything. We needed to allow probability of error. So, there was some sort of randomness involved both in equipping the cards and in proving to you that something was done properly. So, there was some chance that I was going to cheat you. We accepted that because the probability was very small. And so, we needed to modify the notion of a proof, that a proof could be interactive. There would be sort of a prover and a verifier. Prover is convincing the verifier of something. Second of all, the verifier was willing to accept a small chance of error.

And that enabled not revealing everything. But, we had a definition of what does it mean not to reveal everything. We need to define what it later became as the definition of zero knowledge. So, all these aspects were to show something that in retrospect may seem esoteric than it was our entire life because this was our paper to be. Okay, then it started getting generalized because the question was, can you do more than one example? Okay. One, can you have something that doesn't really sort of very strong sort of perfect zero knowledge? And the definition of zero knowledge is in some sense that at the end you will believe what I claim, but you will discover nothing else. Okay? How do you define nothing else? There's sort of an operational definition which is

everything you could have done before we engaged in this interaction where I'm proving you a statement, you could do afterwards. And the way to show that everything you could have done computationally before is what you could have done after is something called the simulation paradigm. You have to show that whatever knowledge this verifier has afterwards, you can simulate that even without the prover and the interaction. So, I I this is a a mouthful, I I realize. But, anything This was the beginning. >> And and did it all Did it come together quickly? Were there parts that were sticking points for months or Tell me a little bit more about just the process of getting from the question as posed by your advisor to what we all read in the in the published paper.

>> So, the advisor didn't exactly pose the question as we solved it. It was It was this mental poker paper. And then he showed that there was another paper actually by Lipton who showed that there's a bug in it, that there's one bit of information about the cards that can be revealed. So, then it was okay, how do you do it without the bit of information? There was a problem in the mental poker solution and it was in substance in retrospect an act of really divine spark to realize that it was all about how do you encrypt a single bit of information and how do you prove that that bit is, you know, let's say zero or one without revealing anything else.

Were there bumps in the road? That was your question. It was very exciting because ideas just came one after the other and we managed to come up with an interesting definition and prove it. But of course you've got, you know, if a graduate student is looking at this, you've got an advisor, right? And they ask you questions, well, how about this and how about that? And then you realize you haven't thought about it and you you do more. We started this whole thing that was just a mental poker paper, but then we generalized that to this idea of zero knowledge proofs more generally and we wrote it. We were very excited. This paper was submitted like six times and we kept getting rejected till we got to this this zero, you know, zero knowledge interactive proofs with Charlie Rackoff also.

So there were certainly bumps, but we were very determined. I'm a lot less determined now, you know, if my paper gets rejected once or twice, they but then it's like, no, we have the right definition. This is very interesting and we were going to it was like a war in substance. It's a terrible thing to say, but >> No, I think that I think there's lessons for, you know, the next generation of PhD students around tenacity being a very important part of of one's trajectory right? >> Absolutely. I don't know if you experienced it or or you Justin or maybe think life was easier. It wasn't life was difficult, but if every time you get a rejection, if you assume that the people rejecting you, they know all, then you can't go further. But somehow we didn't assume and I got to give a lot

of credit to my co-author, to Silvio, who's also very combative, so it was you know, like two [laughter] against one. Yeah. >> Yeah, something tells me the situation remains similar today. What one thing that I find fascinating here, a traditional metaphor to kind of explain the notion of interactive proofs to people is, you know, one mathematician is claiming some theorem is true to another mathematician and rather than writing out like a 50-page proof on the board right there, you know, they have a a conversation. So, that feels like a less frivolous, more formal kind of application than poker, maybe, depending on your your taste, I guess. But, then there's no notion of private or secret information. I've always kind of wondered why the notions of zero

knowledge and interactive proofs kind of came together. It seems like the answer might be poker. >> [laughter] >> No, the answer is privacy. It's because the reason for introducing the interaction and the and the randomness, you know, the probability of error was because this was the way to obtain privacy, which was, you know, the poker example. But, then more generally you ask, "Can you prove, for example, that a composite number is a product of two primes that are of a particular format and in without just giving the factorization?" So, doing some sort of interaction. And only later we realized that we can actually prove statements and this was a paper by Goldreich, Micali, and Wigderson where they showed that you could convince someone that two graphs were not isomorphic to each other, which is a problem which is at

the time we didn't know any other way to do do it. We didn't know how to put a a short proof adjust proof then you. But, there was no zero knowledge involved. So, the realization that you can actually prove more using interaction and probabilism came after the zero knowledge example. And I just want to say one more thing is that you're right that it's natural to think of one mathematician proving a statement to another mathematician. But, the mathematicians didn't like this notion. So, when you talk about interactive proofs to mathematicians now, we're talking many, many years later, they accept it. But, at the time when I would I gave a talk, I remember some colloquiums and I called this an interactive proof, they said, "This is not a proof." Because a proof is something that has zero error.

Now, of course, in reality, many proofs and mathematicians write sometimes they're completely incorrect in the sense that the statement that they prove is incorrect, but often they have mistakes. I mean, these are just very long proofs or if it's a complex theorem, and it's very difficult to to pinpoint the error. So, I I think that it couldn't have come as a way to propose to mathematicians, "Hey, here's an interesting new way to define You had to have a justification for it, which could which was privacy, and then ah, you can actually convince of more difficult a theorems, which we don't know how to do with the standard proof.

>> Yeah, it's it's fascinating. I mean, my personal journey to interactive proofs, you know, started with um forget zero knowledge, right? IP equals Pspace and all of that, and it's fascinating to hear that, you know, you wouldn't have come up with that notion of interactive proofs without privacy and zero knowledge being like kind of the first-order consideration. >> So, there is another proof system, which came a few years after us, but we got published at the same time because of we got rejected all the time, called Arthur Merlin proofs. And Arthur Merlin was really a one round. It was a verifier and then a prover. A verifier was Arthur, and prover was Merlin, but it was a a simpler notion was that it wasn't considering lots of rounds, and second of all, that it didn't talk about privacy, and third of all, that Arthur was just someone who was tossing coins.

Where for zero knowledge, often the verifier tosses coins, maybe, but then they send a message where the prover doesn't know what the coins are, and that's in the sense is a is a power of the verifier. So, he checks to see whether the prover will do the right thing. So, I I just want to say one more thing. We're talking about proving that a theorem is correct. Much of the what start as I understand, the applications are more that the prover knows something that the verifier doesn't. So, for example, I prove that I know a password. Or I prove that I've signed a contract and I I have the signature key. So, it's not so much that that necessarily that is some theorem is correct, but it is that I know the proof of that theorem.

But by me knowing the proof of that theorem means that the the proof exists. Another thing is that, okay, let's say it started with zero knowledge interactive proofs. It both interaction and probabilism and zero knowledge. But then the research kind of split into different directions. There were all the complexity theory people who didn't care about privacy. They got very excited about this idea that this interaction allows you to prove harder and harder statements, which correspond to a more and more complexity classes from standard complexity theory. And then uh it went even in a much more interesting direction where people said, "Okay, do we actually need interaction?"

And it turned out that uh it is possible to sort of take a standard non-interactive proof, like just a standard proof, no zero knowledge, no randomness, no nothing, and to rewrite it in a different sort of in a using some sort of error correcting code, so that now if there was an error in the original proof, the standard classical math type proof, uh there would be lots of errors in the new one. And the reason that that was good was it meant that you could sort of just probe this proof in a random location, and you would land on an error if there was any error at all. You know, that opened a whole um new dimension to sort of a new notion of a proof where you could do local checks.

You could just poke it in a random place, and you can talk about how much you read, which is a lot less than reading the entire proof, and what is the probability of error in it. And I think, you know, it was an object that was easier to study for traditional combinatorialists, computer scientists, and so forth. And that actually leads to SNARKs, right? Because you've got this long proof. It's too long, okay? And uh if you want to really talk back in the world of applications, where is that long proof sitting? You know, it doesn't sit anywhere. You'd like to be able to somehow compress it and send it, and still have the verifier be able to poke in it and find the error.

And now we go to this world where we have hash functions and we have these Merkle trees, very complex hash functions where these proofs can be compressed and yet you're able to kind of poke at them and discover an error with high probability if there was an error in the original uncompressed version. >> So that's a that's a great summary of sort of many many years of research by the theoretical computer science community. Let me rewind a little bit. You mentioned about how there was this branch which took a purely complexity theoretic view of interactive proofs and just like Justin, that was the first way I encountered it, right? It was, you know, probably the complexity theory book [laughter] of Arora and Barak or something like that. Um you know, the proof of IP equals Pspace and so on and

so I'd love to get your thoughts, you know, in particular the sumcheck protocol which shows up in those proofs is one of the main paradigms that's being used today to build SNARKs. And so, you know, I'd love to just hear where were you when you heard, you know, about whether it was IP equal Pspace or one of the precursors, when you heard about sort of the sumcheck protocol. Were you surprised that interactive proofs were as powerful as they turned out to be or just again take me back to to sort of that moment in time for you. >> So we knew it was more powerful than standard proofs.

There's an intermediate segue a little bit and that was that we had one prover and then we there was a work that I was involved in when we where we said, "Okay, what other proof systems are there?" So we said, "Okay, how about if there are two provers?" So there are two people who have written a proof together and there's one verifier. We had the story and that is they're like suspects of a crime, the crime being that there's an error in the proof. And they're sitting in different rooms and you ask questions from one to give you answers and you ask a randomized question from the other to give you answers and somehow you can check the consistency between them in order to verify that they're not cheating.

There was this paradigm and the question was, is it more powerful than one prover or not? Uh and then uh Noam Nisan, he was a postdoc at MIT, and a professor at MIT, and he came up with a protocol to show that the permanent problem, which is a well-known problem that is hard and it's uh hard to be space, okay? It complete. Uh he showed how to use two provers, and it's a sort of a sum-check protocol to prove that a prover could prove to verify the value of the permanent.

And a lot of the ideas of the sum-check are in that protocol. But there were two provers. And I think then he went off to travel in Brazil or something. I don't know, somewhere. And while he was gone, the rest of those guys, Fortnow, Karloff, and Lund, so the paper is FKL then, they figured out how to make that two-prover into one-prover. And it was for for the permanent. And this is all going hap- happening all It's kind of a this very quickly. Once they got that and everybody knew about it, then Adi Shamir from Weizmann managed to take it to the last stage, which was IP equal to Pspace. So we I was at MIT, we had a seminar on these things. It was surprising uh because these ideas are not immediate at all. They are complex.

They are beautiful. Uh they're still used today, as you say, in in concrete protocols that for blockchains and so forth. But I was not removed from it because it was all happening uh same group of people were postdocs, Princeton, Berkeley, and MIT. But it it was surprising, but you know, when you start hearing things one step at a time, you sort of break that barrier of thinking that you just are barely scratching the surface, and then it seems that there's a lot more. I mean, what is really surprising to me is that you guys are actually using it. >> Justin, do you want to talk a little bit about that? Or >> [laughter] >> Like at a high level, what's sort of unique about sum-check for the purposes of concretely performance SNARKs?

>> Yeah, so this this path, the historical path I I always find fascinating, right? That Shafi just recounted, right? It went single prover interactive proofs from from Shafi's paper, and then multi prover interactive proofs, and then PCPs, and then snarks were, you know, kind of first built out of PCPs. But, you know, from a present day perspective, that path is a is especially curious because, uh, you know, we have something called the Fiat-Shamir transformation, which there are open theoretical questions about its security. But, you know, practitioners are sort of happy to to use it. Uh, >> [snorts] >> it's just a generic way to get interaction out of protocols, which means if you want to build a snark, you don't have to go through PCPs, necessarily. That's just the historical

route, right? And in fact, it sort of doesn't make sense to go through through PCPs because PCPs are non-interactive, but then when you compile those into a succinct argument, the interaction comes right back, and then you Fiat-Shamir, right? And so, what what really makes sense from the present day perspective is to start with something like an interactive proof, or a two-prover interactive proof, never go through PCPs, and just remove the interaction once at the end of the day with Fiat-Shamir. This has been my personal path to, you know, starting working on SumCheck and finding it to be a beautiful, simple protocol, and and useful for really simple problems, and over, you know, years figuring out it's sort of like the perfect hammer that actually applies to everything out there. So, I always find that route fascinating. It seems like the the PCPs

just like grab people, like you mentioned, and were somehow easier to think about, but then if your end goal is the snark, it's actually, you know, like a stepping stone you just don't need. And so, to answer Tim's question briefly, the SumCheck protocol has a lot of rounds of interaction in it, and it just seems to be a very good tool for forcing the prover to actually do work, so the verifier doesn't have to do the work, without paying a lot of overheads. My personal intuition is, you know, cryptography is expensive. You know, if you need to commit to a lot of data, you're going to be doing a lot of, you know, hashing or group operations or what have you.

You need to commit to some data to keep the verifier nice and fast and succinct, the proof short. But you'd like to kind of use that sparingly. You commit to more data, it means it takes longer to commit to. It also means you separately have to prove that the data you committed to is like not random garbage. So that takes even more time. And so the sum check protocol just uses interaction to the extreme to use that cryptography, those commitments really, really sparingly. The historical root has just been fascinating. I repeat, PCPs, they typically use like univariate polynomials in their guts. The reason is is it lets you keep the the proof short even when there's no interaction to help you out. But then if you have a lot of interaction, like multivariate polynomials are really nice cuz you can kind of have one round of interaction

per variable. And so, I don't know, this PCP root just, you know, took the the community towards certain techniques and we've now sort of come full circle back to the the beginning. >> To me, what's really fascinating about this development is the power of abstraction. As you said, why would we be talking about zero knowledge interactive proofs early on? And the poker is just a curiosity. But after that, you know, really the understanding that there's something fundamental that's going on here and asking, do you need interaction? How much interaction do you need? How do you get it to do it without interaction?

And also, even with the sum check, so you think about it as it's efficient, it's good, you know, as you were describing it, it's a good way to do things. But if abstractly speaking, where does that come from? Where it comes from is that if we generalize from poker and then proving that you know a password, proving that a contract is a valid contract, more generally, we talk about proving that a computation was done correctly. So there's some algorithm or Turing machine, whatever, and then it takes some input and then it provides some output. And you want to convince someone that the output is the output was correct without having them to repeat the computation themselves.

And the sum check in some sense you can So, there's this abstraction that everything is a computation. And now, really the question is how do you prove to someone else the computation was done properly? And then you realize that if you look at the rules of the algorithm or the rules of the machine that the algorithm is running on, you know, you can express the rules sort of like step-by-step as a sort of algebraic formula that each rule was computed from the data from before. You You did some computation, next piece of data, computation, next piece of data. And this can be expressed already as as you say with polynomials, okay? On variables with the various Those are the actually have value, which is the data. So, there is something you needed to think about computation of

a Turing machine or a circuit in order to even lay down this thing that later will become a subject. So, what were you summing? You were summing the the this formula and over all the steps of the computation. And it's fabulous in my mind that it's this going that to that abstraction that you'd like to summarize computation as an algebraic formula that at the end actually is also the right thing to do for a specific concrete application. >> I agree completely, right? It's like if you're looking at the quote sharp sat problem, that is counting the number of satisfying assignments to a formula, it's like sum check is the perfect fit cuz the sum is you're just summing over all possible assignments of, you know, does this satisfy the formula or not,

right? And when, you know, I've read about sum check in Arora and Barak's textbook, I was like blown away. It's so so beautiful, right? But you might think, oh, we moved away from that. That was just a clean abstraction. But actually, one of the prevailing trends in SNARK design today is to do exactly what you just described of writing out a computation transcript step-by-step-by-step using a virtual machine abstract like a simple CPU, and then, you know, applying some check to prove that every single step was done correctly. Now the way we apply some check doesn't look like the same kind of thing as summing up all satisfying assignments of a formula, but otherwise it's literally exactly what you said which was the way of thinking

when this stuff was worked out in the you know late 80s early 90s. So the similarities and like the small deviations are fascinating and compliment each other. >> I have a question to you. So Canan? >> Yeah of course of course. >> As you say it started both about the interaction probabilism and privacy at the same time. And then the succinctness came in and eliminating the interaction. But from what I understand they call ZK snarks but there is no zero knowledge there. So it the privacy is kind of gone is not interesting or it just cost so much or it's going to come back or what is it?

>> I'm talking to two two of the people in the world that are most annoyed on a daily basis about this this particular terminological error. >> Yeah yeah the snark community whatever name you want to you want to give to the community today uses ZK basically to mean succinct like you say possibly with actual zero knowledge you know with like you know privacy possibly not. Some applications need the privacy and and some don't. Some of the kind of most popular applications today don't need it and that's big reason why you you see a lot of these snarks that people call ZK proofs not actually being ZK right? So if you want to just like scale blockchains so untrusted parties that

exist off chain are posting proofs to the blockchain that they did a bunch of computation correctly so that you know all the blockchain nodes only have to check the proof and don't have to do the work from scratch. There's no privacy necessarily needed there right? Um you know but if you talk about like Zcash you know private currency transfers now you do need privacy and of course, they are using something that that is ZK. Now, you can ask, well, like the SNARKs people like to use, can they be made ZK, and people just aren't bothering? That's a little bit nuanced. I think the short answer is they all can be made ZK in principle. Some of them would experience more performance overhead if you made them ZK than others. So, I think, you know, two things will happen is my prediction. One

is the privacy applications will kind of become more important again over time. Zcash was early, and then privacy became less of a focus, and it'll come back. And so, then everything will have to be ZK. And two, I think the sort of the techniques that will kind of win out will just magically be ZK without the overheads. So, that that's how I think it's going to go. >> I I want to say one other thing that I think is kind of an interesting development over the years. And that is that, uh, in the beginning when we were trying to define these interactive proofs, we wanted to make sure that, uh, we talked about the prover as all powerful.

We show that these, uh, uh, proofs are correct or very small probability of error regardless of how strong the prover is. And over the years, you know, there was, uh, first it was Cripole, Chaum, and Brassard, where they had this notion of an argument where it was an interactive, but not proof interactive argument where the prover was assumed to actually not have much computational power. Part of the reason why you knew he couldn't cheat you is because he wasn't smart enough to do so because he was computation limited. And then Silvio did the same in order to get to the SNARK idea.

Conceptually, it's very it's fascinating. So, it might be that the theorem is wrong. Okay? That you're proving. But, what convinces you that it's okay is that there is no prover that can convince you of the opposite. So, in some sense, one thing is this start with a mathematician. The proof has to be 100% correct, okay? Then we said, you know what, there's this probability of a but we can quantify it and we can show that it's one in a googol's number. You know, it's extremely small. And then we say, it's correct with respect to anybody that can work in a reasonable amount of time. So, there's no one who can point to a in some sense a a mistake, you know, so from as far as we are concerned, it's good enough as

correct. So, that's kind of a conceptually an interesting concept. The fact that our reality is indistinguishable from a correct reality with the computational resources we have, and therefore it's good enough to think of it as as correct, is a paradigm which has led to a lot of efficiency and a lot of improvements, but it is definitely not the same. >> Yeah. >> Uh [laughter] as as my assumption. Yeah. >> Yeah, convincing proofs of false statements exist, but nobody can find them. Um I mean, I was pretty far along in my own career when I started looking at proof systems for these statements where solutions trivially always exist, but they they're presumably hard to find. And yet, you were looking at at

such things, I guess, from day one for, you know, proving knowledge of RSA secret keys or something. >> This is one more step. It's not that the proof is hard to find. Maybe it's it's not even correct. >> Yeah, it's like layers of an onion, right? Do you care about problems where the solutions always exist, but the question is does the prover actually know a solution? And then there's are you going to let convincing proofs of false statements exist, but no one can find them, so it's okay. As I said, you have different flavors and layers, and I guess that's what leads to a beautiful theory. >> So, it's interesting to me that it hasn't really gone into the algorithm's world. In Okay, so worst case, you say an algorithm will run in a certain amount of time, means that in the worst case. But people talk about, of course,

that with respect to certain probability solution might be much faster. So, in some sense, there's a similarity there. If you can't find instances where you could talk about not being able to find an instance where this algorithm runs more than a certain amount of time. And it's probably true in practice for many problems that the instances you run into are all going to be okay. So, as a cryptographer, I immediately think this is a is a question of playing with an adversary. The adversary is trying to tell you no, your algorithm runs slower than you say. But, if the adversary is bounded and he can never do that, what's the difference between having an algorithm that runs quickly except in some very bad cases which no one can ever come up with versus a much more complex algorithm whose worst-case

running time is slow. So, it's interesting that's sort of very natural for cryptographers because there's an adversary and the adversary has some computational powers and you're fighting that adversary and if you can win against that adversary, whether it is convince them something's correct, maintain privacy, all is fine. Whereas, it you know, that kind of thinking could be adopted in other fields, but it hasn't. >> Yeah, the closest analog I can think about that it comes to mind is smooth analysis. >> That's true. >> Which is not a computational concept. It's more of a statistical concept that says that the instances for which say the simplex algorithm is slow are, you know, measure zero or sort of very rare.

>> That's right. >> Um and, you know, in practice, it's kind of a little bit hard for humans to come up with those instances. Like, someone like Mihalis Yannakakis will write like a brilliant paper sort of, you know, giving the bad examples where local search takes an exponential amount of time, but I've never seen a computational treatment of it. So, that would be that would be fascinating. So, maybe a couple reflections on on this great conversation so far. So, one would be just the kind of non-linearity of the ideas. Uh, so, you know, when you read a textbook, right? All the concepts are presented in this very logical manner and it's as if it could have just been discovered in that exact same way.

And so, one thing we've heard from, you know, your story about interactive proofs, zero knowledge, succinctness, all of this, um is that the way it's written down in the textbook is generally not the way it was discovered. >> Absolutely. >> Um but then even more fundamentally than that, the ideas are not even linearizable. I mean, it's really sort of a web of concepts that are connected to each other in in very rich ways. You know, even things that were discovered together by you originally, Shafi, you know, they seemed like they went together at the moment. Maybe it wasn't clear why they had to go together, but over time they keep reoccurring sort of in the in the in the same room, if if you will. So, this idea that there's many many ideas that are connected to each other and that the discovery process, I don't want to call

it a random walk, but it may not be the same path of discovery, which is the one that you you tell later in your in in a textbook. And then the second reflection is about this interplay, let's say between the specific and the general, or even maybe I'd say the toy example and the and the general theory. Um and it's funny because, you know, Chris Dixon, who's, you know, managing partner here at a16z crypto, I mean, he likes to talk about the next technology is going to look like a toy. So, this idea that something that's a toy is actually going to become something very general and powerful. I think you see that theme again in in talking, for example, about, you know, poker.

But then a big part of our job, you know, as researchers, as theoreticians, is to say fundamentally, what is this really about? And at the same time, so you can think simultaneously about very toy examples and very general theories. And indeed, you know, the notions of reduction and completeness and complexity theory, arguably, is about exactly this. The idea that a single problem can stand in for an infinite class of problems. And I'll I will finish this with a question, Shafi, just about sort of how you think about this interplay. Because I don't know about your experience, but when I talk about what I do to people who, you know, are far from what we do, far from being mathematicians or theoreticians, they're always shocked when I talk about it being an extremely creative endeavor.

So, you know, I compare it, you know, more to, I don't know, [snorts] someone who's writing music or or designing a sculpture or or art, or something like this. As opposed to being some kind of very, you know, clinical, goal-driven activity. And so, I just curious your thoughts, Shafi, about like is there a role for is there an importance to kind of playfulness of toy examples in the process of working on, you know, in your case sort of very deep and fundamental theories. >> That's a very interesting question. First of all, I think that researchers are different. Different researchers are different. Some people cannot make any progress without seeing an example. So, if you're going to tell them that there's this thing called interactive proof and there randomness and rounds, they don't know what you're talking

about unless you show them a particular question like is 15 equal to 3 * 5 without giving you three and five, okay. For me specifically, that's part of the question. I need a narrative. We'll get to the creativity in a minute, but the question is also about motivation. What makes you work? And underlying in your question about creativity is that maybe people when they think of mathematicians or theoreticians is that they have a problem and they know know how much mathematics and then they try to apply the the mathematics and they they've somehow superior skills, technical skills, and they're able to apply it and solve the problem.

What makes more sense to me and what has been my experience is there has to be first of all a story in your head. I definitely need that. It's it's not just there is this problem I need to solve. The problem is more of a narrative and now you can attach to it a specific math problem. So, a narrative being maybe that you want to play poker. There's this famous story that Manuel Blum also told us is Alice and Bob and they live in different cities and they want to they have a dog and the question is who gets the dog. Is they have to flip a coin. How do you flip the coin over the telephone? So, there was a story that these two people, they want to flip a coin over the telephone. And now you can start thinking how do you do that? So, for me

a narrative is is very important and I would assume that uh in the blockchain space, there's definitely the narrative, which is you have this ledger, you want to post things, you want to be able to have smart contracts or what whatever that's a narrative also. That but that's not a math problem. From this you can define a math problem and now you can talk about techniques to to find it. Now the question of creative process, how do you solve it, right? Obviously it's creative. I mean how are you going to do it otherwise? I mean it's it's the usual thing, right? If everybody can do it, there would be no need for us, no way to get our papers published and no ways probably to make a business that's profitable. If everyone can do it then there's no extra. So that's that's creativity. For me I need to be in a space where nobody,

you know, somehow your mind can wander. For me that's seminars where people talking about their work and you at some point you you're there, you can't go anywhere else. Your mind wonders and probably there's some idea that has been described that touches on your own, you know, web of thoughts. I don't know what it is for you, but it's definitely creative. >> So changing topics a little bit, a question that Justin and I wanted to ask you was, do you think cryptography currently is rigorous enough? And I asked that because I went back to your Toring Award citation today and one of the things you're credited with along with everything we've been talking about so far is foundations of cryptography.

So in effect adding rigor, rigorous foundations to cryptography. And ever since we've seen this constant back and forth between what assumptions you're willing to make and what conclusions you're willing to achieve. Justin earlier referred to the Fiat-Shamir transform and there remains open questions about the security of that transform in different contexts. So let me hear a little bit about your thoughts on the on the role of rigor, on the role of assumptions of varying plausibility in cryptography as a field. >> Yeah, so in terms of the role of rigor I think that we were very much into defining things precisely and coming up with proof methods to prove things.

And I think that helped the field because uh uh rigor means usually that the definitions are shorter and easy to explain because they're equivalent to other notions and that enables the field to go forward cuz you can build on very strong foundations. Is it as rigorous now? On one hand, yes, because we have a a sort of a recipe book of how to define uh cryptographic security. So, we usually have to sort of model an adversary, that's the acceptable way, and that is to come up with that if you come up with a cryptographic primitive, you have to prove that it's secure in presence of this adversary. You have to define secure also for the primitive.

Uh and usually these proofs are reductions as reduction from this is all going to be secure if factoring is hard, if some other assumption holds. Maybe that two players don't interact with each other, you know, if they're in a multi-party computation. But it has to be a tight proof. You know, so in other words, if somebody comes and breaks the protocol, that will translate to a fast algorithm for factoring or it will translate to some leakage on the secret key or something like that, okay? So, we do have this recipe, which means that uh hopefully the students you train and people who work in the field uh follow it when they design a new protocol.

Now, of course, the field has become much larger and there's a lot more people. So, I'm not sure everybody checks everybody else's work. We when we were a small field and everybody read each other's works, it was feasible. And also because there's a lot more applications, obviously you want to cut corners because you'd like it to be efficient. And that's another incentive for not to satisfy this proof paradigm, you know, this reductions from assumption to primitive. Each case, you know, shouldn't be valued on separately.

I buy assumptions. So, I mentioned the factoring assumption, and I I think everybody here knows that uh in principle quantum computer can factor. I think it's much less in principle than it used to be. So, people are working on actually coming up with, you know, quantum devices that can address uh factorization, and they're starting to talk about constants and how many qubits are involved and so forth. So, we have moved from the factoring assumption to these lattice-based assumptions, which, as far as we know, quantum computers cannot solve in polynomial time.

Of course, again, those lattice-based assumptions might not be as efficient as you want for the blockchain space. So, for blockchain space, you might want something uh that's based on uh I don't know, bilinear pairs or whatever the favorite assumption is right now, which is, in principle, attackable on a classical computers. And people also invent new assumptions because they seem to be true, and it would make your protocol much more efficient. Like that the only way knowledge extraction supports it, the only way to solve the problem is a particular way, and you utilize that in order to get a very efficient scheme. In my mind, as long as they can state their assumption precisely, and show, indeed, that protocol is a quick security is equivalent to this assumption,

we're in this win-win paradigm. Somebody comes along, breaks the protocol, might be bad for AZ16, but it will be good for mathematics, we'll discover something new. And it also makes it less likely. But it's sort of the natural course of events, right? You want things to be efficient. You have to pay in um maybe not taking the strict the most ancient assumption out there that people feel confident. >> So, um you know, we we've been talking a lot about, in effect, ancient history, at least by computer science standards.

But you've been super active for your entire career, including the last many years. So in general, would love to talk about your more recent work, last 5 to 10 years. One idea um would be your work related to machine learning and related to law. And certainly one thing I'd be particularly interested in is just was working in these application areas, was it a pivot for you intellectually or to what extent did the same mindset that you could use in your work in cryptography and complexity theory that still poured over pretty well to these other application domains?

>> So I'll tell you two things that are related to what you brought up. So first of all, the law aspect, I was in Berkeley, I was the director of the Simons Institute and I had some law colleagues. And also before that I spent a year at Radcliffe and I had some interaction with Martha Minow that, you know, was just coming off being the law school dean. And we had an idea of teaching a course on law and cryptography or law and algorithms. Because it seemed like the whole, you know, again, going back to the narrative, the idea of trying to convince a judge of of your innocence, you could think of that as a a proof. Of course, you know, in law you really try to avoid putting precise numbers and

probabilities on likelihood of of something being true. Because once you put a number, one can sort of show that it's incorrect. And the notion of evidence is not the same as a proof. Um but it was interesting to talk to lawyers and to understand how they think. And that brought us to this place where we showed that even uh if you think about legal applications, one of the first works that I was involved in was about this question of wiretapping. So let's say they, you know, there's a a wiretap order.

The police is allowed or FBI is allowed to tap some phones and it turns out that after the warrant is taken away, they have something like 90 days to sort of open the files. So, the question was how do you really scrutinize all these wiretaps if there's no public access to it? We came up with some paper where we said let's bring together encryption zero knowledge actually blockchains where people would think of having all these wiretaps on the blockchain encrypted so that privacy is maintained till a time in the future where all of a sudden automatically it should be open. So, the cryptographic tools that we had uh

seem to uh be relevant to that question. Another place was you know, let's say the FBI discovers some sort of pornography ring or something using some software. And the software is proprietary and secret. And then they come to court and they claim in front of the judge that they have a lot of evidence that this person was engaged in illegal activity on the internet. Uh then the side representing the accused could ask to see the software. But once they see the software, the FBI cannot use the software anymore. So, there was a question how do you prove that you use a specific software without revealing the software? So, that was really proofs and zero knowledge, you know? Can you sort of convince another side that you used the software without

revealing the software? So, something very natural about using this in the realm of law. So, that's story one. Story two is just about the machine learning. Today that's all the rave, you know, besides blockchains. And um and there's really fantastic questions there. How did Why should you believe when, you know, uh chatbot, uh whether it is Open AI or Google or Meta or whatever, gives you an answer to a question. And when I say question, I mean let's say it's a math question. You know, there's a prompt which is a math question and they give you an answer. Why would you believe it? In fact, we know that you shouldn't really believe it um for the particular question you ask, on the average you should believe it.

Let's say 90% of the time. So, can uh a chatbot provide a proof, a mathematical proof, for the particular problem you ask that the answer is correct? And so, this is actually work with Steurer-Wills and Paradise and Guy Rothblum and Olga Meed, where we proposed to take the notion of interactive proofs and adapt it to the machine learning setting, where you would actually be training a chatbot not only to produce answers, which are correctly say 90% of the time, but for every answer to also teach them how to you know, how to produce proof. Not only learn how to solve problems, but learn how to come up with proofs. And it's been There's an algorithm

and it's been successful in some cases with some real language models. So, I think that there's a lot of uh future to the notion of of of proofs. Uh also zero-knowledge proofs maybe in the future, because you'd like to prove without really the training data. I mean, you can go lots of places there. And I think it's fascinating. You know, I was talking to a friend who's also seasoned computer scientist, and then they expressed skepticism about machine learning. And I was like, "You know what? We're so lucky that it's happening now rather than in 15 years, that where we can still use the things we know to make a difference.

You know, why don't you Why are you skeptical? Just go with it." So, I think that was sort of my motivation. >> Yeah, I think that's great. I mean, what There's frustrations in being early to a technology. There's a lot of moving parts and the models aren't sort of agreed upon yet, but on the other hand, you know, the impact you can have, like you say, while there's still time to make a difference with the trajectory of technology is >> Absolutely. >> is uh pretty amazing. It's It's one of the privileges of being a computer scientist, honestly, where just sort of new waves of technology and applications come up every, you know, decade. And every time that happens, it's a new opportunity for for all of us. So, >> Totally. And also, you know, maybe the the particular chatbot or the particular It won't be language models, it'll

something else will change but the idea that you should prove your answers if you can that's that should remain because we shouldn't believe you know everything we're told. You know so I came to that also narrative I saw some talk somewhere that I could use some chat box as my financial advisor. So I was very excited came home and then I had this whole big new plan of how to invest and then it turned out it was all predicated on the wrong understanding of some rule it's like what? >> [laughter] >> I had to go to lawyers and spend like 5 6 thousand dollars just to realize because I said do this he says no it's wrong he says no it's right chat GPT told me.

>> [laughter] >> Oh my goodness well you're definitely an early adopter Shafi I'll give you that. For [laughter] all the pros and all the perils therein so. Then I guess the lesson of the story is it all comes back again to proofs and knowledge right again. >> Yeah yeah I think that proofs are very fundamental. >> Fantastic well thank you so much Shafi really appreciate the time so. >> Bye bye have a good day. >> Talk to you soon. All right so that was fascinating and maybe first let me ask about something that you also alluded to kind of early in the episode which was around the origins of interactive proofs and zero knowledge proofs from mental poker and it's not the only

example one can think of of you know something which seems like a toy as it were leading to actually sort of deep theory so I don't know I mean what do you think is sort of playfulness and sort of toy examples kind of an important part of research for you? >> For me personally I'd say yes in a different flavor my work with the sum check protocol and recognizing how it's sort of the hammer for which everything is a nail in non-obvious ways came about from using it to solve like the simplest problems computer scientists study the subject protocol kind of directly solves them in interesting ways, and making the protocol run fast takes insights even in those simple settings. And then it

turned out that those exact same algorithms and ideas actually are completely general, and now we use those same techniques to prove arbitrary computations, right? So, um the power of of theory is like generalizability and abstraction, and often the the right thing to study is kind of the cleanest, simplest thing, which feels like a toy, and then it unlocks, you know, like the whole world of computation. Um I think poker is especially interesting because there's something sort of playful, almost frivolous about it. In fact, it's very complicated. I think it especially in computer science, there's a there's a long history of sort of, you know, playful topics that might not feel super important or or deep, sort of unlocking notions or ideas that then

become core to the the whole field. >> And one thing that you know, we talked a little bit about sort of playfulness and and toys, and you even used the word frivolous, but it's something that I think is not quite the same, but related. And two things we hear about a ton in crypto, right, are memes and narratives. And, you know, I often kind of say like there'll be like a famous sort of research paper, but actually what everybody knows is sort of the simple example on page two, right? So, like there's 1,000 times as many people that know the example on page two as have read more deeply into the paper. This is before my time, but I I wonder if like, you know, the graph coloring zero-knowledge protocol would be like an example that turned that theory into kind of a something that became a meme

that could sort of travel and affect quickly, at least relative to how ideas um traveled in the 1980s. So, I think that's also important. You know, you can prove results, you can develop a theory, but for the theory to be successful, you also have to communicate it to others. Other people have to get it. Other people have to be excited about it and want to build on it. And so, I think, you know, starting from sort of simple examples, I I think can can be powerful also in in that way and just helping communicate the essence of what the general theory is about. And then I was also kind of amused to hear Shafi literally talk about narratives being important for her in thinking about her research. The idea that you'd start with, you know, say the narrative of two people trying to jointly flip a coin

over the phone, sort of a problem basically given to her by her advisor at Berkeley, Manuel Blum. Or, you know, in in more modern times she said, you know, like the idea of a global, you know, distributed ledger being a narrative, right? And then the sort of the role of the researcher, a certain type of researcher anyways, is really turning that into something formal, into mathematics, having mathematical definitions, articulating, you know, what problem you're solving, what properties you want, and then, you know, formal protocols or theorems or guarantees. So, you know, inasmuch as we, you know, talk a lot sort of in industry about sort of narrative being important for, you know, projects to succeed, I essentially see that come up also for Shafi in sort of how theories how theories can succeed.

>> Yeah, somehow these clean goals can be very clarifying. The interactive proof model was sort of introduced as a interesting model in its own right, and we had the same notion of what is a mathematical proof for 2,000 years dating to the ancient Greeks, you know, you write your your proof in a in a book and someone can check it step by step. And this was sort of a natural generalization of it that at the time mathematician Shafi said hated. Cuz he he you know, even though mathematicians do have conversations with each other in the in the, you know, in the real world to convince each other of something being true or not, they ultimately, you know, prize these these written formal proofs. And so that the model came out, a natural model, but just there's the model. Some protocols

originally given, but nothing like this sumcheck protocol that that Noam told us about, right? And so somehow the the right model leads to the right protocol leads to all sorts of other stuff. And the it's the the stories along the way, right? Without the right model, you just don't get the sum check protocol, right? With um without the sum check protocol coming from a complexity theorist, you don't get the, you know, practical SNARKs that will ultimately, you know, uh underlie the world's digital infrastructure. >> And you're right, there's a there's often like a back and forth. Like maybe the first thing someone comes up with is an algorithm, and only then do you step back and be like, wait a minute, what This is a cool algorithm, but like what's the problem we're solving? And like why do I think it's cool? What are those properties? And then when you

write those down, you're like, okay, now let's start from a clean slate. If I think about any algorithm that might have those properties, is something even better than the one I came up with in the first place? >> Yeah, and uh I guess points to the the power of abstraction, but you know, without clarity and narratives or clear clear goals, you don't know what abstractions are the right ones and and things like that. >> You know, maybe the final thing to talk about around Shafi's interview. So she told a story or she alluded to the fact, and you alluded to the fact, that the GMR paper was rejected multiple times um before it's accepted. For people in the audience that, you know, aren't themselves researchers, right, it may look like all these classic results just sort of fall from the sky fully formed, right, and must have all, you know, been

famous sort of from day one, but there's really a process that goes on behind that. I think both on the part of the inventors or the authors in sharpening the clarity with which they explain their ideas and maybe coming up with more examples and, you know, having memes and effects to illustrate it. But then also I just feels like, you know, new ideas just take time to be absorbed. So why do you think that is? Like why are kind of really good new ideas hard for even the most seasoned experts to sort of, you know, recognize the first time they see it? >> So I think one one of the issues is experts always want to understand how something relates to what came before. I think if you look at the GMR paper, they have a whole bunch of explanations of, you know, how these model these notions

zero knowledge proofs and interactive proofs relate to like other things that they're just not related to at all. And it's clearly like reviewers were like, wait, how how does these things relate? Something's totally new and the fact that it's totally new almost almost works against it because you you can't point to like, oh, this is a clear step forward relative to something that came previously. >> Yeah, the easiest thing to understand is like here's a problem you already know and a result that improves in a agreed upon way over the state of the art, right? >> Yeah, yeah. >> if it's some new completely new definition that no one's ever thought about then people struggle with like is this a interesting definition? Is this a trivial definition? And of course, as you know, theoreticians their biggest fear is sort of accepting a paper that turns out to be like trivial in some

sense. So >> Right, right. >> I don't know, you know, to minimize errors of that form, you often wind up perhaps being a little too negative on works that you don't fully understand yet. >> And again like it took five years from publication and almost maybe a decade from when they actually just came up with the model to see the full power of it with the sum-check protocol unlocking that. So we're we're very bad at predicting the implications of new things and what's to come. And the nature of research is it's fundamentally unpredictable or it wouldn't be research. >> I mean, at one point Shafi said, you know, how do you solve the problem?

Well, it's creative. Of course it's creative. If it's creative, someone would have done it already. >> Yeah. >> I thought that was I thought that was great. So >> Yeah, yeah.