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.
@@brixomatic However, this gives you a 100% guarantee that you have the key. If for example you were to walk down the hallway and I asked you to come down the left hallway, I can with 50% certainty say you have the key (if you went right and went through the locked door and came to left VS you were already left and didn't need the key) and repeating the experiment many many times can give me confidence.
This explanation was easier to understand and more straightforward than all of the explanations offered in Wired’s “explained at 5 level of difficulty” video on ZKP!
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?
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!
It's very frustrating that almost all such videos do a perfectly good job of explaining the abstraction, but then do literally nothing to explain the actual implementation. I had about 499 good abstractions, and now I have 500. Still don't know how it's actually done.
Yes, after many hours, I have concluded that it is a scam. Ultimately they bamboozle you and then you are siphoned off into their API and paying for gas to run smart contracts on a shitcoin. Even when there are examples of math, The initial conditions look nothing like computer programming instructions converted numbers, but mathematical patterns.
Exactly! I'm frustrated for the same reason. I think it might have something to do with public and private keys and hashes. For example a website stores only hashes of its users passwords and never stores the password itself. From the hash it's impossible to recreate the password. When the user logs in with their password the authenticator software only relays the hash of what the user typed in and it's checked to see if it matches the hash the website stores on file. Thus the website knows that the user entered the correct password without even knowing what the password is or what the user entered. Not sure if that's perfect zero knowledge though.
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?
Scott Tsai He's explaining that you also need a proof that the voter knows what they're voting, so that someone can't just give them an envelope and tell them to submit that
The problem with e-voting is not the algorithm or the protocol behind it, it's the implementation of it. It doesn't matter if you have plans to build a perfect system if people keep making mistakes trying to build it.
Even before we get to the impossible implementation problem I'm yet to see even a vaguely valid algorithm that lets citizens vote anonymously while retaining the simplicity of invigilated paper votes and restricting vote tampering. It would also have to let the citizens verify their their vote was counted and not discarded or modified. Each step is easy but combining encryption with hashing with signatures while maintaining anonymity in a function voting system has yet to come to my attention.
@@noder8867 Because votes can be saved and if there is doubt a recount can be ordered. There will always be some trust unless you can recount all the votes yourself, but having different checks and balances reduces trust in any one person.
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
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.
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".
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
I don't know if someone has mentioned this before but wouldn't I have to show you that I indeed have a full deck of cards before proceeding? Or is that already assumed? Let's say it's not. How could we ensure that I have a fair and full deck of cards before proceeding
Ok, I just saw this same "demo," but with candy clouds instead of pens. My immediate thought was, "What if the pens ARE the same color, and that's what we want to prove?" Suddenly the swap test fails. So it feels like a particularly trivial example is being chosen. I want to see a deep dive demo into how this idea ACTUALLY WORKS - something that would give me some shot at being able to apply it to anything I wanted to apply it to.
There are ways to encrypt data such that you can still apply operators (like addition) on them. For addition, you'd have to build an encryption scheme for which the following holds: encrypt(A + B) = encrypt(A) + encrypt(B)
This would've been super helpful if that was mentioned. To me it was all about "we have envelopes and then we use what is inside to calculate a sum", meaning that he has to open it. Using a special envelope that allows to do math really did not come anywhere in that demonstration.
Cool thx :D It's just my curiosity, but aren't these types of encryption inherently worse than other forms of encryption? Also if you have an example I'd be ecstatic.
klemen kobau generally yes because once you have relations between encrypted values that can be used to break the encryption. For example there are encryption schemes that make comparison possible. But in this special use case I believe this is fine because we only have 0 or 1 as encrypted values that always should add up to 1.
...but hopefully it gives you knowledge about what it is and what its uses are. I’m sure there are well explained videos for specific ZKPs elsewhere...
@dosmastrify, voting example does not tell you how it works. I.e. it does not explain how to use zero knowledge proofs to prove that I know who I voted for in e-election. It merely states in broad terms that it is possible. I think the explanation could have been more... in-depth.
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.)?
Apparently, there exists encryption methods that do allow for operations such as summing.. I know.... i had to dig thru comments to get that "small" detail..
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.
The details left unstated in this video about electronic voting using zero knowledge proofs could fill a decent size book. It presumes that methods exist without describing how they might work. On top of which, the example isn't valid in an election where you may vote for nobody.
The ability to vote for nobody is trivially accounted for though. since by definition 'nobody' represents a singular option. (there's only one possible way to vote for nobody) this just means that 'nobody' is conceptually the same as a single candidate. So it still means you can vote for 'one' candidate, but that 'nobody' is considered a valid choice of candidate. (you voted for a single candidate, which happens to be the null candidate - eg. None of the actual candidates.)
Why do don't do electric voting is because someone can hold a gun to someone's head. Same reason why you are not allowed to take photos of your ballot before you seal the envelope. Also: It is easier to trust physical paper than an electronic machine. Computers are inherently untrutwearthy if you don't know exactly how it does thing. And fraud is much easier when you only need to log in with your electronic ID and such.
I wonder how zero knowledge would solve the most fundamental issue of e-voting. Imagine a well working paper system: You can stand in the voting room all day, watching people put envelopes in the voting box, taking note of who put one in and how many people put one in. After that you can watch the box opened, every envelope opened and the counting. Thereby you can prove to yourself a lot of things without knowing who voted for what option: - the total number of envelopes is the total number of actual unique people. There were no envelopes in the box before the voting began. - each envelope contains only one vote or its invalid - therefore you can derive each unique person voted just once - each vote represents the genuine free decision of a unique person: The voter could decide freely because he wasn't watched, his vote will be in the box because he put it there and the position where he made his mark wasn't changed While some part of this may be proven by zero knowledge prove, what prevents a voting machine from having some "votes in the box" beforehand and silently discarding the same number of real votes? Or what prevents a voting machine changing a vote before it was encrypted?
There are actually Zero Knowledge proofs for this as well. Imagine a system, where you encrypt your vote and publish it on a website specifically designed for this election. Then you (and every other voter) can check for themselves, that their vote is actually present there. After the election closes, the votes are shuffeled, aggregated and the aggregate is opened. For every step, you can give a zero knowledge proof, that this step was performed honestly (assuming that a large enough number of officials who supervise the election are actually honest). These zero knowledge proofs have to be published together with the election results, so everyone can see that the counting wasn't rigged. Of course I omitted a whole lot of stuff, e.g. how you know that everyone only votes once, but these protocols are way to complex to explain them completely in one comment.
I've learned about zkp on the example of the Alibaba door while learning about smart-contracts, i find this example far more simple that the example used in the video. if someone could enlighten me about non-interactive zero knowledge I would be thankful
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.
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?
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??
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?
I'm not sure I understand how in the voting example there is a difference between "knowing the content of the vote" and knowing that 1) the votes are binary, 2) they sum up to 1, and 3) that you know what you're voting for
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)?
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.
Yea, as most people in the comments are saying it gave only non computer examples for something that is implemented with computers. So the methods used in the fictional examples will not look anything like the real implementations. It leaves us very unsatisfied.
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 ?
The point is to prove that the card is red without revealing any other details about the card (suit or number). You can easily do this by showing the person all 26 black cards from the deck. This works since a deck only has 26 cards of red and 26 of black. By showing you all 26 black, then the other secret card must be red. You've proven it is red, but the person still doesn't know the suit (diamond or heart) nor do they know the number. Do remember that basic ZPK really only works when all parties involved are honest. In this example, the deck must be only 52 cards consisting of 26 red and 26 black and the person with the cards did not alter the deck in any way. Also, the person who picked the card must have picked a single card from that deck.
The example of the red card is great but I still cannot understand how could I prove something like "I have more than 10k dollars in my bank account" without revealing how much money I do exactly have. The red card is related to the other 51 by some rules (there are exactly 26 card for each color, and so on), so I can give informations about the other variables related to my card, but the amount of money I have is not related to anything...
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.
But one thing about the cards example. This gives me a 100% certainty about you having a red card right? Don't ZKP have some probability in them? As you have to repeat the experiment many many times to gain enough confidence that person A knows a secret?
yes, zero knowledge proofs arent actual proofs in a sense that there's always a chance that they guessed it. think about that pen example, there is the chance that i just guessed whether they had a or b all say x rounds. those a s and b s are represented by bits 1 or 0. usually virtually all cryptographic protocols have sizes, meaning they can be 32 bit, 64 bit or 2048 and so on. the number of key size digits defines key size and entropy, that is how many possible variants of 1 s and 0 s orders are there. in zpk s the times of rounds they repeat the challenge is related to the concept above, they gonna repeat the challenge number of times respective to those key sizes and then hardness of breaking the zpk translates into rsa-2048 or aes-256, which are moderns cryptosystems used for passwords in general anyway that neither can you crack (solve the order of pens) nor can you guess (chance that you accidentally name that order).
@@dropagemonem Sure. But the card example is different. As you know in a single round for 100% certainty that the card is red (given the deck is 26 red and 26 black). So is this still a ZKP or not.
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?
one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true. Simple example. There are 2 people, A and B. Now A has told B that he knows B's password for the safe, B's thinks A is lying and tells A to prove that he knows B's password. Now A could just tell B the password, but there are other people in the room and A doesn't want them to overhear, so instead A open's B's safe with the password. Now B is convinced that A knows the password even though A never told B the password, by opening the safe. The zero knowledge part is that A never has to reveal to B what the password is to prove that A has the password.
Rules need to be in place as to how to play the game, and answer is constrained. It sounds out of the world because it is new but will become obvious and something people have been using it in the past albeit not applied to computers.
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.
The sound is too quiet, and I couldn't understand some parts. Subtitles would certainly help. Even if he talks perfect english, the listener might not have perfect comprehension.
It is not reversible, even with infinite time. Multiple different texts can have the same hash, and you would not know which one was originally hashed.
In this case it would have to be reversible in some form, because we still have to count the votes. If it were a proper hash we would not be able to retrieve that knowledge
Hashing isn't reversible because an infinite number of inputs can reach the same hash function output. You can brute-force "reverse" a hash, but you have no way of knowing if that is what the user input originally, unless you also have more information about the input (for example, that the input is an 8-character alphanumeric string). This is actually a weakness when you are using hash functions to verify data. With encryption, you have a 1-to-1 mapping of inputs and outputs with is different for each possible key. Though even brute-forcing encryption requires that you have some knowledge of the input (for example, that it looks like a 7zip archive). If you encrypt random data, there is no way to brute force the key.
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.
The pen example was the best one to refer to this. The envelope example was just to unclear. Thanks for clearing this up a bit more.
I honestly think you explained this better than the video, thank you.
Isn't your example the same as the Ali Baba cave?
@@boyabundabasketball4988 Yes, it is also known as the Ali Baba cave.
@@brixomatic However, this gives you a 100% guarantee that you have the key. If for example you were to walk down the hallway and I asked you to come down the left hallway, I can with 50% certainty say you have the key (if you went right and went through the locked door and came to left VS you were already left and didn't need the key) and repeating the experiment many many times can give me confidence.
He proves he knows about the subject but gives us zero knowledge.
That was the point right?
LOL
i was about writing a similar comment but yours is just appealing XD
IM DYING 😂😭💀
It's like when you and a friend have a secret, and you're in public and he says a keyword for that secret topic, and you're like "ayyyy"
wrgg
I literally just had an exam on this... Next time please upload this one day earlier thank you
But the timing of this video's release has nothing to do with the timing of your exam.
IdeallyYours ... do people here need to state /s as for sarcasm for you?
zero chance of that happening !
Kevin North security
Yeah, but now they can reveal everything you got wrong ....or right lol haha
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.
This explanation was easier to understand and more straightforward than all of the explanations offered in Wired’s “explained at 5 level of difficulty” video on ZKP!
When he first said secret, I totally thought he said cigarette
Me too. Plus I've never smoked.
I ended the video with zero knowledge too. Great Presentation. It is really insightful and well explained. Thank you
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?
Not necessarily. The metadata about who's vote it is could be stripped off before it gets to the tabulation phase.
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!
It's very frustrating that almost all such videos do a perfectly good job of explaining the abstraction, but then do literally nothing to explain the actual implementation. I had about 499 good abstractions, and now I have 500. Still don't know how it's actually done.
Accurate observation.
Read vitalik's blog on it, where he references the original zk-SNARKs paper
Yes, after many hours, I have concluded that it is a scam. Ultimately they bamboozle you and then you are siphoned off into their API and paying for gas to run smart contracts on a shitcoin.
Even when there are examples of math, The initial conditions look nothing like computer programming instructions converted numbers, but mathematical patterns.
Exactly! I'm frustrated for the same reason. I think it might have something to do with public and private keys and hashes. For example a website stores only hashes of its users passwords and never stores the password itself. From the hash it's impossible to recreate the password. When the user logs in with their password the authenticator software only relays the hash of what the user typed in and it's checked to see if it matches the hash the website stores on file. Thus the website knows that the user entered the correct password without even knowing what the password is or what the user entered. Not sure if that's perfect zero knowledge though.
@@JamesBlacklock it's a scam
Finally a topic that is well presented without being common knowledge already. Best video of the year on this channel IMO!
I believe that most of the stuff they post on this channel is not common knowledge. Common knowledge is something known by most people.
Vote Red Pen! Crooked Blue Pen is supported by Big Ink! Draw a wall! Draw a wall!
All pens are corrupted. Vote for a pencil instead ✏️
All forms of writing are bogus. Don't endorse the broken system. Don't vote.
Fake ink!
The peniarchy will fall
Blood Bath and Beyond. This pen is RRR...RRR....BLUE!
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?
Scott Tsai He's explaining that you also need a proof that the voter knows what they're voting, so that someone can't just give them an envelope and tell them to submit that
That makes sense. Thanks!
The problem with e-voting is not the algorithm or the protocol behind it, it's the implementation of it. It doesn't matter if you have plans to build a perfect system if people keep making mistakes trying to build it.
well the protocol is also a problem.
Even before we get to the impossible implementation problem I'm yet to see even a vaguely valid algorithm that lets citizens vote anonymously while retaining the simplicity of invigilated paper votes and restricting vote tampering. It would also have to let the citizens verify their their vote was counted and not discarded or modified. Each step is easy but combining encryption with hashing with signatures while maintaining anonymity in a function voting system has yet to come to my attention.
@@recklessroges Even with paper votes, how do you truly know your vote was "not discarded or modified"? It all comes down to trust.
Any advancements in this area?
@@noder8867 Because votes can be saved and if there is doubt a recount can be ordered. There will always be some trust unless you can recount all the votes yourself, but having different checks and balances reduces trust in any one person.
I can only understand this as a high level overview about the concept which ultimately requires the actual algorythm/crypto to be really understood.
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
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.
Really? I read the Ali Baba cave parable on Wikipedia before watching this video and found it was a lot easier to understand.
No matter which pen you vote for the stationary industrial complex still wins.
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".
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
I don't know if someone has mentioned this before but wouldn't I have to show you that I indeed have a full deck of cards before proceeding? Or is that already assumed? Let's say it's not. How could we ensure that I have a fair and full deck of cards before proceeding
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?
Ok, I just saw this same "demo," but with candy clouds instead of pens. My immediate thought was, "What if the pens ARE the same color, and that's what we want to prove?" Suddenly the swap test fails. So it feels like a particularly trivial example is being chosen. I want to see a deep dive demo into how this idea ACTUALLY WORKS - something that would give me some shot at being able to apply it to anything I wanted to apply it to.
I came here after watching about ZNP from wired and get a bit confused. But this video cleared all my confusions and now I get the hang of it.
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?
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?
But how would you sum the encripted numbers? Isn't decripting them to sum them up giving away information?
There are ways to encrypt data such that you can still apply operators (like addition) on them. For addition, you'd have to build an encryption scheme for which the following holds: encrypt(A + B) = encrypt(A) + encrypt(B)
This would've been super helpful if that was mentioned. To me it was all about "we have envelopes and then we use what is inside to calculate a sum", meaning that he has to open it. Using a special envelope that allows to do math really did not come anywhere in that demonstration.
Cool thx :D It's just my curiosity, but aren't these types of encryption inherently worse than other forms of encryption? Also if you have an example I'd be ecstatic.
It was not well explained. See my comment at the top.
klemen kobau generally yes because once you have relations between encrypted values that can be used to break the encryption. For example there are encryption schemes that make comparison possible. But in this special use case I believe this is fine because we only have 0 or 1 as encrypted values that always should add up to 1.
This video gives zero knowledge about how zero knowledge works.
because how it woeks depends on where you use it. It is only to show what it is.
...but hopefully it gives you knowledge about what it is and what its uses are. I’m sure there are well explained videos for specific ZKPs elsewhere...
He just tell us enough to prove us he knows.
aspie96 voting? Did you not watch to the end?
@dosmastrify, voting example does not tell you how it works. I.e. it does not explain how to use zero knowledge proofs to prove that I know who I voted for in e-election. It merely states in broad terms that it is possible. I think the explanation could have been more... in-depth.
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.)?
Apparently, there exists encryption methods that do allow for operations such as summing.. I know.... i had to dig thru comments to get that "small" detail..
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.
Nice examples. For those who feel that the accent is confusing, just view the subtitles... Google seems to be able to understand his accent just fine!
5:04 - Tom Scott will disagree with you!
The details left unstated in this video about electronic voting using zero knowledge proofs could fill a decent size book. It presumes that methods exist without describing how they might work. On top of which, the example isn't valid in an election where you may vote for nobody.
The ability to vote for nobody is trivially accounted for though.
since by definition 'nobody' represents a singular option. (there's only one possible way to vote for nobody) this just means that 'nobody' is conceptually the same as a single candidate.
So it still means you can vote for 'one' candidate, but that 'nobody' is considered a valid choice of candidate. (you voted for a single candidate, which happens to be the null candidate - eg. None of the actual candidates.)
Why do don't do electric voting is because someone can hold a gun to someone's head.
Same reason why you are not allowed to take photos of your ballot before you seal the envelope.
Also: It is easier to trust physical paper than an electronic machine. Computers are inherently untrutwearthy if you don't know exactly how it does thing. And fraud is much easier when you only need to log in with your electronic ID and such.
I wonder how zero knowledge would solve the most fundamental issue of e-voting.
Imagine a well working paper system: You can stand in the voting room all day, watching people put envelopes in the voting box, taking note of who put one in and how many people put one in. After that you can watch the box opened, every envelope opened and the counting. Thereby you can prove to yourself a lot of things without knowing who voted for what option:
- the total number of envelopes is the total number of actual unique people. There were no envelopes in the box before the voting began.
- each envelope contains only one vote or its invalid - therefore you can derive each unique person voted just once
- each vote represents the genuine free decision of a unique person: The voter could decide freely because he wasn't watched, his vote will be in the box because he put it there and the position where he made his mark wasn't changed
While some part of this may be proven by zero knowledge prove, what prevents a voting machine from having some "votes in the box" beforehand and silently discarding the same number of real votes? Or what prevents a voting machine changing a vote before it was encrypted?
There are actually Zero Knowledge proofs for this as well. Imagine a system, where you encrypt your vote and publish it on a website specifically designed for this election. Then you (and every other voter) can check for themselves, that their vote is actually present there.
After the election closes, the votes are shuffeled, aggregated and the aggregate is opened. For every step, you can give a zero knowledge proof, that this step was performed honestly (assuming that a large enough number of officials who supervise the election are actually honest). These zero knowledge proofs have to be published together with the election results, so everyone can see that the counting wasn't rigged.
Of course I omitted a whole lot of stuff, e.g. how you know that everyone only votes once, but these protocols are way to complex to explain them completely in one comment.
7:15 can someone explain the third ZKP
What encryption technique does zkp use, I know it isn't in the scope of the video but I really want to know???
How does one sum up encrypted votes if they are encrypted?
I've learned about zkp on the example of the Alibaba door while learning about smart-contracts, i find this example far more simple that the example used in the video. if someone could enlighten me about non-interactive zero knowledge I would be thankful
You were way ahead of the curve man!
I had zero knowledge about this before I watched this.
I had a Linear Algebra exam today. This video title about sums it up..
*The video description says "proove" [sic].* Just wanted to let you know...
+3ICE thanks, I'd fixed it but it's taking a while to propogate... >Sean
@@Computerphile Haha I love you guys
I've been applying this method (sort of) my entire life without even knowing I realise now.
Alberto Sonnino is a good teacher.
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.
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?
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??
So what's the difference between this and zk-snarks?
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?
I'm not sure I understand how in the voting example there is a difference between "knowing the content of the vote" and knowing that 1) the votes are binary, 2) they sum up to 1, and 3) that you know what you're voting for
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?
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)?
Not that I've managed to create or find, (and I've been searching for years.)
he did great work on Narwhal which is used in the Sui blockchain
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.
Yea, as most people in the comments are saying it gave only non computer examples for something that is implemented with computers. So the methods used in the fictional examples will not look anything like the real implementations. It leaves us very unsatisfied.
Isn't it just homogeneous encryption (voting)?
awesome intuitive examples!
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 ?
The point is to prove that the card is red without revealing any other details about the card (suit or number). You can easily do this by showing the person all 26 black cards from the deck. This works since a deck only has 26 cards of red and 26 of black. By showing you all 26 black, then the other secret card must be red. You've proven it is red, but the person still doesn't know the suit (diamond or heart) nor do they know the number. Do remember that basic ZPK really only works when all parties involved are honest. In this example, the deck must be only 52 cards consisting of 26 red and 26 black and the person with the cards did not alter the deck in any way. Also, the person who picked the card must have picked a single card from that deck.
The example of the red card is great but I still cannot understand how could I prove something like "I have more than 10k dollars in my bank account" without revealing how much money I do exactly have.
The red card is related to the other 51 by some rules (there are exactly 26 card for each color, and so on), so I can give informations about the other variables related to my card, but the amount of money I have is not related to anything...
Can you make a video on Strings and Pattern Matching?
6:29 What if I want to cast a blanc vote?
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.
How do you restrict one user to vote only once with anonymity ?
thanks! after watching this video, i feel like i have gained zero knowledge.
But one thing about the cards example. This gives me a 100% certainty about you having a red card right?
Don't ZKP have some probability in them? As you have to repeat the experiment many many times to gain enough confidence that person A knows a secret?
yes, zero knowledge proofs arent actual proofs in a sense that there's always a chance that they guessed it. think about that pen example, there is the chance that i just guessed whether they had a or b all say x rounds. those a s and b s are represented by bits 1 or 0. usually virtually all cryptographic protocols have sizes, meaning they can be 32 bit, 64 bit or 2048 and so on. the number of key size digits defines key size and entropy, that is how many possible variants of 1 s and 0 s orders are there. in zpk s the times of rounds they repeat the challenge is related to the concept above, they gonna repeat the challenge number of times respective to those key sizes and then hardness of breaking the zpk translates into rsa-2048 or aes-256, which are moderns cryptosystems used for passwords in general anyway that neither can you crack (solve the order of pens) nor can you guess (chance that you accidentally name that order).
@@dropagemonem Sure. But the card example is different. As you know in a single round for 100% certainty that the card is red (given the deck is 26 red and 26 black). So is this still a ZKP or not.
Wouldn’t the card example not be a true zero knowledge proof due to info leakage? As an observer would also gain info that the card is red
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?
Good video!
Who came up with that intuition explanation? Thats fire!
Is this a zero knowledge proof or a proof by contradiction? What is the difference?
isn't this basically data validation? I mean this is boundary checking is it not?
More from Signor Sonnino please.
Doesn't matter what, I could listen all day. :)
I still don't understand it...
But you're convinced that it works, right? That's Zero Knowledge Proof.
I know that zSNARKs exist, but I don't understand how to apply them to real world problems...
That's why it's called zero knowledge , isn't that a proof ?
one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.
Simple example. There are 2 people, A and B. Now A has told B that he knows B's password for the safe, B's thinks A is lying and tells A to prove that he knows B's password. Now A could just tell B the password, but there are other people in the room and A doesn't want them to overhear, so instead A open's B's safe with the password. Now B is convinced that A knows the password even though A never told B the password, by opening the safe.
The zero knowledge part is that A never has to reveal to B what the password is to prove that A has the password.
Jack Kraken Thank you, that made it entirely clear.
So what are the proofs for evoting? Tell us!
Please guys, make a video about OPUS audio codec, it is quite interesting how it saves space
I don't understand one thing, he is color blinded, how he can know that you tell truth he shifted pens or not?
Good explanations. I finally understand this. Thanks :-)
Rules need to be in place as to how to play the game, and answer is constrained. It sounds out of the world because it is new but will become obvious and something people have been using it in the past albeit not applied to computers.
Great vid man! Helped a lot. Greetings from Israel
Couldn't you tell the number of the card by seeing which number is missing?
Privace Anansi Technologies...?
Excellent explanation ! Tks
What stops someone to agregate a single vote with a bunch of known votes to read it?
Never vote for le pen!
made my day
I kek'd
> watches computer science video
> comments are about pen politics
How can one possibly learn about zero knowledge proofs?
You should consider using a trepied.
is there an implementation example? programming language doesnt matter.
I have to admit that some brain sparks happened when I watched this video, but in the end I still didn't really understood it :/
Does anyone else agree that the opportunity for a matrix pun was missed by Computerphile?
on a nearly future i want to make a machine able to proof just verifying. no way to know how to proof.
John Snow knows math. I'm glad.
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.
It's like cracking enigma, you know it can't be x if you observe y. But you still don't know z
He hired three people to do this video lol
So how do I zero knowledge prove that my vote was binary and the sum was 1 ?
put up subtitle
his english is really good, i dont see why you would need subtitles
The sound is too quiet, and I couldn't understand some parts. Subtitles would certainly help.
Even if he talks perfect english, the listener might not have perfect comprehension.
People still learning english may only understand british/american accents.
You are talking about science, this topic is not known to everyone. So, to understand it correctly, either clear the audio or add subtitles.
Learn English then, idk what to say to you, this is an English language channel.
Handles cards like a magician :)
Computer Science Daddy 😍
How do we prove that a milk colored sky is not blue?
He looks like "Steven Strait" from Expanse
more please!!!
Has anyone told this guy that he looks like John Krasinski?
He talks about encryption as if it were hashing. Encryption is reversable. Hashing isn't.
Hashing is reversible. However, it isn't physically possible before the heat death of the universe.
It is not reversible, even with infinite time. Multiple different texts can have the same hash, and you would not know which one was originally hashed.
In this case it would have to be reversible in some form, because we still have to count the votes. If it were a proper hash we would not be able to retrieve that knowledge
Hashing isn't reversible because an infinite number of inputs can reach the same hash function output. You can brute-force "reverse" a hash, but you have no way of knowing if that is what the user input originally, unless you also have more information about the input (for example, that the input is an 8-character alphanumeric string). This is actually a weakness when you are using hash functions to verify data.
With encryption, you have a 1-to-1 mapping of inputs and outputs with is different for each possible key. Though even brute-forcing encryption requires that you have some knowledge of the input (for example, that it looks like a 7zip archive). If you encrypt random data, there is no way to brute force the key.