If I don't trust the machine to encrypt my vote and ask to see several decryptions first, can't it just always show me what I want to see? You need a separate method of verifying the encrypted vote (and invalidating it, should a vote with that cyphertext appear in the final results).
Yeah, it would make more sense, if any vote you casted would be counted and if you any time (until the end of election) decide to decrypt and verify it, it would been annulled.
If the machine always showed your vote while it was creating the receipt you'd have no way to know if what it showed you matched what was printed. Voters shouldn't be able to decrypt their own receipt because then votes could be sold. Voter decryption would also make it impossible to know if the vote was ever decrypted by them (and thus couldn't be thrown out)
@@Walter-mr5hd I fear that would in term again allow selling of the vote by using the matchstick principle. The person buying the votes may have a policy of checking 5% of the bought votes for whether they were cast for their candidate which in term would make it risky for a person to sell their vote but then cheat.
With homomorphic encryption, couldn't you know what someone (let's say Carole) voted for by taking ten votes including Carole's, do the tally to check how many have voted for Alice, then do the same with only the nine other voters, and that way you deduce if Carole voted for Alice or not?
You're absolutely right that if you can decrypt ballots at will, you can break ballot secrecy. Heck, you could just go and do the tally with only Carole's vote and be done with it! Many E2E verifiable voting systems combat this through "threshold decryption", where multiple mutually-distrusting trustees are required to decrypt the ballots. For example, the key to decryption might be split among voting officials, rival candidates, NGOs and international observers, requiring cooperation between some or all of them to decrypt any ballots.
If I know who I voted for, what prevents me from multiplying my vote against anyone else's to then get a count of both of our's, thus revealing the other persons vote?
My best guess would be that the key also changes? Let's say for simplicity that the keys also need to be multiplied. So the decryption key you get is the multiplication of all keys, which can only be applied to the multiplication of all votes, not a subset of the votes.
Either way there is an unique encryption key for each ballot (otherwise every encrypted ballot would be the same for a vote on the same candidate), and those keys won't be published because that would allow you to decrypt individual votes. So you always need one decryption key, provided by some authority, that could lie... Unless I'm misunderstanding something here...
I was about to say that exact same thing. Being able to "test" your encryption is pointless since you still have to trust that the machine doesn't cheat the real votes. If you placed an evil machine in a place where Alice was popular you could have it switch all Alice and Bob votes and have the "test" switch them back. Granted that's the only thing the machine could get away with since it doesn't know if you're keeping the vote or not so it can't decrypt and re-encrypt since that wouldn't match your receipt.
@@SkySpiral7_Lets_play It doesn't even need to encrypt. It can just generate random strings and store them in a database against your ID. On voting day it could just show whatever you selected and then on the count they can show whatever number they want to get the result they want. You need to be able to verify that your vote is counted. Without the decryption keys, you can't.
@@joshmc5882 I didn't follow why you'd need decryption keys if you don't need to encrypt. But based on what you said I came up with this (which might be what you mean): when casting a vote the voter is given a random UUID and when all the votes are in they can release a list of UUID to vote cast and the voter can confirm their UUID has the correct candidate name next to it. Since it's a random UUID looking at the published list won't tell you who is who but will allow you to verify the total count. Of course this would allow you to sell your vote since being able to verify my vote can also be used to prove my vote to another person. No keys of any kind needed. Of course there's no way to prove that the system hasn't been artificially padded with extra votes.
I also like to live dangerously. ;) Years of telling people that we shouldn't click on random links on the Internet. And yet people like you and I still blindly scan QR codes with our telephones, that contain so much information about us.
Luckily, the QR codes are not able to automatically execute anything, like clicking links might! At least, my barcode app only shows the content and does not immediately do something.
Great, and how do you confirm that the computer telling you what kind of ballot it is, isn't just regurgitating the value you selected, while your vote itself wouldn't truly decrypt into the opposite vote? You can't separate the machines so that the computer's only information about your vote is your key, because otherwise your receipt, plus an algorithm, is all that's needed to decode it. However, what I'd do, to avoid pretty much any scrutiny save someone deliberately looking at the source code and understanding the whole encryption process - which would be kept secret for safety reasons, is to simply double-encode everything. Instead of 2 possible choices, instead I design the system for 4 possible choices. In this way I can record 4 states in the encrypted reciept. Who they ACTUALLY voted for, and who they're going to be Counted for. So we have: Vote Alice, Count Alice - Candidate 00 Vote Alice, Count Bob, - Candidate 01 Vote Bob, Count Alice, - Candidate 11 Vote Bob, Count Bob - Candidate 10 If anyone requests their vote back in some super-secure way: If (Candidate == 00 || 01) return 'Alice'; If (Candidate == 01 || 10) return 'Bob'; And the part of the code that tallies: Alice.count = Candidate 00 + Candidate 11; Bob.count = Candidate 10 + Candidate 01 The decryption machine will know who it should SAY they voted for, and tell them accordingly. While the final tally will report the results of column 2 by comparing the summed results from state 1 and 3 against 2 and 4. It seems to me that adding this in would be incredibly trivial - the software is going to be modular for the number of candidates, so doubling the number of candidate states wouldn't be a problem. And the part of the Program that decrypts and the part that tallies likewise will need a very sparse modification to pull off the deceit.
***** To be honest, I'm just very interested to know how it is possible to do math with an encrypted cypher at all. If that's possible, then I'm sure we're only a few years away from manipulating the cypher to list as Alice when decrypted and count as Bob when encrypted. The way Xylos144 set it up seems like it'd be trivially easy to do. I mean, if the computer has to make a cypher that lists as Alice and counts as Alice, why would it be difficult to make it list as Alice and count as Bob? The only way I see that being impossible is if there was an algorithm that made "lists as Alice" automatically leads to counting as Alice. Which may not be the case.
This solution is literally combining all of the worst parts of electronic voting and paper voting into one clusterfuck of non-verifiable, highly vulnerable to fraud, and easy to sell votes system. I totally recommend you read the paper CCCEx09 that is linked in the description, it goes over the exact E2EV process and all of the nuances of the mathematical hashing algorithm. It really isn't that complicated, yet, just like RSA, it is highly effective.
OK, but with the match stick method, you're trusting the system isn't rigged, just like without it. If you want to make sure your vote's counted it could just as easily save your key and then generate what you said you voted for, but count it differently. It only proves the vote wasn't accidentally wrong, not intentionally.
Re: claim at 1:06 that selfies allow vote selling, here are three ways that taking a selfie doesn't really enable vote selling: 1) You can take a picture of a blank ballot, and in something like MS Paint, you add marks that look like a pen to the oval, or to connect the arrow, or however a completed ballot looks in your jurisdiction. Then you post the altered image. 2) You can take a picture of a completed ballot, then make a stray mark on the ballot. Take your spoiled ballot back to an election judge and request a new one. Then you can fill out the new ballot however you want. 3) In jurisdictions with mail-in voting, you can fill out the ballot at home, take a picture of that ballot, then go vote in person instead of mailing in the home ballot.
Still nothing is better than a traditional paper vote. Count it in front of people after the voting is done, is what make people sure that the counting was not RIGGED
Detecting fraud is one thing. Correcting a result is another. I'm Aussie and there were so many problems with one election it was redone (WA senate at a fed election).
Human-counted paper voting limits the counting methods to very simple ones, which tend to lack certain fairness criteria (remember that with preferential voting, it isn't as simple as just counting who has the most votes). Using computers to count allows for more complex and fairer methods to be used, for example using a method involving finding a Smith set (taking quadratic time in the number of candidates).
Well look at Switzerland. We can vote for the whole congress, people give a list of a few dozens of people as a vote. They're all counted by hand, no problem.
Since there could be social pressure for or against abstaining, I would hope that there's also an encryption scheme for all the non-votes. So the online database would include all eligible voters (whether they went to the polls or not), and those who abstained would have encrypted receipts as well, impossible to differentiate from the others.
So if all the votes are public, and you can check the results by yourself, can't you tell what each person's vote was by checking the full list, and then checking a list that doesn't contain that one person's vote?
I suppose, but you already know more than you should about the tally in the example. The example used a scheme of 0 for Bob and 1 for Alice, so one result, tallying 10 people, is 0+0+0+0+1+1+1+1+1+1 = 6 votes for Alice. The problem is, internally, the machine can use any sum it wants, and it can come up with the sum using any particular fashion. The machine can tell you that you voted a certain way with one number, but then use another number in a different formula for the official count.
You can, as he said, multiply the encrypted votes to tally the total result. But you can't, and you shouldn't be able, to decipher any individual vote (to avoid selling votes and for privacy).
To me, those 'encrypted votes' are just magic numbers from a black box. I still have no way to verify that my vote for candidate A was actually counted for candidate A, and not for B
Yeah, and that's a pretty huge problem for a voting machine... You have to trust some obscure untransparent central authority/machine to count votes correctly, which could be easily tampered with. I'd rather have some people selling their vote than the entire process being untransparent and easily manipulable.
The decryption code isn't something that's public. When you multiply together all the votes, you still have an encryption that needs to be decrypted. If you knew how to decrypt it in the first place, you'd just decrypt that single code.
It is completely anonymous as long as no one can ever use the decryption code except to check their own test-vote or when the winner is publicly determined. The fact that you can multiply votes together except for one simply doesn't matter because if you can decrypt the final product, you can decrypt any individual vote.
The integrity of the voting process is a separate problem. Votes in paper-based systems today can typically be associated with the voter by their serial numbers, but these sheets are tightly controlled by election authorities. Though I agree, the problem of securing a single key, easily copied, that decrypts all votes is much riskier than the unique and difficult to copy counterfoils. The verifiability of some electronic voting systems is a nice property. But I still don't think it's better than traditional paper ballots that are well understood and relatively easy to protect. Not really seeing the huge advantage to electronic voting, other than maybe cost and speed, neither of which are things that elections should be optimized for.
This would create a situation where a single person/department/group (whoever created the encryption code) would be able to find out how any person voted - there would be no trust that the voting was confidential!
Well, I understand that the voting process will not be done online - only the results posted - so voting is done as normal with all the ID checks that entails - so no more issues with multi votes than what is already present I guess!
Yeah, but if you sit in a room with one of these machines and vote for some candidate under a bunch of pseudonyms all day, you can turn a close election by yourself. Or just have the voting machine do the voting itself.
I'm curious about one thing: if the multiplication of encryptions is the encryption of the addition of the plaintexts, and the decryption of that multiplication is revealed to the public, wouldn't that mean that you can decrypt the individual votes as well? Since it seems difficult to me that the multiplication of the results of one code happen to coincide with the additions of the plaintexts in another code in every possible scenario. How is that dealt with?
My understanding is that the individual votes may be decrypted (that's how their zero-knowledge proof works) but only by election officials. But then how would election officials prove that they decrypted the ciphertext properly without revealing their private key and therefore everyone's voting choice? I guess they could generate a plaintext and an r value that would encrypt to the product of the receipts (by r value, I mean a padding value - the plaintext is padded because otherwise all "0" and all "1" votes would look alike and the ballot wouldn't be secret). But then again I don't know if that could also be constructed with the private key. I guess that it couldn't because otherwise the system would be useless. Also, the fact that the election officials could decrypt individual votes means that the vote isn't totally secret. Then again, decrypting individual votes might be useful against someone who decides to encrypt a large number and try to submit that as their vote.
Sure trust corrupt officials working for someone like Lukashenko or Maduro… or cast doubt on elections like the US 2020 elections or Crimea referendum. Fun times!
Couldn't you simply tally all the votes but one by multiplying the ciphers and the one choice that's missing a vote when compared with all the votes tallied would be the one you didn't tally in the first place, thus revealing the encrypted vote value? For example, I tally everything and get 6 for Allie. Then I tally everything except for Jubal - if I get 6 for Allie again, he voted for Bob, and if I get 5 for Allie, he voted for Allie?
But how does the voting machine decrypt that "test" vote? That implies that there is an algorithm for decrypting a single vote, which defeats the whole purpose.
I see Ron Rivest at the RSA security conference every year. Cool to see him on Numberphile! I'd might actually start voting again if something like this ever gets implemented.
1:19 but you could take the picture then change it and sell your ballot to all the candidates and vote for who you like, they cant verify that was the actual ballot submitted
What key decrypts the summed ciphertext(votes)? Would like a more in-depth video on the homomorphic encryption part. When he briefly explains it sounds like you can figure out everyone's votes by simply summing pairs of votes.
Did i miss something or it's very easy to see who someone voted? You just need to do the sum over all the votes and then do it again without bob vote and i can see if bob voted 1 or 0
+Guest6265+ Then voting observers have a way to generate DECRYPTION key for list of N voters? That seems too magical for me, cuz my brain is stucked to idea that encryption and decryption key for any algorithm have to be generated at the same time.
at 3.50 it tells u that the product of 2 encryption will be the sum of the value so I guess that doesn't matter how many votes u are summing. If what u are saying is true that means that they are using an encryption specific for a certain amount of votes and that can't be true because the encryption must be chosen before the election and at that moment you don't know exactly how many people are going to vote
Guest if that is the case than all you need is one single person who didn't vote to ruin the whole election. Also, as far as I understand, that's not how the system is described
What if you take your vote out of the set, multiply them all together, and then decrypt? In this example, wouldn't the total decrease by one if the vote had been for Alice?
@@Mrtnlys sorry, that can't be the entire answer. What would be the point of all of this if it's just the voting authorities who announce the results at the end? There needs to be a verification process: any user can do the encrypted tally, but can't decrypt it; only authorities can and they announce the result. Then they need to prove that their decryption is indeed correct. I believe there are protocols for this, but it's great omission from the video. Without it it makes zero sense.
@@Czeckie I was thinking the same thing. A solution I thought of would be integrating a block chain where you have an decryption key for your address on the chain and then the actual decryption key for your vote. The vote decryption key is public but the address is not. Making sure that they stay anonymous
In practice it is harder to ensure correct tallying of votes. For example, the encrypted token could contain 2 bits of information: who you actually voted for and who the machine wants to tally the vote for. If the voter checks the correctness (thereby voiding the ballot), the machine reports the first bit, and when the voter submits the vote the machine tallies the second bit.
I googled it and it looks like how it works is not too far from normal encryption works. Kind of how multiplying two numbers is easy but factorizing them is hard. They way homomorphic works is kind of the same idea but uses some other math so that there is some margin of error to the equations, kind of like working with two irregular factions at the decimal level. You can also look up, "Ideal lattice" and "Ring learning with errors" which will show you the raw math and what is really used.
This is an improvement on other electronic voting methods, but there's still a lot of ways to attack it. For instance: if you voted for candidate A, the machine could tell you that you voted for candidate A even though it's internal record has you voting for candidate B.
And even though people are able to verify that the correct result is being decrypted at the end (by everyone multiplying all votes), people would still have to rely on the final decryption not being rigged.
How does the voter know the machine isn't just faking decryption? Ie. machine always encrypts Alice, but remembers of which receipts should be for Alice and which for Bob. When you test your receipt, the machine doesn't actually decrypt it, just checks the table and spits out the expected answer so everything looks aboveboard. Also, fact that the receipts *can* be decrypted by the machines seems to pose a privacy threat. Whoever owns the machines can presumably decrypt any receipt. How is voter privacy maintained? Maybe I'm missing something or the video didn't have time to delve into these, but it is not obvious to me. Given modern recording tools selling votes is very hard to prevent, unless we start entering the voting booth nude. Since that is probably not going to fly, I would stick with plaintext receipts that are entered into regular urns for later verification by manual methods.
We can't make vote selling impossible, but we can make it unfeasibly expensive and risky. To sell a vote under our current system you would need a camera or person watching the path from the voting booth to the ballot box. Assuming you went with the less-conspicuous camera, you'd still need to verify the footage. To do this on a large enough scale to sway an election without getting caught is just not reasonable.
I think everyone in this system have the encryption key. When you see a receipt though, you can't decrypt it. That is because the plaintext is something like "voteAlice_randomchars_fd#8o^20}[l". But when you are shown the plain text you can easily verify it using your own PC or smartphone by encrypting it and checking that it matches the ciphertext.
The only trouble with this system is that it doesn't grant you provable anonymity: anyone in charge of the voting machine can potentially decrypt every vote and check who voted what. And that's a massive no-no. With paper ballots anonymity is granted by the assumption that the papers are identical and that once cast, they mix around in the box, making it impossible to trace back any single vote to any single voter. While at the same time the physical arrangement of the polling station, and voter identification before you enter the booth guarantees that you can list the name of every person who voted. These seemingly conflicting requirements make it incredibly tricky to make an electronic voting system that can be trusted to the same level as the paper ballot. (Which of course itself is far from perfect.)
Wait a minute. If I know my vote and its encryption could I not build the sum of every pair of myvote-anothervote and determine the value of the other vote from it? That would decode everyones vote once one is known. What am I getting wrong?
You can't decrypt an encrypted vote with one vote. You would need thousands of a votes and encryption pairs to get anything close to the original encryption method. There are countless ways of making one or a few votes mathematically yield their encryption pairs.
What got me confused is the statement made that every voter can always verify the sum of published votes and no dependency on the number of evaluated votes was mentioned. The election could theoretically be held with there being 2 voters. Verifying the election outcome is identical to precisely inferring the other persons vote in that case. So if what you said is true that would mean that the (perhaps approximate) total number of votes cast is somehow a parameter of the shared key generation of all votes in that election and it is generated in a way that performing partial sums of votes does NOT yet correlate significantly with the value of that partial sum. Only almost complete sums start to converge on the total sum. None of that was hinted at and your answer does not quite satisfy me, excuse me if I failed to understand. Or is the encrypted key one gets to take home not the encryption of ones own vote but some other validly cast vote so no one knows one valid pair in the first place? If so I completely missed that.
What about this case: After we have all the votes and "multiply and decrypt" them and say it is 16 for Alice. Then i remove my vote and do the same thing. Then the result can be for example 15 for Alice. That way everyone know that i have voted for Alice. How is this case dealt with?
Vasilis Keramidas You can't remove your vote. If you're checking the system, it's not a vote at all. Imagine you were in a country with a complete democracy and they used plain paper poll booths. The counts came in and there were 2 million votes for Alice and 1 million for Bob. You "removed" your vote and they recounted. There are now 1.9 million for Alice and 1 million for Bob. No change in how voting security is implemented would stop that scenario.
Sure there is. With paper ballots, there's no way to know what is "your" ballot. In such a system, removing a ballot and recounting would not reveal how an individual voted.
How would this system handle write-in votes? It seems to me that you'd need each candidate to have an encryption key issued in advance for it to work. Even if the system issued encryption keys to new write-in candidates on the fly, you'd have no way as a voter to know that your vote for Alice counted together with someone else's vote for Alice Smith, and another person's vote for Alice Smith/John Brown (a running-mate) etc.
instead of getting a code for who you voted for you should get a code for you name or ID. Then all the votes should be listed publicly alongside the encrypted codes of the voters. This allows each person to verify their own vote and anyone can tally all the votes to verify the result and also this keeps each voter anonymous.
That would only work if every voter was given their own verifiable encryption key. That isn't feasible, and it would defeat the purpose anyway, because if you can verify your encryption key, then you can still easily sell your vote.
It isn't impractical at all. In fact, the mafia used to do this on the east coast of the US, and it was effective. The mistake that you're making is that you assume that the person buying votes is the candidate. That wasn't the case. It was the people that we would now call lobbyists.
I don't think you would want the machines to be able to decrypt the votes. I think a simpler method would be to show you the encrypted value you would get by each vote next to the name, if the person is dubious they can remember a distinct features of the vote they want from the others (possibly with the ability to have new encryptions generated using a different pad if they cannot find anything distinctive enough), they can then check their printed vote once it comes out. The only way this could be tampered with is if the machine can predict who you want to vote for before you do in order to swap the displayed values, but in the example given in the video, the machine could just lie about the decryption (assuming that the machine has been tampered with). Obviously, there are other considerations: in particular about the padding that is used to avoid the same vote being encrypted with a different pad for each making them look different. I am sure a cryptographer doing this as a living can work out a reasonable way of achieving a unique pad that must be the same for all of them as its only valid for the session. Removing the ability to re-encrypt is also an option.
you've moved the problem to the verification machine, as it can hold in memory your true selection and replay it back to you despite encoding the alternative.
666Tomato666 But that's not enough. If the election officials just tell us "The total tally is decrypted to 11 votes for Ally and 5 votes for Bob", then you're back at square 1. The decryption algorithm, with all details like keys, have to be publicly available so anyone can check if there is to be any point to it at all. I am wondering how they can do that without giving away the key for every single vote.
Xeverous But this is not hashing. Hashing is, by definition, irreversible, while this is encryption, where if you know the algorithm, you can go back and forth between encoded message and plaintext. Because that is the whole point. You are SUPPOSED to be able to go back from your reciept to what you voted, if only you're given access to the algorithm. That's what the machines do if you decide to test your reciept.
MasterHigure you can do the decryption by spreading the key among multiple people (like Shamir Secret Sharing, but with all parties needing to be present for it to work) and can do the decryption publicly if that public ceremony includes all candidates, you get legitimate election
If you can multiply two ciphers together to add the votes together, you could check each of a set of votes by multiplying them together in various combinations.
Comparing a computer that can have code that handles certain scenarios is completely different from a matchbox where the match cannot change once it has left the warehouse. I don't see it being outside the realm of possibilities that a machine could 'know' that the cypher decrypts to Alice and this is what it spits out when checked, but when multiplied with other votes, comes out as a vote for Bob.
The "multiply and decrypt" method would not be possible in hiding votes.....because a system would have to be created to allow any number of votes to be made, making it a variable constraint. This means that if only one person votes, then you should be able to reliably come up with how many votes toward a candidate....which reveals that person's vote, and if you can reliably do this with each individual along with the total mass of population, then you have revealed EVERYONE's vote. There may be a possibility to put votes within "blocks" where each block is considered separately and only if the entire block is filled will the tally work....however, with encryption techniques, this creates a flaw in the system where an individual can decipher the block because you've had to add information to determine the block itself. It's similar to having a one-time pad key, only to use it on multiple messages, defeating the purpose.
Cool, CGP Grey and the Nail and Gear of the Hello Internet podcast both appear on the voting machine. Is "Vote-A-Tron-6000" a nod to "Fit-A-Tron-5000" from Hello Internet?
4:18 "...What you want to do is add them up... You multiply all those ciphertexts together and end up with a sum of all the plaintext ballots"? This needs some further explaining. I'm sure I could research this, but I would expect the video to do more than leave the viewer hanging. Besides, multiplying those large numbers would yield an unwieldy product. The word "Homomorphic" doesn't explain anything either. It simply means a system in which some processes can be carried out on the ciphertext (the encrypted stuff the voter sees). It looks like the answer requires some reading en.wikipedia.org/wiki/Homomorphic_encryption
I think public verifiability is more important than preventing vote buying. I think that the voting receipt hash should also hash with something like one's SSN, such that you could decrypt your individual receipt with your SSN, essentially using the voting receipt as a public key, and the SSN as a private key. That way all of the voting receipts can be published, and everyone could verify that their vote was cast the way the wanted it to be cast. Once everyone has verified their vote, all of the votes are published, but with a new hash attached to them - at this point, it becomes anonymous, except for area demographics.. So every vote is now made completely public to see, except that you can't see who made that vote. The new hash can also be verified with the SSN,, so that you can look up the anonymous hashes for your voting precinct, and find your hash to verify that it says what it should say. Then, once the anonymous vote is verified, the anonymous, publicly available votes are tallied together and the winners are announced.
But if you need the decryption key to verify the product as well, you still have no way of knowing whoever done the tallying wasn't making the results up.... So you still have to trust the system with no proof.
you don't have decryption key, but you have encryption key. After they show you plaintext you can encrypt it back and see if you get the same ciphertext.
Well, they give you plain-text + seed for random number generator("IV" is probably a correct term for this) that was used to encrypt that particular message. Often, non-deterministic encryption is achieved just by prepending a few random bytes to the beginining of plain-text message before encryption. If somebody decrypts such message, he will see the IV in the first few bytes at the begining of the message. In the video they skipped over a lot of details, so it's no wonder that everybody looks so confused in the comment section.
Ok. But wouldn't it become kinda easy to discover how other people voted then? Once you know the public key + you only have a few options of vote (say Hillary or Barrack) + you brute-force find the random bytes used to generate other people's ciphertext. Considering everybody's ciphertexts available online after election like forever.
Just make IV long enough. Even to count from 0 to maximum 256 bit number will probably take more than lifetime of our solar system with modern supercomputers.
Just give everyone a micro chipped counter that has a number pad on it ,in the booth you place it on top of the picture of the candidate you wish to select the number pad then flashed for a few seconds allowing you to check is correct you then take it out the booth and place it in the box if votes are all held on the same day and the counters are encrypted with the same encryption algorithm it makes it easier for counting , additionally chips would be harder to spoil .Further more you could make the number pad react to a camera flash making it hard to buy someone's ballot
What did I miss here: - You have access to all encrypted votes so you can do the homomorphic sum yourself and see the sum of votes - You get your own encrypted vote Can you then not - take the sum of N votes and do the tally, then take that N votes plus your vote and do the tally and compare, and thus check if yours is voting for the right candidate? - in fact, do this with every vote that you have in encrypted form and check what it voted for? I don't quite know how that encryption would work, but I imainge one for each candidate might be enough to check another encrypted vote by the difference of the sum. How is this prevented? I mean, it should be,shouldn't it?
Well the homeomorphic encryption part might be much more challenging, since that type of voting is not as simple as a simple tally of selections. But the other parts could work.
Are there different keys when doing a multiply-then-decrypt vs. decrypt-then-count? Another way to ask the question is can the public read the web and tally n>=2 votes with a public key rather than the private key used by recorder?
I think you need to preface the video with the computerphile video on public keys. I see a lot of comments around the safety of public key encryption systems which are already explained in the video with R. Miles.
I'm a little confused about the "testing your vote" method. If we don't trust the computer or its programming, how do we trust the "check" button operates exactly the same as the "submit" button? The check button might always give you what you punched in, while submit sends in something else. There must be if-then logic to eradicate the check result and that if-then logic could be manipulated to change the submission upon "submit" but not "check".
Because the check button happens after you get your key, and the machine doesn't know whether you're about to press the check button to retroactively invalidate your vote. It would have to gamble that the one it's going to rig is the one you don't invalidate. If it fails that gamble even once, the entire process is called into question.
Excel Kobayashi The order of operations you describe makes way more sense. The way I heard it was: you don't get anything from the device until you chose whether it was a test or a submission. If it's a test, it tells you both the key and ciphertext, if it's a submission it just gives you the ciphertext. I guess I had a derp moment.
What prevents someone from doing the multiply and decrypt thing to your vote and just one other? If you know who you voted for you can easily deduce what the other person voted for, which defeats the whole purpose of this system.
What I don't get is how the final tally is done and then decrypted. Couldn't you decrypt an intermediate tally, add one vote and decrypt again to unblind that one vote? How is the final decryption only possible on the total set of votes?
8 ปีที่แล้ว
does this mean that each machine, in order to be able to decrypt, has to store a private key internally, which, if hacked, can be used to decrypt people's votes? or does it generate a new private key for each vote? Or more generally, does homomorphic encryption, as described here, has to use one global private key to work?
I have a question. If you take a solved rubik's cube and do any set of moves (which can include turning or rotating the cube) and repeat it a couple of times you will get back to a solved cube. can you please explain why?
Felix Schlosser think of it in numbers. Original is 0 When it comes back to 0 it terminates When it goes to 100 it should terminate because the pieces aren't in the original place but they have the same solution of that makes sense. If you take the function x+25(make it right clockwise for example) it will add up to 100 after 4 times. Now let's say you have the function(x+25) then you want to do (x-3)which is turning the top counterclockwise let's say 25,22,47,44,69,66,... eventually it will turn up a multiple of 100 No matter what you do it will always end up back to the original solution(multiple of 100)
How do you know that the machine just doesn't remember which candidate people voted for, and when they have their ballot voided and decrypted to make sure that the machine is working, it just spits out what it memorized instead of what the actual ballot barcode decrypts to? The machine could still be changing entries as they come in.
Because you could still vote for another candidate just to check-and invalidate that vote in the process. Whether you wanted to check the machine by voting A, B and C in random sequence and number of times, it would be impossible for the machine to guess your next vote.
The machine could still cheat you. Let's say the following machine is rigged towards candidate B: Say the candidate I truly wish to vote for is candidate A. I go to the machine and decide I'd like to test it, so I vote for candidate B. The cheating machine counts a vote for candidate B, remembers my name and that I voted for candidate B, and prints me a slip with "B" encrypted on it. I put it in for verification, and instead of actually checking what is encrypted on it, the machine just looks at what it remembers me voting for and will print out "B." The vote is invalidated and removed from the total count. I decide that isn't proof enough for me that the machine isn't rigged, so I cast a vote for candidate A with the intent to invalidate it later. The cheating machine counts a vote for candidate B, remembers my name and that I voted for candidate A, and prints me a slip with "B" encrypted on it. I put it in for verification, and instead of actually checking what is encrypted on it, the machine just looks at what it remembers me voting for and will print out "A." The vote is invalidated and removed from the total count. NOW, I decide that I trust the machines. I cast my vote for A and the above process occurs. How have I not been cheated? It has nothing to do with the machine guessing my vote.
I see; This is more of a question of morality from the electoral authority. This is also true for conventional voting systems; either the voter could claim am incorrect vote, or an observer claim to have observed misbehaviour. I whole heartedly believe my self, that computers shouldn't be used in important voting as something could easily be altered whether it is with intent or not; they're very error-prone.
How would a system such as this handle a more complicated voting system like instant runoff or single transferable vote? Does the computer just take everyone's preferences and spit out a number?
What if the voting machine remembered that you tried to vote for Candidate A, and gave you an encrypted receipt for a vote for Candidate B. If you try to decrypt it at that voting machine instead of submitting it, it'll lie and tell you that you voted for Candidate A because it remembers from earlier.
how can you encrypt it in such a way that you can understand decryption but not do it yourself? it seems that any long enough number could be made to show a name given enough strange rules?
Wouldn't the part about the checking the inscription be able to allow people to find out clues with enough data, like you could remember the number then get a check and then you know what one match is. if you get enough people to remember their code then you could deduce the encryption key right. At least i think that would be possible but i don't know the mechanics of encryption thoroughly enough to be confident
If everyone can create the summed ciphertext by multiplying the encrypted votes together (and decrypt it), then can't you figure out anyone's vote simply by comparing the decrypted ciphertext sum to the a sum of all the votes except for the person you want to know the vote of? It seems that if everyone can verify the sum in this manner then you can figure out anybody's vote.
The point is that you cannot decrypt anything, only the voting authorities can.You are only able to verify that the voting authorities are decrypting the correct ciphertext by multiplying yourself.
If you still have no idea what the summed ciphertext decrypts into, then what stops the authorities from saying it decrypted into whatever result they want?
The problems I see: - if the results are published, can't we just brute-force the encryption key since we know the ciphertext and cleartext (we can multiply all numbers together to get the result and we know how the election went because that also has to be public?) - Each voting machine contains the decryption key. (that's just inacceptable. if any1 gets hold of a machine, they can just decrypt all datasets) - not an expert on homomorphic encryption but can you pad the cleartext in order to make each vote look distinct (encr(a) != encr(a)) (because I don't think you can) - I don't know how well this works for more than two candidates... and generally I am not a huge fan of publishing any reversable, connectable (to a person) data online. whatsoever. no matter how "unbreakable" the cipher is. because I believe that everything can be broken given enough time.
Question 1: How can I tell that nobody added a nonvalide vote? Question 2: If the encrypted voting of all people is public, who will stop me from decrypting in 20 years with bruteforce and strong computers, that we can not even imagine yet?
For your first question, the same way we do now. We check the list of people who voted against the list of people who are allowed to vote. Your second question is a real concern, but that problem lies at the heart of all cryptography. All we can do is make the encryption strong enough that by the time it's decrypted, the data will be worthless. A bigger danger than brute force is how do you keep the keys secure for that long. The videos proposed system has thousands of people holding the decryption keys; we'd need to trust all of them.
With the homomorphic encryption approach: if all encrypted votes are public, and it's possible to multiply encrypted values together and get the sum of the plaintext, can't I use *my* encrypted vote and anybody else's vote to determine how any other individual voted? If I know I voted for Alice so that's a 1 then multiplying with one other encrypted vote gives me a 1 or a 2, I know that the other voter voted for Bob or Alice, don't I?
The only problem I see is the decryption of the tally. Sure, you can check that all the encryptions add up correctly, but Since you don't have the algorythm for the decryption in the end you have to trust that the sum of all encryptions decrypts to what officials say.
Can we please talk about the Condorcet criterion? I think showing the mathematics of voting and alternative voting methods would be a great subject for Numberphile. I know CGP Grey has some great videos on voting systems, but he doesn't go into the math in the way that Numberphile might.
Couldn't you count all the encryptions to see the total votes for Alice, then do it again with all but one and see what he voted for? if you get the same number he voted for Bob, if It's one less votes for Alice he voted for Alice
The QR code next to "You voted for: Alice" links to Tom Scott's e-voting video
I will video record myself voting for the same party every year and in primaries.
Is that a little CGP Grey face on the VOTE-A-TRON?
Upfade Must be an alternative vote-a-tron
Henry Tompkinson HAHAHAHAHAHAH😂😂😂
Yeah, it is
Upfade isn't the symbol above it almost the symbol of his podcast
I spotted that !
7 years late...
If I don't trust the machine to encrypt my vote and ask to see several decryptions first, can't it just always show me what I want to see? You need a separate method of verifying the encrypted vote (and invalidating it, should a vote with that cyphertext appear in the final results).
Yeah, it would make more sense, if any vote you casted would be counted and if you any time (until the end of election) decide to decrypt and verify it, it would been annulled.
If the machine always showed your vote while it was creating the receipt you'd have no way to know if what it showed you matched what was printed. Voters shouldn't be able to decrypt their own receipt because then votes could be sold. Voter decryption would also make it impossible to know if the vote was ever decrypted by them (and thus couldn't be thrown out)
@@Walter-mr5hd I fear that would in term again allow selling of the vote by using the matchstick principle. The person buying the votes may have a policy of checking 5% of the bought votes for whether they were cast for their candidate which in term would make it risky for a person to sell their vote but then cheat.
With homomorphic encryption, couldn't you know what someone (let's say Carole) voted for by taking ten votes including Carole's, do the tally to check how many have voted for Alice, then do the same with only the nine other voters, and that way you deduce if Carole voted for Alice or not?
You're absolutely right that if you can decrypt ballots at will, you can break ballot secrecy. Heck, you could just go and do the tally with only Carole's vote and be done with it!
Many E2E verifiable voting systems combat this through "threshold decryption", where multiple mutually-distrusting trustees are required to decrypt the ballots. For example, the key to decryption might be split among voting officials, rival candidates, NGOs and international observers, requiring cooperation between some or all of them to decrypt any ballots.
If I know who I voted for, what prevents me from multiplying my vote against anyone else's to then get a count of both of our's, thus revealing the other persons vote?
Harlequin314159 or multiplying everyone but one person and seeing how that changes the tally
You seem to be forgetting that people run the government
My best guess would be that the key also changes? Let's say for simplicity that the keys also need to be multiplied. So the decryption key you get is the multiplication of all keys, which can only be applied to the multiplication of all votes, not a subset of the votes.
If that were the case, you wouldn't be able to verify the final tally, so the creators could easily lie.
Either way there is an unique encryption key for each ballot (otherwise every encrypted ballot would be the same for a vote on the same candidate), and those keys won't be published because that would allow you to decrypt individual votes. So you always need one decryption key, provided by some authority, that could lie... Unless I'm misunderstanding something here...
But how can you verify that when the machine tells you your vote has been properly cast it hasn't been contrived to lie to you?
How would you know that the machine didn't change the key or algorithm when it is being tested? Like with the Volkswagen emissions
I was about to say that exact same thing. Being able to "test" your encryption is pointless since you still have to trust that the machine doesn't cheat the real votes. If you placed an evil machine in a place where Alice was popular you could have it switch all Alice and Bob votes and have the "test" switch them back. Granted that's the only thing the machine could get away with since it doesn't know if you're keeping the vote or not so it can't decrypt and re-encrypt since that wouldn't match your receipt.
You have to add a verification mechanism.
@@SkySpiral7_Lets_play It doesn't even need to encrypt. It can just generate random strings and store them in a database against your ID. On voting day it could just show whatever you selected and then on the count they can show whatever number they want to get the result they want.
You need to be able to verify that your vote is counted. Without the decryption keys, you can't.
@@joshmc5882 I didn't follow why you'd need decryption keys if you don't need to encrypt. But based on what you said I came up with this (which might be what you mean): when casting a vote the voter is given a random UUID and when all the votes are in they can release a list of UUID to vote cast and the voter can confirm their UUID has the correct candidate name next to it. Since it's a random UUID looking at the published list won't tell you who is who but will allow you to verify the total count. Of course this would allow you to sell your vote since being able to verify my vote can also be used to prove my vote to another person. No keys of any kind needed. Of course there's no way to prove that the system hasn't been artificially padded with extra votes.
See the second video with Ron Rivest about how to check an election result: th-cam.com/video/ZM-i8t4pMK0/w-d-xo.html
loved the video!
Nice QR code!
And for anyone checking, they are all the same as well as far as I could tell, except the first one!
I also like to live dangerously. ;)
Years of telling people that we shouldn't click on random links on the Internet. And yet people like you and I still blindly scan QR codes with our telephones, that contain so much information about us.
Luckily, the QR codes are not able to automatically execute anything, like clicking links might!
At least, my barcode app only shows the content and does not immediately do something.
Great, and how do you confirm that the computer telling you what kind of ballot it is, isn't just regurgitating the value you selected, while your vote itself wouldn't truly decrypt into the opposite vote?
You can't separate the machines so that the computer's only information about your vote is your key, because otherwise your receipt, plus an algorithm, is all that's needed to decode it.
However, what I'd do, to avoid pretty much any scrutiny save someone deliberately looking at the source code and understanding the whole encryption process - which would be kept secret for safety reasons, is to simply double-encode everything.
Instead of 2 possible choices, instead I design the system for 4 possible choices. In this way I can record 4 states in the encrypted reciept. Who they ACTUALLY voted for, and who they're going to be Counted for.
So we have:
Vote Alice, Count Alice - Candidate 00
Vote Alice, Count Bob, - Candidate 01
Vote Bob, Count Alice, - Candidate 11
Vote Bob, Count Bob - Candidate 10
If anyone requests their vote back in some super-secure way:
If (Candidate == 00 || 01)
return 'Alice';
If (Candidate == 01 || 10)
return 'Bob';
And the part of the code that tallies:
Alice.count = Candidate 00 + Candidate 11;
Bob.count = Candidate 10 + Candidate 01
The decryption machine will know who it should SAY they voted for, and tell them accordingly. While the final tally will report the results of column 2 by comparing the summed results from state 1 and 3 against 2 and 4.
It seems to me that adding this in would be incredibly trivial - the software is going to be modular for the number of candidates, so doubling the number of candidate states wouldn't be a problem. And the part of the Program that decrypts and the part that tallies likewise will need a very sparse modification to pull off the deceit.
I came here to say this. Unless you gave the voter their own decryption key, there's no way for anyone to verify that they aren't being deceived.
***** To be honest, I'm just very interested to know how it is possible to do math with an encrypted cypher at all. If that's possible, then I'm sure we're only a few years away from manipulating the cypher to list as Alice when decrypted and count as Bob when encrypted.
The way Xylos144 set it up seems like it'd be trivially easy to do. I mean, if the computer has to make a cypher that lists as Alice and counts as Alice, why would it be difficult to make it list as Alice and count as Bob?
The only way I see that being impossible is if there was an algorithm that made "lists as Alice" automatically leads to counting as Alice. Which may not be the case.
This solution is literally combining all of the worst parts of electronic voting and paper voting into one clusterfuck of non-verifiable, highly vulnerable to fraud, and easy to sell votes system. I totally recommend you read the paper CCCEx09 that is linked in the description, it goes over the exact E2EV process and all of the nuances of the mathematical hashing algorithm. It really isn't that complicated, yet, just like RSA, it is highly effective.
A public database with all the names and votes? Who controls this database? You just defeated the whole system...
What's the use of such a voting system when your only choice is Alice or Bob? :P Then the entire election is just a smoke screen.
How do you sell your vote after you've already voted?
You don't... You sell it beforehand, but the shady person only hands over the $20 if you show them proof that you did what was agreed...
You can't. The selfie is to show the person who bought your vote that you voted as he said, and hopefully he will pay you once you show that proof.
You don't have to tell someone that you have voted already.
They could make a deal that they pay you half the money before the vote, half when you've proved that you voted for them.
OK, but with the match stick method, you're trusting the system isn't rigged, just like without it. If you want to make sure your vote's counted it could just as easily save your key and then generate what you said you voted for, but count it differently.
It only proves the vote wasn't accidentally wrong, not intentionally.
Do I spot a mighty Nail and Gear there?
I saw some definite stick figure glasses.
confirmed. vote-a-tron-6000 is grey
Mass produced by Grey Industries.
Primo Zerajo from the same creators of the fit-a-tron6000
Re: claim at 1:06 that selfies allow vote selling, here are three ways that taking a selfie doesn't really enable vote selling:
1) You can take a picture of a blank ballot, and in something like MS Paint, you add marks that look like a pen to the oval, or to connect the arrow, or however a completed ballot looks in your jurisdiction. Then you post the altered image.
2) You can take a picture of a completed ballot, then make a stray mark on the ballot. Take your spoiled ballot back to an election judge and request a new one. Then you can fill out the new ballot however you want.
3) In jurisdictions with mail-in voting, you can fill out the ballot at home, take a picture of that ballot, then go vote in person instead of mailing in the home ballot.
can't believe this is THE guy who invented using Bob and Alice as example person names 50 years ago. Wild
Still nothing is better than a traditional paper vote.
Count it in front of people after the voting is done, is what make people sure that the counting was not RIGGED
And its easy to see if a station was rigged, and to rig an election needs lots of ballots, which is something that can be traced.
Detecting fraud is one thing. Correcting a result is another. I'm Aussie and there were so many problems with one election it was redone (WA senate at a fed election).
You can have both with this system, I don't see how it can hurt other than someone breaking the encryption
Human-counted paper voting limits the counting methods to very simple ones, which tend to lack certain fairness criteria (remember that with preferential voting, it isn't as simple as just counting who has the most votes). Using computers to count allows for more complex and fairer methods to be used, for example using a method involving finding a Smith set (taking quadratic time in the number of candidates).
Well look at Switzerland. We can vote for the whole congress, people give a list of a few dozens of people as a vote. They're all counted by hand, no problem.
That vote-a-tron is definitely CGP grey
Haiiry Cake +
anp/yswexb-b
This was fascinating! I would love to see more videos with Ron!
Since there could be social pressure for or against abstaining, I would hope that there's also an encryption scheme for all the non-votes. So the online database would include all eligible voters (whether they went to the polls or not), and those who abstained would have encrypted receipts as well, impossible to differentiate from the others.
So if all the votes are public, and you can check the results by yourself, can't you tell what each person's vote was by checking the full list, and then checking a list that doesn't contain that one person's vote?
thx, same question here
you know decryption of only one ciphertext - the one that is the overall tally
I suppose, but you already know more than you should about the tally in the example. The example used a scheme of 0 for Bob and 1 for Alice, so one result, tallying 10 people, is 0+0+0+0+1+1+1+1+1+1 = 6 votes for Alice. The problem is, internally, the machine can use any sum it wants, and it can come up with the sum using any particular fashion. The machine can tell you that you voted a certain way with one number, but then use another number in a different formula for the official count.
whiteflagstoo
that's why both the tally and the decryption of it is published together - you can calculate the tally yourself
If you remove one vote, it doesn't decrypt to an interpretable plaintext.
2 Numberphile videos a day! You surely know how to satisfy your Numberphiles Brady.
So you can verify that your vote was counted, but how do you verify it was counted correctly after the election is over and the results are published?
You can, as he said, multiply the encrypted votes to tally the total result. But you can't, and you shouldn't be able, to decipher any individual vote (to avoid selling votes and for privacy).
To me, those 'encrypted votes' are just magic numbers from a black box. I still have no way to verify that my vote for candidate A was actually counted for candidate A, and not for B
That's exactly the point, because if you could, it can serve as a proof, and thus you can sell your vote.
Yeah, and that's a pretty huge problem for a voting machine... You have to trust some obscure untransparent central authority/machine to count votes correctly, which could be easily tampered with.
I'd rather have some people selling their vote than the entire process being untransparent and easily manipulable.
Check whether or not the public record of everybodies votes decrypted match the election result that is published
about the multiplication thing: what if you multiply together all votes except for one, wouldn't you be able to then know what they voted?
The decryption code isn't something that's public. When you multiply together all the votes, you still have an encryption that needs to be decrypted. If you knew how to decrypt it in the first place, you'd just decrypt that single code.
Stericify that does not resolve the issue. voting is supposed to be completely anonymous.
It is completely anonymous as long as no one can ever use the decryption code except to check their own test-vote or when the winner is publicly determined.
The fact that you can multiply votes together except for one simply doesn't matter because if you can decrypt the final product, you can decrypt any individual vote.
What if the machines were made by George Soros? Then the DNC will have the decryption key.
The integrity of the voting process is a separate problem. Votes in paper-based systems today can typically be associated with the voter by their serial numbers, but these sheets are tightly controlled by election authorities. Though I agree, the problem of securing a single key, easily copied, that decrypts all votes is much riskier than the unique and difficult to copy counterfoils.
The verifiability of some electronic voting systems is a nice property. But I still don't think it's better than traditional paper ballots that are well understood and relatively easy to protect. Not really seeing the huge advantage to electronic voting, other than maybe cost and speed, neither of which are things that elections should be optimized for.
This would create a situation where a single person/department/group (whoever created the encryption code) would be able to find out how any person voted - there would be no trust that the voting was confidential!
So to make it confidential you just need to put the encrypted code on the Internet - not the person's name!
That leaves you with the much bigger problem of illegitimate votes. How do you verify that each listed vote came from a single registered voter?
Well, I understand that the voting process will not be done online - only the results posted - so voting is done as normal with all the ID checks that entails - so no more issues with multi votes than what is already present I guess!
The only problem I can think of is, what would stop someone from adding a bunch of fake receipts to the final tally?
You wouldn't be able to know which encryptions count as a vote for which candidate, or if they count for a candidate at all
+ZarZDodge But a rigged machine would...
Yeah, but if you sit in a room with one of these machines and vote for some candidate under a bunch of pseudonyms all day, you can turn a close election by yourself. Or just have the voting machine do the voting itself.
If fake receipts were added, there would be a discrepancy between the number of voters who came in and the number of receipts.
The voters are registered cryptographically, which means one vote per key per person, and the key cannot be forged.
I'm curious about one thing: if the multiplication of encryptions is the encryption of the addition of the plaintexts, and the decryption of that multiplication is revealed to the public, wouldn't that mean that you can decrypt the individual votes as well? Since it seems difficult to me that the multiplication of the results of one code happen to coincide with the additions of the plaintexts in another code in every possible scenario. How is that dealt with?
My understanding is that the individual votes may be decrypted (that's how their zero-knowledge proof works) but only by election officials.
But then how would election officials prove that they decrypted the ciphertext properly without revealing their private key and therefore everyone's voting choice? I guess they could generate a plaintext and an r value that would encrypt to the product of the receipts (by r value, I mean a padding value - the plaintext is padded because otherwise all "0" and all "1" votes would look alike and the ballot wouldn't be secret). But then again I don't know if that could also be constructed with the private key. I guess that it couldn't because otherwise the system would be useless.
Also, the fact that the election officials could decrypt individual votes means that the vote isn't totally secret. Then again, decrypting individual votes might be useful against someone who decides to encrypt a large number and try to submit that as their vote.
a good way to trust your vote: no computers
Sure trust corrupt officials working for someone like Lukashenko or Maduro… or cast doubt on elections like the US 2020 elections or Crimea referendum. Fun times!
Couldn't you simply tally all the votes but one by multiplying the ciphers and the one choice that's missing a vote when compared with all the votes tallied would be the one you didn't tally in the first place, thus revealing the encrypted vote value? For example, I tally everything and get 6 for Allie. Then I tally everything except for Jubal - if I get 6 for Allie again, he voted for Bob, and if I get 5 for Allie, he voted for Allie?
I dislike this system, the government can decrypt your votes.
But how does the voting machine decrypt that "test" vote? That implies that there is an algorithm for decrypting a single vote, which defeats the whole purpose.
The test vote is the real vote, until you try to verify it. Then it's invalidated for the new vote.
The point is that only some vote counting authority has the key and can verify every vote, but everyone else can't so the votes can't be sold
+Igor Noga
That implies that the counting authority can always be trusted, in which case paper ballots work fine as well.
But Igor what if the vote counting authority is the one coercing people? Happens more than you think in real life.
I see Ron Rivest at the RSA security conference every year. Cool to see him on Numberphile! I'd might actually start voting again if something like this ever gets implemented.
1:19 but you could take the picture then change it and sell your ballot to all the candidates and vote for who you like, they cant verify that was the actual ballot submitted
What key decrypts the summed ciphertext(votes)? Would like a more in-depth video on the homomorphic encryption part. When he briefly explains it sounds like you can figure out everyone's votes by simply summing pairs of votes.
Did i miss something or it's very easy to see who someone voted? You just need to do the sum over all the votes and then do it again without bob vote and i can see if bob voted 1 or 0
I think that the multiplication of the encryption only matches the sum if you do it for all the votes. It shouldn't work for subsets.
Tyler Johns, if you can't decrypt the sum everything is pointless because nobody can check if the result of the election is correct.
+Guest6265+
Then voting observers have a way to generate DECRYPTION key for list of N voters? That seems too magical for me, cuz my brain is stucked to idea that encryption and decryption key for any algorithm have to be generated at the same time.
at 3.50 it tells u that the product of 2 encryption will be the sum of the value so I guess that doesn't matter how many votes u are summing. If what u are saying is true that means that they are using an encryption specific for a certain amount of votes and that can't be true because the encryption must be chosen before the election and at that moment you don't know exactly how many people are going to vote
Guest if that is the case than all you need is one single person who didn't vote to ruin the whole election. Also, as far as I understand, that's not how the system is described
What if you take your vote out of the set, multiply them all together, and then decrypt? In this example, wouldn't the total decrease by one if the vote had been for Alice?
You have no way to decrypt, only the voting authorities have
@@Mrtnlys sorry, that can't be the entire answer. What would be the point of all of this if it's just the voting authorities who announce the results at the end? There needs to be a verification process: any user can do the encrypted tally, but can't decrypt it; only authorities can and they announce the result. Then they need to prove that their decryption is indeed correct. I believe there are protocols for this, but it's great omission from the video. Without it it makes zero sense.
@@Czeckie I was thinking the same thing. A solution I thought of would be integrating a block chain where you have an decryption key for your address on the chain and then the actual decryption key for your vote. The vote decryption key is public but the address is not. Making sure that they stay anonymous
*BOB 2016*
MAKE NUMBERPHILE GREAT AGAIN
☻/
/▌
/\
It's already great Donald Brump
In practice it is harder to ensure correct tallying of votes. For example, the encrypted token could contain 2 bits of information: who you actually voted for and who the machine wants to tally the vote for. If the voter checks the correctness (thereby voiding the ballot), the machine reports the first bit, and when the voter submits the vote the machine tallies the second bit.
Grey approved this voting machine.
Totally thought that said homoerotic.
Isn’t anybody going to mention that at 19:00, the Vote-a-tron 6000 has the image of CGP Grey?
Could you do a longer video about how the encrypted vote would be counted through multiplication of the numbers? I'm really confused
I googled it and it looks like how it works is not too far from normal encryption works. Kind of how multiplying two numbers is easy but factorizing them is hard. They way homomorphic works is kind of the same idea but uses some other math so that there is some margin of error to the equations, kind of like working with two irregular factions at the decimal level. You can also look up, "Ideal lattice" and "Ring learning with errors" which will show you the raw math and what is really used.
This is an improvement on other electronic voting methods, but there's still a lot of ways to attack it. For instance: if you voted for candidate A, the machine could tell you that you voted for candidate A even though it's internal record has you voting for candidate B.
And even though people are able to verify that the correct result is being decrypted at the end (by everyone multiplying all votes), people would still have to rely on the final decryption not being rigged.
A CGP Grey voting machine (Vote-a-tron-6000)
First thing I noticed. Very appropriate. And inside is STV. ;-)
+
If you can multiply encrypted votes together to make a tally, can't you use that ability to tell who a questioned vote is for?
How does the voter know the machine isn't just faking decryption? Ie. machine always encrypts Alice, but remembers of which receipts should be for Alice and which for Bob. When you test your receipt, the machine doesn't actually decrypt it, just checks the table and spits out the expected answer so everything looks aboveboard.
Also, fact that the receipts *can* be decrypted by the machines seems to pose a privacy threat. Whoever owns the machines can presumably decrypt any receipt. How is voter privacy maintained?
Maybe I'm missing something or the video didn't have time to delve into these, but it is not obvious to me.
Given modern recording tools selling votes is very hard to prevent, unless we start entering the voting booth nude. Since that is probably not going to fly, I would stick with plaintext receipts that are entered into regular urns for later verification by manual methods.
We can't make vote selling impossible, but we can make it unfeasibly expensive and risky. To sell a vote under our current system you would need a camera or person watching the path from the voting booth to the ballot box. Assuming you went with the less-conspicuous camera, you'd still need to verify the footage. To do this on a large enough scale to sway an election without getting caught is just not reasonable.
I think everyone in this system have the encryption key. When you see a receipt though, you can't decrypt it. That is because the plaintext is something like "voteAlice_randomchars_fd#8o^20}[l". But when you are shown the plain text you can easily verify it using your own PC or smartphone by encrypting it and checking that it matches the ciphertext.
The only trouble with this system is that it doesn't grant you provable anonymity: anyone in charge of the voting machine can potentially decrypt every vote and check who voted what.
And that's a massive no-no.
With paper ballots anonymity is granted by the assumption that the papers are identical and that once cast, they mix around in the box, making it impossible to trace back any single vote to any single voter.
While at the same time the physical arrangement of the polling station, and voter identification before you enter the booth guarantees that you can list the name of every person who voted.
These seemingly conflicting requirements make it incredibly tricky to make an electronic voting system that can be trusted to the same level as the paper ballot. (Which of course itself is far from perfect.)
Wait a minute. If I know my vote and its encryption could I not build the sum of every pair of myvote-anothervote and determine the value of the other vote from it? That would decode everyones vote once one is known. What am I getting wrong?
You can't decrypt an encrypted vote with one vote. You would need thousands of a votes and encryption pairs to get anything close to the original encryption method. There are countless ways of making one or a few votes mathematically yield their encryption pairs.
What got me confused is the statement made that every voter can always verify the sum of published votes and no dependency on the number of evaluated votes was mentioned. The election could theoretically be held with there being 2 voters. Verifying the election outcome is identical to precisely inferring the other persons vote in that case. So if what you said is true that would mean that the (perhaps approximate) total number of votes cast is somehow a parameter of the shared key generation of all votes in that election and it is generated in a way that performing partial sums of votes does NOT yet correlate significantly with the value of that partial sum. Only almost complete sums start to converge on the total sum. None of that was hinted at and your answer does not quite satisfy me, excuse me if I failed to understand. Or is the encrypted key one gets to take home not the encryption of ones own vote but some other validly cast vote so no one knows one valid pair in the first place? If so I completely missed that.
Yay!!! Nobody said "first!" :0
Speaks very highly of the numberphile audience.
That would be plain wrong. Zeroth of course.
kth!
K+1 th
nth!
that is because I am Graham's-Numbereth... idek don't listen to me :/
What about this case:
After we have all the votes and "multiply and decrypt" them and say it is 16 for Alice.
Then i remove my vote and do the same thing. Then the result can be for example 15 for Alice. That way everyone know that i have voted for Alice.
How is this case dealt with?
Vasilis Keramidas You can't remove your vote. If you're checking the system, it's not a vote at all. Imagine you were in a country with a complete democracy and they used plain paper poll booths. The counts came in and there were 2 million votes for Alice and 1 million for Bob. You "removed" your vote and they recounted. There are now 1.9 million for Alice and 1 million for Bob. No change in how voting security is implemented would stop that scenario.
Sure there is. With paper ballots, there's no way to know what is "your" ballot. In such a system, removing a ballot and recounting would not reveal how an individual voted.
BookofAeons Then you can sell your ballot.
Selling a ballot requires being able to prove who you voted for. Anonymous ballots explicitly prevent this.
They also explicitly prevent you from knowing if your vote was counted, which was what this video was about.
What happens to the audio at 5:47?
How would this system handle write-in votes? It seems to me that you'd need each candidate to have an encryption key issued in advance for it to work. Even if the system issued encryption keys to new write-in candidates on the fly, you'd have no way as a voter to know that your vote for Alice counted together with someone else's vote for Alice Smith, and another person's vote for Alice Smith/John Brown (a running-mate) etc.
instead of getting a code for who you voted for you should get a code for you name or ID. Then all the votes should be listed publicly alongside the encrypted codes of the voters.
This allows each person to verify their own vote and anyone can tally all the votes to verify the result and also this keeps each voter anonymous.
That would only work if every voter was given their own verifiable encryption key. That isn't feasible, and it would defeat the purpose anyway, because if you can verify your encryption key, then you can still easily sell your vote.
It isn't impractical at all. In fact, the mafia used to do this on the east coast of the US, and it was effective. The mistake that you're making is that you assume that the person buying votes is the candidate. That wasn't the case. It was the people that we would now call lobbyists.
I don't think you would want the machines to be able to decrypt the votes. I think a simpler method would be to show you the encrypted value you would get by each vote next to the name, if the person is dubious they can remember a distinct features of the vote they want from the others (possibly with the ability to have new encryptions generated using a different pad if they cannot find anything distinctive enough), they can then check their printed vote once it comes out. The only way this could be tampered with is if the machine can predict who you want to vote for before you do in order to swap the displayed values, but in the example given in the video, the machine could just lie about the decryption (assuming that the machine has been tampered with).
Obviously, there are other considerations: in particular about the padding that is used to avoid the same vote being encrypted with a different pad for each making them look different. I am sure a cryptographer doing this as a living can work out a reasonable way of achieving a unique pad that must be the same for all of them as its only valid for the session. Removing the ability to re-encrypt is also an option.
you've moved the problem to the verification machine, as it can hold in memory your true selection and replay it back to you despite encoding the alternative.
How do you manage a valid public decryption of the total tally without giving away how a given single vote can be decrypted?
MasterHigure read what are hashing functions
Many things are hashed, not encrypted
666Tomato666 But that's not enough. If the election officials just tell us "The total tally is decrypted to 11 votes for Ally and 5 votes for Bob", then you're back at square 1. The decryption algorithm, with all details like keys, have to be publicly available so anyone can check if there is to be any point to it at all. I am wondering how they can do that without giving away the key for every single vote.
Xeverous But this is not hashing. Hashing is, by definition, irreversible, while this is encryption, where if you know the algorithm, you can go back and forth between encoded message and plaintext. Because that is the whole point. You are SUPPOSED to be able to go back from your reciept to what you voted, if only you're given access to the algorithm. That's what the machines do if you decide to test your reciept.
MasterHigure
you can do the decryption by spreading the key among multiple people (like Shamir Secret Sharing, but with all parties needing to be present for it to work) and can do the decryption publicly
if that public ceremony includes all candidates, you get legitimate election
If you can multiply two ciphers together to add the votes together, you could check each of a set of votes by multiplying them together in various combinations.
but you know how to decrypt just a single value...
666Tomato666 Which doesn't exactly strengthen the system...
it does in that if you remove any vote (in particular, your own), you will get a different tally
666Tomato666 And that strengthens the system how?
Nillie
because you can independently verify that your, and by extension, everybody's else vote was counted?
How do you tally when there's 16 candidates?
Very timely video, good job.
Comparing a computer that can have code that handles certain scenarios is completely different from a matchbox where the match cannot change once it has left the warehouse. I don't see it being outside the realm of possibilities that a machine could 'know' that the cypher decrypts to Alice and this is what it spits out when checked, but when multiplied with other votes, comes out as a vote for Bob.
The "multiply and decrypt" method would not be possible in hiding votes.....because a system would have to be created to allow any number of votes to be made, making it a variable constraint. This means that if only one person votes, then you should be able to reliably come up with how many votes toward a candidate....which reveals that person's vote, and if you can reliably do this with each individual along with the total mass of population, then you have revealed EVERYONE's vote.
There may be a possibility to put votes within "blocks" where each block is considered separately and only if the entire block is filled will the tally work....however, with encryption techniques, this creates a flaw in the system where an individual can decipher the block because you've had to add information to determine the block itself. It's similar to having a one-time pad key, only to use it on multiple messages, defeating the purpose.
Cool, CGP Grey and the Nail and Gear of the Hello Internet podcast both appear on the voting machine. Is "Vote-A-Tron-6000" a nod to "Fit-A-Tron-5000" from Hello Internet?
but if the text can be decrypted, can't the people who had access to the software then decrypt everyone's receipt?
4:18 "...What you want to do is add them up... You multiply all those ciphertexts together and end up with a sum of all the plaintext ballots"? This needs some further explaining.
I'm sure I could research this, but I would expect the video to do more than leave the viewer hanging. Besides, multiplying those large numbers would yield an unwieldy product.
The word "Homomorphic" doesn't explain anything either. It simply means a system in which some processes can be carried out on the ciphertext (the encrypted stuff the voter sees). It looks like the answer requires some reading en.wikipedia.org/wiki/Homomorphic_encryption
I think public verifiability is more important than preventing vote buying. I think that the voting receipt hash should also hash with something like one's SSN, such that you could decrypt your individual receipt with your SSN, essentially using the voting receipt as a public key, and the SSN as a private key. That way all of the voting receipts can be published, and everyone could verify that their vote was cast the way the wanted it to be cast. Once everyone has verified their vote, all of the votes are published, but with a new hash attached to them - at this point, it becomes anonymous, except for area demographics.. So every vote is now made completely public to see, except that you can't see who made that vote. The new hash can also be verified with the SSN,, so that you can look up the anonymous hashes for your voting precinct, and find your hash to verify that it says what it should say. Then, once the anonymous vote is verified, the anonymous, publicly available votes are tallied together and the winners are announced.
But if you need the decryption key to verify the product as well, you still have no way of knowing whoever done the tallying wasn't making the results up.... So you still have to trust the system with no proof.
you don't have decryption key, but you have encryption key. After they show you plaintext you can encrypt it back and see if you get the same ciphertext.
He said the ciphertext is non deterministic, that means you get a new ciphertext every time you encrypt your vote.
Well, they give you plain-text + seed for random number generator("IV" is probably a correct term for this) that was used to encrypt that particular message.
Often, non-deterministic encryption is achieved just by prepending a few random bytes to the beginining of plain-text message before encryption. If somebody decrypts such message, he will see the IV in the first few bytes at the begining of the message.
In the video they skipped over a lot of details, so it's no wonder that everybody looks so confused in the comment section.
Ok. But wouldn't it become kinda easy to discover how other people voted then? Once you know the public key + you only have a few options of vote (say Hillary or Barrack) + you brute-force find the random bytes used to generate other people's ciphertext.
Considering everybody's ciphertexts available online after election like forever.
Just make IV long enough. Even to count from 0 to maximum 256 bit number will probably take more than lifetime of our solar system with modern supercomputers.
Now lets have a debate with the "Electronic voting is a bad idea" video from computerphile!
Just give everyone a micro chipped counter that has a number pad on it ,in the booth you place it on top of the picture of the candidate you wish to select the number pad then flashed for a few seconds allowing you to check is correct you then take it out the booth and place it in the box if votes are all held on the same day and the counters are encrypted with the same encryption algorithm it makes it easier for counting , additionally chips would be harder to spoil .Further more you could make the number pad react to a camera flash making it hard to buy someone's ballot
To check if my hashkey is actually a vote for Alice, can I multiply all hashs except mine and/or use other hashkey that I'm sure is not for Alice?
What did I miss here:
- You have access to all encrypted votes so you can do the homomorphic sum yourself and see the sum of votes
- You get your own encrypted vote
Can you then not
- take the sum of N votes and do the tally, then take that N votes plus your vote and do the tally and compare, and thus check if yours is voting for the right candidate?
- in fact, do this with every vote that you have in encrypted form and check what it voted for? I don't quite know how that encryption would work, but I imainge one for each candidate might be enough to check another encrypted vote by the difference of the sum.
How is this prevented? I mean, it should be,shouldn't it?
Interesting but could this work with rank choice voting?
Well the homeomorphic encryption part might be much more challenging, since that type of voting is not as simple as a simple tally of selections. But the other parts could work.
How do you ensure that the multiplied ciphertexts can be decrypted, but not the individual ciphertexts?
They don't need to be necessarily decryptable, if you can encrypt the sum you can verify that they are equal
Are there different keys when doing a multiply-then-decrypt vs. decrypt-then-count? Another way to ask the question is can the public read the web and tally n>=2 votes with a public key rather than the private key used by recorder?
I'd like to see an explanation of whether (and how) this sort of scheme could be applied to Condorcet voting systems.
I think you need to preface the video with the computerphile video on public keys. I see a lot of comments around the safety of public key encryption systems which are already explained in the video with R. Miles.
What is the derivative of the absolute value of X to the power of X?
Jaedon McDonald y
IS THAT EVEN CONTINUOUS??
Gabriel Pulido GREAT! Now what's the derivative of that?
:D
I love the sound effects.
Nice CGP Grey reference on the Vote-a-tron-6000
I'm a little confused about the "testing your vote" method. If we don't trust the computer or its programming, how do we trust the "check" button operates exactly the same as the "submit" button? The check button might always give you what you punched in, while submit sends in something else. There must be if-then logic to eradicate the check result and that if-then logic could be manipulated to change the submission upon "submit" but not "check".
Because the check button happens after you get your key, and the machine doesn't know whether you're about to press the check button to retroactively invalidate your vote. It would have to gamble that the one it's going to rig is the one you don't invalidate. If it fails that gamble even once, the entire process is called into question.
Excel Kobayashi The order of operations you describe makes way more sense. The way I heard it was: you don't get anything from the device until you chose whether it was a test or a submission. If it's a test, it tells you both the key and ciphertext, if it's a submission it just gives you the ciphertext. I guess I had a derp moment.
What prevents someone from doing the multiply and decrypt thing to your vote and just one other? If you know who you voted for you can easily deduce what the other person voted for, which defeats the whole purpose of this system.
What I don't get is how the final tally is done and then decrypted. Couldn't you decrypt an intermediate tally, add one vote and decrypt again to unblind that one vote? How is the final decryption only possible on the total set of votes?
does this mean that each machine, in order to be able to decrypt, has to store a private key internally, which, if hacked, can be used to decrypt people's votes? or does it generate a new private key for each vote? Or more generally, does homomorphic encryption, as described here, has to use one global private key to work?
I have a question. If you take a solved rubik's cube and do any set of moves (which can include turning or rotating the cube) and repeat it a couple of times you will get back to a solved cube. can you please explain why?
Felix Schlosser think of it in numbers. Original is 0
When it comes back to 0 it terminates
When it goes to 100 it should terminate because the pieces aren't in the original place but they have the same solution of that makes sense.
If you take the function x+25(make it right clockwise for example) it will add up to 100 after 4 times.
Now let's say you have the function(x+25) then you want to do (x-3)which is turning the top counterclockwise let's say
25,22,47,44,69,66,... eventually it will turn up a multiple of 100
No matter what you do it will always end up back to the original solution(multiple of 100)
thx
How do you know that the machine just doesn't remember which candidate people voted for, and when they have their ballot voided and decrypted to make sure that the machine is working, it just spits out what it memorized instead of what the actual ballot barcode decrypts to? The machine could still be changing entries as they come in.
Because you could still vote for another candidate just to check-and invalidate that vote in the process. Whether you wanted to check the machine by voting A, B and C in random sequence and number of times, it would be impossible for the machine to guess your next vote.
The machine could still cheat you. Let's say the following machine is rigged towards candidate B:
Say the candidate I truly wish to vote for is candidate A.
I go to the machine and decide I'd like to test it, so I vote for candidate B.
The cheating machine counts a vote for candidate B, remembers my name and that I voted for candidate B, and prints me a slip with "B" encrypted on it.
I put it in for verification, and instead of actually checking what is encrypted on it, the machine just looks at what it remembers me voting for and will print out "B." The vote is invalidated and removed from the total count.
I decide that isn't proof enough for me that the machine isn't rigged, so I cast a vote for candidate A with the intent to invalidate it later. The cheating machine counts a vote for candidate B, remembers my name and that I voted for candidate A, and prints me a slip with "B" encrypted on it.
I put it in for verification, and instead of actually checking what is encrypted on it, the machine just looks at what it remembers me voting for and will print out "A." The vote is invalidated and removed from the total count.
NOW, I decide that I trust the machines. I cast my vote for A and the above process occurs. How have I not been cheated? It has nothing to do with the machine guessing my vote.
I see; This is more of a question of morality from the electoral authority. This is also true for conventional voting systems; either the voter could claim am incorrect vote, or an observer claim to have observed misbehaviour.
I whole heartedly believe my self, that computers shouldn't be used in important voting as something could easily be altered whether it is with intent or not; they're very error-prone.
Now this is an excelent idea. Is it feasible? Think it would be great if countries that currently use e-voting would switch to something like this.
if any machine can be used to decrypt any vote, how can I protect the decryption keys from ever falling into the wrong hands?
how to i get diffrent ciphers for each person and still be able to perform homomriphic. Because if a added salt how will i remove it when adding
Thank you for such a simple explanation 😁😁
How would a system such as this handle a more complicated voting system like instant runoff or single transferable vote? Does the computer just take everyone's preferences and spit out a number?
What if the voting machine remembered that you tried to vote for Candidate A, and gave you an encrypted receipt for a vote for Candidate B.
If you try to decrypt it at that voting machine instead of submitting it, it'll lie and tell you that you voted for Candidate A because it remembers from earlier.
how can you encrypt it in such a way that you can understand decryption but not do it yourself? it seems that any long enough number could be made to show a name given enough strange rules?
Wouldn't the part about the checking the inscription be able to allow people to find out clues with enough data, like you could remember the number then get a check and then you know what one match is. if you get enough people to remember their code then you could deduce the encryption key right. At least i think that would be possible but i don't know the mechanics of encryption thoroughly enough to be confident
If everyone can create the summed ciphertext by multiplying the encrypted votes together (and decrypt it), then can't you figure out anyone's vote simply by comparing the decrypted ciphertext sum to the a sum of all the votes except for the person you want to know the vote of? It seems that if everyone can verify the sum in this manner then you can figure out anybody's vote.
The point is that you cannot decrypt anything, only the voting authorities can.You are only able to verify that the voting authorities are decrypting the correct ciphertext by multiplying yourself.
If you still have no idea what the summed ciphertext decrypts into, then what stops the authorities from saying it decrypted into whatever result they want?
The problems I see:
- if the results are published, can't we just brute-force the encryption key since we know the ciphertext and cleartext (we can multiply all numbers together to get the result and we know how the election went because that also has to be public?)
- Each voting machine contains the decryption key. (that's just inacceptable. if any1 gets hold of a machine, they can just decrypt all datasets)
- not an expert on homomorphic encryption but can you pad the cleartext in order to make each vote look distinct (encr(a) != encr(a)) (because I don't think you can)
- I don't know how well this works for more than two candidates...
and generally I am not a huge fan of publishing any reversable, connectable (to a person) data online. whatsoever. no matter how "unbreakable" the cipher is. because I believe that everything can be broken given enough time.
i have a question,how can someone buy your vote with the selfie pic?
Question 1: How can I tell that nobody added a nonvalide vote?
Question 2: If the encrypted voting of all people is public, who will stop me from decrypting in 20 years with bruteforce and strong computers, that we can not even imagine yet?
For your first question, the same way we do now. We check the list of people who voted against the list of people who are allowed to vote.
Your second question is a real concern, but that problem lies at the heart of all cryptography. All we can do is make the encryption strong enough that by the time it's decrypted, the data will be worthless. A bigger danger than brute force is how do you keep the keys secure for that long. The videos proposed system has thousands of people holding the decryption keys; we'd need to trust all of them.
With the homomorphic encryption approach: if all encrypted votes are public, and it's possible to multiply encrypted values together and get the sum of the plaintext, can't I use *my* encrypted vote and anybody else's vote to determine how any other individual voted? If I know I voted for Alice so that's a 1 then multiplying with one other encrypted vote gives me a 1 or a 2, I know that the other voter voted for Bob or Alice, don't I?
Numberphile and E2E verifiable voting? I'm in heaven!
well... if I can count them myself... then I can also count just one... and know if it's a 1 or 0 ... or not?
The only problem I see is the decryption of the tally. Sure, you can check that all the encryptions add up correctly, but Since you don't have the algorythm for the decryption in the end you have to trust that the sum of all encryptions decrypts to what officials say.
Eastereggs in the VOTE-A-TRON-6000. Love it
How would this work with races that have more than 2 candidates?
Can we please talk about the Condorcet criterion? I think showing the mathematics of voting and alternative voting methods would be a great subject for Numberphile. I know CGP Grey has some great videos on voting systems, but he doesn't go into the math in the way that Numberphile might.
Couldn't you count all the encryptions to see the total votes for Alice, then do it again with all but one and see what he voted for? if you get the same number he voted for Bob, if It's one less votes for Alice he voted for Alice