Placeholder Image

字幕表 動画を再生する

  • 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

So today I would like you to talk about zero-knowledge proofs.

字幕と単語

ワンタップで英和辞典検索 単語をクリックすると、意味が表示されます

A2 初級

知識ゼロの証明 - コンピュータマニア (Zero Knowledge Proofs - Computerphile)

  • 0 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語