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