Zero Knowledge Proofs – Computerphile


So today I would like you to talk about zero-knowledge proofs. So the reason why I would like to talk to you about that is that today there are a lot of useful technologies coming out, so more and more technologies are very great, but they have the big drawback that they need your data. And your data can actually be pretty private or sensitive. In that scope, actually, privacy enhancing technologies aims to let you have both. So you can benefit from modern technologies without having to give back your data, or, on the other way around, you can have your privacy without having to go back to the Stone Age, for instance. One nice example of privacy enhancing technologies is the zero-knowledge proof and it’s the thing I’m going to talk about you today What actually zero-knowledge proofs are — they are protocol which let a prover, let’s say me, to prove you a statement about a secret, without actually giving up that secret. So I can prove to you that I know a secret, and something about that secret, without revealing that secret. So this is how it works in general, but an easy way to understand the intuition behind zero-knowledge proof It’s actually the game with these two pens. So I will give you these two pens and the idea is that you are color blind and you cannot distinguish which one is the red and which one is the blue. But you don’t believe me. You think that actually there are no way to distinguish these pens and now I would like to prove you that these pens are actually distinguishable without giving away the information of which one is the blue and which one is the red. So I don’t want you to know which one is the red which one is the blue, but still be sure that you believe me when I say: one these two are not equal So how does it work? So I will give you these two pens in random order and now I will ask you to put it behind your back and to swap your arms. Either you do either you don’t at randomly. As far as I’m concerned, I don’t know if this is blue or this is red, these are just two pens that look the same to me. Exactly, you are color blind, but I can distinguish them. Okay, so I’m putting these behind my back. You swap them or you don’t. And now I can tell you, you didn’t swap the pens. So now you actually kind of believe me, but you’re not really sure, because I could have simply said it at random. I had a 50% chances to guess, to guess the right answer, so let’s say you do it again. All right okay, going behind my back and, yeah. Now I can say you swapped the pen. So now you’re a little bit more convinced because you know that I could have cheated only with a chance of 25% And that’s the idea behind zero-knowledge proof. We can repeat that experiment as often as you like, decreasing the probability to 12.5% and so on until you’re fully convinced that I couldn’t have cheated about that. This is the first example and I have a second one to make things absolutely clear. It’s about these cards, so let’s say that we have a classic card deck of 52 cards, and I’ll take like one randomly from this. And now I would like to prove you that this card is actually red But I don’t want to give away the information about the number on that card and nothing else about that. How does it works to convince you about that without giving away the number? So I will simply put that here so you can see it and I take the other one. Now what I will do is, I will show you exactly 26 cards that are actually black. So now you can count them, and if you do you, will notice that if there are here 26 cards which are black, this one here must be red. So this is our nice example on how zero-knowledge proof works and the intuition behind them. To make this thing a little bit a little bit more mathematical for the people that may like it, zero-knowledge proofs actually have three criteria. If the protocol respects these three criteria, you can say, “Okay I did a zero-knowledge proof.” The first is correctness. It simply states that, if both people are honest, so if I’m honest and you are honest, everything works fine The second one is soundness. It’s also kind of obvious. It means that if I don’t know the secret I cannot prove the statement, and I cannot prove that I know the secret so with the example of before if I couldn’t recognize the color of the pens I wouldn’t be able to tell you if you swapped or not pens behind you back and the third one is what makes the whole point of having zero knowledge proof is the is the characteristic called zero-knowledge in itself it means that after following the protocol you learn nothing more than the statement that I wanted to prove you So in the example of the card you learn nothing more that the card here is actually red Nothing, no side information. That’s the whole point. How can you use your knowledge proofs in the real life? So an example for that, a very nice one, is about e-voting how to use zero-knowledge proof to make e-voting work fine, so let’s say that we want to vote for an election which has two candidates two candidates are the pen that we had before and Have two envelopes here and my vote Let’s say I want to vote for the pen on the right here What I do is I’ll write a 1 here and 0 here now I put My vote inside the envelope and putting the vote inside the envelope actually means and encrypting them using Specific type of scheme which is not the scope of that video so the vote one, which means I want to vote for pen blue, I’ll put here and 0 I don’t want to vote for this pen here now How does it works you do the same ok so I have to write 1 and 0 and you put them here Do you have to look away at this time?
Yes ok, let’s get my one and then zero, there we go And so everybody does this voting such way, the envelope means that the voted are encrypted, the idea is that at the end we use protocol to aggregate the results inside all the envelopes without revealing particularly each vote we will only reveal the sum of all the votes having blue and all the votes for red But if we do that there is many ways that we, the voter, can cheat The first thing we could do actually is not write 0 or 1 and the election it’s all about voting for exactly one candidate, not both, and not none of them So the first zero-knowledge proof we could include inside that e-voting protocol is the proof that The sum of our votes, so the sum of the things that are inside your envelope, sum up to 1 Which means you voted for exactly one candidate, but now imagine that you were about cheating and what you did was you put? minus 1 in one envelop and plus 2 in the other one the sum is still 1 But you could not do that, so a second zero-knowledge proof you should add to the protocol is the proof that the encrypted values are binary, so either 0 or 1, so these makes two zero-knowledge proofs And now let’s say another one which is also optional Let’s say, for instance, that I know nothing about Pen’s politic, but I do know that you know a lot about it So what could I do is I take your envelope, your previous vote I copy/paste it without knowing what’s inside and then I vote it on top of it. To avoid that, the third zero knowledge proof would be to prove that I actually know the inside of the envelope that actually know what am I voting for and this mitigates the three problems that we could have with naive e-voting. This is one of the example and this could be applied actually in the same way for assigning petitions online for e-petitioning system So it’s an idea where you can vote electronically so having the benefits of technology without giving away your privacy when you mentioned looking inside and checking that things are binary and add up to one people could look inside those anyway, could they? Or is there a special protocol? No, so actually the envelope here are not really envelope These are encryption of what is inside so there is no way to decrypt it and no one is really willing to and has not the possibility to decrypt each single vote you can only decrypt once all the votes have been summed up So there is no way to recover which person voted for which a pen at the end There is only way to know that the person actually Did a binary vote which also sum up to 1 and that he knew the content of the vote This is part of the encryption protocol, is it? Yeah, the second part is part of the zero-knowledge protocol that comes over and works with the encryption protocol. The idea is that, the fact that the vote is binary is your statement but the votes content is your secret so it’s still in the definition of zero-knowledge proof about proving you statements about the secret without revealing you the secret so for instance the fact that the card is red, back in our cards example but not what the numbers, right? Exactly, yes. That’s an example or also the secret is my vote, so the secret is: is it zero or one? I don’t tell you that, but I want to tell you the statement that it is binary It then there will be no energy cost to computing No energy cost. No energy cost, because, here’s the fascinating thing, what costs the energy is not the computation itself, it’s a raising information

100 Replies to “Zero Knowledge Proofs – Computerphile”

  1. 0:51 I quit smoking 3 days ago and now I'm like "TELL ME ABOUT THE CIGARETTE! I WANT TO KNOW"

    I can't watch Quentin Tarantino movies now and now cigarettes took this channel from me too??? WHAT ELSE DO I HAVE TO DO TO QUIT???

  2. What if we would count an election, then we could remove one vote and count again. We could find out the value of the vote we removed…

  3. Finally a topic that is well presented without being common knowledge already. Best video of the year on this channel IMO!

  4. A part I don't think was entirely clear was the following:

    Given that the secrets/data are assumed to be encrypted, how can they prove something about information that's, by definition, not accessible (e.g. that each individual vote met the criteria of being binary, etc.)?

  5. I'm sorry. This guy is amazing but I can't cope with the accent. Cigarette for secret. Nope. Just too difficult for me to follow. My fault, not his.

  6. Wow. I totally didn't understand a thing about this subject before. And now, I think that I know even less. Perhaps you could do a follow up with a better explanation and some real practical examples.

  7. Sadly, being able to retain and exploit the extra information used in a typical transaction is viewed by the data aggregators not as a bug, but as a feature.

  8. After listening to this guy for 3 minutes, I rediscovered a so called "hit single" by an artist known as Loona, titled: "Latino Lover". It was a feint memory in my brain from my childhood and it came back alive… I'm not sure I'm thankful.

  9. So zero knowledge proof is basically guessing on data? Like say for instance you are able to determine that the data that is being stored may or may not be used for third parties?

  10. Encryption – It's said in the video that it's not part of scope, but I think it's essential. Who does the encryption when you put into envelope? I find it hard to "believe" that there would be a magic algorithm which would decrypt if and only if elections are finished and all envelopes are in hands of "good guys".

  11. A problem with a lot of e-voting schemes is that even if you can't decrypt the vote individually, you can still copy the vote to a separate pile, add dummy votes until you can decrypt it, then count the difference from the dummy votes.

    One way you can mitigate this problem is to have some randomness to it. Say you have a 33% chance to vote for the other candidate. You hand over 3 votes, do a zero knowledge proof that all 3 votes aren't the same, then the voting booth chooses one at random. The more voters you have the less likely it is that the randomness will affect the outcome, however the risk of it happening does increase if it's a close election. Yet for an individual it's unlikely they would face any consequences if someone reads it, with the high risk of it being incorrect.

  12. This reminds me of the way cryptographic keys are exchanged in WPA – what is actually exchanged is a key generated from some odd bits of data like the time, so you only prove that you know the key, without broadcasting it over wireless

  13. I did not expect the video to end so abruptly. I was expecting him to have a chance to explain the tallying of the votes.

  14. Im a bit confused. What exactly would the proofs be that the sum is one, the inputs are binary, and that I know whats inside?

  15. It would have been awesome if he had gone into more detail of the zero knowledge protocol.

    For example, how is it it's only decryptable when you sum the values? How, if it's encrypted, can you make sure that it's a binary?

  16. I don't get the part around 7:16 ~ 7:48.
    I have trouble understanding both the speaker's English and the substance. Could someone enlighten me?

    What problem was he trying to solve and how do "copy and pasting someone else's ballot" and "voting on top" factor into it?

  17. While this does explain the concept very well, I don't understand how the encrypted votes will be counted without revealing their content. Surely a voter has to decrypt their two envelopes before any protocol can add their votes to the totals, right? So why wouldn't that reveal what they voted?

  18. Man, that pen trick is so much clearer and more informative than the parable of Ali Baba's Cave that I've usually seen used to describe zero knowledge proofs.

  19. About e-voting:
    Is it possible for the voter to check his vote has been registered and counted correctly, WITHOUT the voter being able to proof to anyone how he voted(necessary for voter secret)?

  20. 100% garbage here. The integration of techniques of deceit into a curriculum should be a prime indication that there is no knowledge to be gained and someone is wasting someone elses time. UCL is a garbage school and offers nothing but mediocre intellects. Empirical evidence is the only valid form of proof. Using scams to validate a proof is just another way of deceiving. The ethics of the educators at this school are highly suspect (if they exist at all).

  21. I can only understand this as a high level overview about the concept which ultimately requires the actual algorythm/crypto to be really understood.

  22. I don't get the 3rd,optional proof. You copy it and vote on top of it. What does that mean and how does it proof anything? Can Somebody explain?

  23. You take the blue pen and you forget about everything you've learnt you remain a part of the matrix, you take the red pen you stay in wonderland a bit longer, you go down the rabbit hole. What do you choose?

  24. Great video to convey the intuition of zero knowledge proofs, which I didn't know already. It'd be really helpful to see a basic encryption example to take the intuition another step towards full understanding. Thanks for the great content!

  25. And yet, E-Voting is a baaaaaaaaaaaaaaaaaaaaaaaad idea. Tom Scott'll explain it in the very detail.

    "Some things aren't meant to be digitized."

  26. There is no zero knowledge "proof" here, only correlation and zero knowledge assumptions.

    What would you do if you wanted to prove that you cheated on a previous proof? Don't you first have to prove that the deck had 52 cards, that 26 were red and 26 were black before proving that the card you had was red? But then, wouldn't you have exposed what the possible values of the card you held were? In that case I have the knowledge that the one card you're holding is one of the 26 cards that I know the value of. Therefore I don't have zero knowledge… so yea.. you have to lie or give more than zero knowledge for me to KNOW that you are telling the truth. And even then, if you lied I wouldn't know the truth; hence the whole concept breaks down. How is this useful in any way? It's just obfuscation – and that NEVER works.

  27. So what if I write a virus for your e-voting system that tells the user they are voting for the blue pen, but the software submits a vote for the red pen instead?

  28. By what method is it possible to irreversibly encrypt packets of single digit binary data where only the sum of those packets is then ascertainable?

  29. You said that you present 26 cards, either red or black(depending upon the color you have) from the deck. Isn't that's also some knoweldge that you are providing it to the person in front ?

  30. A simple example of a Zero Knowledge proof ist this: Say there is circular hallway, separated by a locked door. To prove that I know how to unlock the door, I don't need to give you the key, nor do I need to show you how I unlock the door. We'd just start at the opposite side of the hallway (where the door isn't visible) and I'd go down the hallway to the left and I'll come back on the right side. I couldn't have pulled it off if I didn't know how to open the door.
    This is the way some protocols on the internet work. You will encrypt something and send it to me. I will decrypt it, and will tell you something about the content (like a checksum, or a task that I need to solve). An eavesdropper will only see and encrypted message and a checksum (or the result of the task), never will he see the message (the task), nor will he see the key, nor will he know what I did. In this case I have proven to be the person I claim to be (the one you exchanged a key with over another channel at a different time) without revealing anything to an eavesdropper.
    With secure asymmetric encryption (key pairs, where one key is public and one is private) this can be achieved without exchanging a secret key over another channel. You could encrypt something with my public key (that everyone may have) and ask me to tell you something about the content you just sent. If I can pull that off, I have proven to you, that I have the private key, with no one but me having any knowledge of the private key itself and no eavesdropper having knowledge about the actual content, the key or the challenge.
    A zero knowledge proof is basically giving someone a challenge that they could not solve without having a required knowledge, not revealing the required knowledge itself.

  31. This just made me realize something. Imagine if you could vote for as many people as you liked. I bet gary johnson would have stood a real chance of winning against donald trump. The only reason so few people voted for gary johnson is they thought it would be a waste of a vote.

  32. hi~ this video was such an eye candy. however I'd love to see subtitles. I can say I understood pretty much but subtitles speed up the learning process. But! it was a such a great and informing video. I'm looking forward more on provable security by Antonio on YT.

  33. Yeah ok i sort of get it, to start of with i thought this was for web searches or to hide a trace of searches or page visits, i guess it could be. But then thought you are relying on encryption, and if the encryption couldn't be broke in the first place then why bother with what you have just said, or am i missing the point??

  34. Lots of italians lately, I seem to notice. Or at least, I've counted two, which is already a lot compared to earlier. Pizzaphile soon?

  35. What eejot came up with the name zero knowledge proof? It's oxymoronic. Nobody can be in the position of saying "I have proven this yet I have no knowledge". This is about partial information transfer, just as if I told you that I have a preference between beetroots and beefburgers and whether you've swapped them, without telling you which one I prefer. For elections this is about gaining statistical knowledge while preserving individual anonymity. Bad name.

  36. 1 you could have distinguished the pens based on some other distinguishable aspect about the pens and not the color that only you are aware of…2 the pen need not be blue, some other color perhaps(may be it is green) hence still distinguishable from the red

  37. Accent isn’t so bad, but his stuttering grammar makes it very hard to follow what he is saying. First computerphile video I ever disliked/stopped watching to go get a better summary elsewhere.

  38. Soundness and correctness are the same thing. However soundness is a term mostly used in technical context, in contrast with correctness. What he should have said is soundness and completeness instead.

  39. But how can you prove you proved it?
    LIke the color blind guy can deny you proved him anything… isnt this a problem?

  40. This is just an example of how ZKP can work, but it doesn't explain how it works! Could we get a video with more mathematical explanation?

  41. so we understand zero knowledge but didnt get the part of knowing the "pen's politics" i.e user proving they knew what they are voting for – lost me there.

Leave a Reply

Your email address will not be published. Required fields are marked *