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
This only explains the concept and gives three non-technical examples. While the concept is clear to me now, I feel like I'm missing the actual implementation.
With e-voting he says everyone submits their encrypted vote and the results can only be revealed as a sum, not as individual votes. But he doesn't say how, surely everyone has to decrypt their vote (open the envelope) so the totals can be counted. But then everyone can see what everyone else voted, so how does that protect their privacy?
I get why every voter has to prove that the sum of their votes is 1 (when voting on two parties). Their individual votes must be binary (one is +1 for candidate A, the other is +0 for candidate B). And the voters need to prove they know what they put in each envelope (as to not simply copy their friend's votes). But how is any of this done?