Computer Scientist Explains One Concept in 5 Levels of Difficulty

Computer scientist Amit Sahai, PhD, is asked to explain the concept of zero-knowledge proofs to 5 different people; a child, a teen, a college student, a grad student, and an expert. Using a variety of techniques, Amit breaks down what zero-knowledge proofs are and why its so exciting in the world of cryptography. Amit Sahai, PhD, is a professor of computer science at UCLA Samueli School of Engineering.

Video Transcript

AMIT SAHAI: Hi, my name is Amit Sahai, and I'm a professor of computer science at the UCLA Samueli School of Engineering. Today, I've been asked to explain zero-knowledge proofs in five levels of increasing complexity. A zero-knowledge proof is a way for approver to convince a verifier that some statement is true and yet reveal no additional information beyond the fact that the statement is true.

Zero-knowledge proofs are being used in blockchains and cryptocurrencies. So cryptographers are excited about zero-knowledge because of its amazing mathematical properties, but also because of its incredible applicability to so many different scenarios. What's your favorite subject?

- I'd say math. Some of these small problems can actually be really big and complicated. It's like a puzzle.

AMIT SAHAI: I love math for the same reason. Today I'm going to tell you about a thing called zero-knowledge proof. So in the zero-knowledge proof, there are two people. There's a prover, and a verifier. And I want to prove that something is true to you.

But the weird thing is, I want to prove to you that it's true without telling you any reasons why. I remember when I first heard about it, I was like, wait, what? How could that possibly be, right?

- Yeah.

AMIT SAHAI: So what do you see in this photo?

- A lot of penguins.

AMIT SAHAI: Yeah. Hidden among all these penguins is a puffin. Do you want to try to look for it? Do you see where it is?

- Hm.

AMIT SAHAI: I know where it is, but I don't want to tell you. Do you believe me? You're not sure to believe me, right?

- Yeah.

AMIT SAHAI: But what if I could prove to you that I know where the puffin is without revealing to you where it is. Let me show you. I took that photo that we showed you, and I put it behind this poster here. Why don't you go take a look through that hole.

- I see the puffin.

AMIT SAHAI: So when you look at this board, we don't know where the photo was, right? Was the photo, like, with the corner here, in which case the puffin would be all the way at this side? Or was the photo with the corner here, in which case the puffin would be on the other side? So this is a really simple example of a zero-knowledge proof. I convinced you that I knew where the puffin was, but you didn't learn anything else.

- Why do you study zero-knowledge proof?

AMIT SAHAI: When I first learned about them, I just thought they were so cool. But it turns out they're also really useful not just for finding, like, puffins. If you just type in your password and the hacker hacks into the computer, they can just get your password, right?

- Yeah.

AMIT SAHAI: What if instead, we could somehow use a zero-knowledge proof to log in. You would just be able to prove that, hey, I'm Chelsea, without revealing anything to them. If you could do that, then it would be amazing, right?

- Yeah.

AMIT SAHAI: Because then even if the hacker hacked into the computer, he wouldn't learn anything, because even the computer doesn't learn anything. So Chelsea, in your own words, what is a zero-knowledge proof?

- Zero-knowledge proof is proof to a statement. You don't show them why or what. You just show them a tiny segment or just do some sort of weird magic trick that's not really a magic trick, and they'll be convinced. And you didn't show them why or anything like that.

AMIT SAHAI: So have you ever heard the term zero-knowledge proof before?

- I have not, no.

AMIT SAHAI: You have not, right? It's a way for a prover to convince a verifier that something is true without revealing anything about why it's true, which sounds totally bizarre, right?

- Yeah.

AMIT SAHAI: How can that possibly be? What I want to do is prove to you that I know this combination without revealing the combination to you. And what you could do is, you could write a little note, a secret that I definitely wouldn't know. Fold it up, stick it in here. And then if I know the combination, I should be able to open it and tell what you wrote. All right.

There we go. All right, so my dog is named Doug. Did you figure out what the combination was?

- No.

AMIT SAHAI: So nowhere in this interaction did you see any information that you didn't already know, and yet I convinced you that I know the combination, right?

- Yeah. So what's the exact purpose of a zero-knowledge proof? Is it like proving something but without giving enough information that could endanger whatever it is that you're proving?

AMIT SAHAI: So you're asking, why shouldn't I just share my secrets with somebody? People don't trust each other, and if I was able to prove that I've done something correctly to someone without having to reveal my secrets, then that person would trust me more.

- How does this relate to computer technology? Like do you type it into a computer, and somebody else receives it? Or is it an in-person interaction?

AMIT SAHAI: Suppose you wanted to exchange messages with someone that you knew. What would you guys do? You'd probably first get together and figure out some secret code, right, and then write messages to each other in that code. But what if you've never met the person before? What if you want to exchange secret messages with me, and we've never met each other before. How could we possibly do that?

- I have no idea.

AMIT SAHAI: It sounds impossible.

- It does.

AMIT SAHAI: But it's not. You wouldn't use like a physical lock or a physical box. We would instead use mathematics to do these kinds of things. You could take a message and encrypt it using mathematics, and then I could prove to you that I know the key. I could open it up and send it back to you. That way I would be proving to you that I know the mathematical key to the mathematical lockbox. So based on what we've discussed today, in your own words, what is a zero-knowledge proof?

- It's like if you have this really important secret that you want somebody to know about, but you don't want to tell them everything, you can use a zero-knowledge proof to prove to them that secret, but not give away all of it.

AMIT SAHAI: What are you studying?

ZAYN SIDDIQUE: I'm a first-year computer science student at USC Viterbi. I'm interested in all things data, and internet, and blockchain, and cryptocurrency.

AMIT SAHAI: Have you ever heard of zero-knowledge proofs?

ZAYN SIDDIQUE: Only in passing.

AMIT SAHAI: So actually, in the blockchain space is one of the spaces where we are seeing zero-knowledge proofs being implemented. And I think it's just the beginning. Let's talk about zero-knowledge proofs. At its core, a zero-knowledge proof is an interaction between two people. Then I should be able to convince you that some statement is true, but you won't have any idea why it's true.

ZAYN SIDDIQUE: Well, I understand that it's true because the operations performed in the proof are of a certain, you know? They have certain attributes that would make them true.

AMIT SAHAI: What you're basically asking me is, wait, what? Right? So this is what makes zero-knowledge proof so fascinating and so counterintuitive. And I think the best way I can explain it to you is by means of an example. But before we do that, I have to decide what I'm going to prove to you with a zero-knowledge proof.

ZAYN SIDDIQUE: Sounds good.

ZAYN SIDDIQUE: And the way we're going to approach this is through something called NP completeness. What an NP-complete problem is, it's a problem that's really hard to solve. But if you can solve it, you can solve any problem that's in the class NP, and that includes a vast number of problems. And what we're going to do is, we're going to use an NP-complete problem to actually prove an incredible variety of statements through a zero-knowledge proof.

And the specific NP-complete problem that we're going to be looking at is called map three coloring. OK, so here we have a map, and these are a bunch of countries. And we've arranged them so that no countries that have the same color share a border. That's what makes a map like this validly colored.

And now you might think, well, why should we care? It turns out that whether or not a map can be three-colored in this way is an example of an NP-complete problem. And it turns out that, you know, maybe what you really want to do is you want to give a zero-knowledge proof that you have at least 0.3 bitcoins. Right? That would be cool.

ZAYN SIDDIQUE: Yeah.

AMIT SAHAI: Without revealing what the address is of your account. It turns out I can take that statement that I have at least 0.2 bitcoins and convert it into a map of countries, and that map of countries will be three-colorable like this only if you have at least 0.2 bitcoins.

ZAYN SIDDIQUE: How would we turn something like this into a zero-knowledge proof?

AMIT SAHAI: Of course, the first step is, we have to erase all the colors. What I've done is I've put a color inside each of these envelopes. Now, how do you know that it's a valid coloring? You don't, right? You have to pick any two neighboring countries. You can pick them however you like, at random.

ZAYN SIDDIQUE: Can I get these two?

AMIT SAHAI: These two. All right, sounds good. Here we have green, right? And over here we have blue. And as you can see, they're two different colors. So you have a little bit of confidence, right, that I have managed to color this correctly, but not that much confidence, because I've only shown you two of the countries.

ZAYN SIDDIQUE: Yeah.

AMIT SAHAI: So now, of course, one way to get more confidence is to open up more of them for you, but that would be revealing information to you. I don't want to do that. So instead, I'm going to ask you to please turn around. And now let's change up these colors. Can you pick two countries at random, and we'll reveal to you the colors again?

ZAYN SIDDIQUE: I'll pick this one and this one.

AMIT SAHAI: Nice. And that's smart of you to check with the same, one of the ones you already had, right? But as you will see, now it's not green. It's blue. And this one, on the other hand, is green. The colors I showed you last time don't work with these new colors. This wouldn't have worked before.

ZAYN SIDDIQUE: Because of this one, right?

AMIT SAHAI: Exactly. But it works for this coloring that I'm showing you right now. So what we've done is we've made it impossible for you to put the pieces together. And if you do this, let's say, 1,000 times, and if I correctly showed you different colors each 1,000 times, you'd be really convinced. And that's it. That's the entire zero-knowledge proof.

ZAYN SIDDIQUE: Oh, OK. So is it, like there's no like actual explicit, like, step one, step two, step three.

AMIT SAHAI: No.

ZAYN SIDDIQUE: It's just like, a probabilistic proof, almost.

AMIT SAHAI: Yeah, in actual implementations, we wouldn't use envelopes. We would use encryption. But it's really, this is the protocol.

ZAYN SIDDIQUE: So what are the broader implications of zero-knowledge proofs? Are they supposed to be like, more practical for implementation end, or are they supposed to structurally prove something?

AMIT SAHAI: It's not about making something more efficient. It's about doing things that we just didn't know how to do before. I can actually prove to you without revealing to any of my secrets that I use to behave honestly. I could prove to you that I signed some encrypted document correctly without revealing to you what that secret document was. That ability to change the game, like really just change what we can do is what zero-knowledge brings to the table.

ZAYN SIDDIQUE: Where do you think we could build more trust using zero-knowledge proofs and its implementations?

AMIT SAHAI: One great example is like in elections. If you could prove that an election was correctly conducted, that every vote was counted, and it all added up to one person winning with a particular total in zero-knowledge, then you don't have to give up the actual votes of any person. And yet everyone could see that, hey, yeah, it was done correctly.

It's so great to have you here and to talk with you, Eli. Can you tell me a little bit about your research?

ELI JAFFE: My research is in cryptography. Specifically, I'm working on some various multiparty computation protocols. The one I'm working on right now is a system for computing aggregate statistics so that service providers like Google Chrome or Tesla can collect those statistics without learning anything about individual users' data. I, as a user, don't have to let Firefox know that my favorite website is mylittlepony.com, but they can know how many users go to mylittlepony.com every day.

AMIT SAHAI: That's near and dear to my heart, are part of computation.

ELI JAFFE: Obviously, zero-knowledge proofs are about proving things to another person without revealing the details of what it is that you're proving. But you know, in my mind, zero-knowledge actually goes even further beyond that. It's like this overarching concept that you can see a lot in multiparty computation, where you want to accomplish some sort of task without revealing anything more than exactly what you need to accomplish that task.

AMIT SAHAI: Right, and it allows you to prove that you've been behaving honestly without revealing any of the secrets involved that you used to actually behave honestly. So we, of course, know that zero-knowledge proofs for NP-complete languages play such a huge role in cryptography. I'm curious, what what was your first experience with NP completeness like?

ELI JAFFE: Yeah, so my first encounter with NP completeness was in my very first algorithms class that I took as an undergraduate. So that was my first introduction, is that an NP-complete language is this amazing problem that not only tells you about itself, but solving this problem can actually tell you about an entire class of really interesting problems.

AMIT SAHAI: When we first started to think about proofs as an interactive game, where we're talking to each other, that made zero-knowledge possible.

ELI JAFFE: Absolutely.

AMIT SAHAI: Right?

ELI JAFFE: Yeah.

AMIT SAHAI: And the idea that randomness could be useful for proving something, again, seems so counterintuitive. If we think about this platonic ideal of a proof, there's no randomness. There's no non-determinism that's present there.

ELI JAFFE: And it has to do with this whole idea of flipping a proof on its head. You know, in an old classical proof, randomness is specifically against the goal of what you're trying to do. Because you're trying to make everything obvious, and you're trying to reveal the flow of information.

AMIT SAHAI: Indeed.

ELI JAFFE: But once you flip that on its head, and you're no longer trying to do that, suddenly all of the bad properties of randomness become good.

AMIT SAHAI: Exactly, right. Because randomness is unpredictable, and that's what we want. We want that unpredictability of randomness to be utilized to actually hide the information that we want to hide. How have you used your knowledge in the projects that you've worked on? What are the challenges that you find?

ELI JAFFE: In my experience, usually the hardest part is figuring out exactly where the best place is to use it. I've written some papers in the past that I've used zero-knowledge in a more theoretical way. But when it comes to applications, some of the most exciting applications that I've seen so far have been in the blockchain space.

AMIT SAHAI: So what are some of the efficiency bottlenecks that you find?

ELI JAFFE: In terms of efficiency, one of the coolest things about zero-knowledge proofs is that there's so many kinds. I like to call them flavors. I think that in general, when you're using zero-knowledge proofs in application, the main bottleneck tends to lie on the prover.

AMIT SAHAI: Can you take the prover's job and split it up into lots of parallel computations?

ELI JAFFE: That's such a fun question.

AMIT SAHAI: It's such a great question. And yeah, I think we still don't know the answer to that as a field.

ELI JAFFE: One of the coolest things I've seen over the past three or four years, when I've been working on this kind of stuff, is the transition from theoretical to applied and seeing all of these amazing systems that people thought of in the past 30 years start to actually get efficient enough to be actually made.

AMIT SAHAI: No doubt. And especially with cloud computing, exploiting the power of the cloud to enable zero knowledge proofs and to make use of zero-knowledge proofs would be

ELI JAFFE: Yeah, absolutely.

AMIT SAHAI: And also in the blockchain space, for example, if you want to speed up the generation of proofs, if that could be done in a distributed way, then that would be great. One of the hopes that I have is that the power of multiparty computation is about bringing people together who are mutually distrustful.

ELI JAFFE: Yeah.

AMIT SAHAI: Right. So can we take that power that's there in the cryptography and use it to somehow help with the tremendous level of mistrust that exists in society right now, in helping to bring groups of people together?

ELI JAFFE: I think that's one of the reasons that I was so drawn to multiparty computation in the first place. In my mind, one of the most important problems in the world is the fact that so many people don't trust each other. And to be able to actually use math to create technology that can allow people to work together without having to trust each other is a really cool and awesome mission, I think.

AMIT SAHAI: Shang-Hua, it's so great to see you again. I think last time we met was in 2017, or something like that.

SHANG-HUA TENG: I think we Zoomed once during the pandemic, but it's good to see you in person.

AMIT SAHAI: Right, absolutely.

SHANG-HUA TENG: And actually, in '86, I was taking a crypto class with Professor Leonard Adleman, The A of RSA, and he assigned me the paper by Goldwasser-Micali [? Charlie ?] [? Rieckhoff ?] on zero-knowledge proof. So that's, indeed, my first ever presentation ever in this country.

AMIT SAHAI: Was about zero-knowledge.

SHANG-HUA TENG: Was about zero-knowledge, yes.

AMIT SAHAI: It's such an almost hypnotic, concept.

SHANG-HUA TENG: It's also an interesting way how, mathematically, to formulate those concepts. For example, we have data, then eventually we said, from data, like data mining, you can get the information. And then you have this word called knowledge.

Right, so knowledge has been long debated even in philosophy. What is knowledge? But here is, in a very fascinating way, mathematicians or computer scientists want to somehow capture knowledge. They didn't say zero-information proof.

AMIT SAHAI: Right.

SHANG-HUA TENG: So what's your take on why knowledge is, rather than information, or zero-data proof. Clearly, there's data there, so can't be zero-data.

AMIT SAHAI: Absolutely. I don't think we still have a completely satisfactory answer to that question. What was such a beautiful insight, as I'm sure you know, is that the idea of zero-knowledge being something that you can already predict. If you can already predict the answer, then you must not be gaining any knowledge by that interaction. This insight of being able to predict the future accurately, and that being an evidence of a lack of new knowledge was such a beautiful insight, such an amazing insight.

SHANG-HUA TENG: But why not zero-information here? Fundamentally, clearly, from computing perspective, security perspective, is how much knowledge you gain, I guess, more than how much information you gain.

AMIT SAHAI: Indeed.

SHANG-HUA TENG: And how much data you have, right? So that big data then immediately imply a knowledge. But people can, sometimes.

AMIT SAHAI: Right, sometimes. I mean, for example, in medical research, how amazing would it be to be able to have a drug and be able to prove that my drug works in this model, and yet not have to actually reveal the structure of the compound?

SHANG-HUA TENG: What, currently, you're saying would be the next directions?

AMIT SAHAI: What are the next big things?

SHANG-HUA TENG: Yes.

AMIT SAHAI: This concept of zero-knowledge programs would allow you to carry out completely arbitrary computations in a zero-knowledge way, without any interaction. I can just take the program, convert it to a zero-knowledge program, or an obfuscated program, and then just send it to you. And then you can run it and gain the benefit of that computation without having to talk to me anymore.

SHANG-HUA TENG: That's right. This non-interactive nature.

AMIT SAHAI: The non-interactive nature.

SHANG-HUA TENG: But with verifiability in it.

AMIT SAHAI: Indeed.

SHANG-HUA TENG: Sometimes, when, for example, when you have multi-protocol exchange, that, you know, random numbers showed up. You have to enter the random number.

AMIT SAHAI: For authentication, yes.

SHANG-HUA TENG: Authentication right now. Clearly, I think in blockchain, they also began to incorporate more.

AMIT SAHAI: Indeed.

SHANG-HUA TENG: Their zero-knowledge proof in the ledger.

AMIT SAHAI: We're definitely at this moment now where zero-knowledge is going to be used more and more. There are so many conferences and meetings that occur in the zero-knowledge space where you and I are not invited, because it's for the people who are developing, the people who are programming, not us mathematicians.

SHANG-HUA TENG: Yes, yes.

AMIT SAHAI: And I think that's a sign. That's a sign that our baby has grown up, and you know, it's time for it to be developed.

SHANG-HUA TENG: I think profoundly, the student often also ask me, what are the future direction, both in terms of crypto, zero-knowledge proof in the real world, and how mathematically you see in computing?

AMIT SAHAI: It's a great question. And I wish I could see the future. I can't, actually, but let me try. The part of that that I'm the most comfortable answering is, of course, the mathematical side. I think that there is, we've done so much in cryptography over the last few decades, but we understand so little. Even today, we understand so little.

And I think the most fundamental aspect of that is understanding hardness. How do we get hard problems? How do we actually build mathematically hard problems so that we can then use them to build efficient zero-knowledge programs and efficient zero-knowledge proofs, right?

SHANG-HUA TENG: I guess also, with quantum computing, you need an even harder problem.

AMIT SAHAI: Indeed, absolutely. You know, now that we have the specter of quantum computing coming at us, and we all know that quantum computers can break a lot of cryptographic systems.

SHANG-HUA TENG: That's a profound challenge.

AMIT SAHAI: It's a profound challenge. So can we find new sources of hardness that are quantum-resistant, even quantum computers can't break. And that's something I've been working on for the last several years. But I'm be very excited to see what happens in that space.

SHANG-HUA TENG: But I'm sure they will motivate beautiful mathematics.

AMIT SAHAI: Yes, that's right. You know, one of the great things about the real world is that people in the real world have demands, and those demands often sound impossible. And that's where we come in. It's our job to make the impossible possible.