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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
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!
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!
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.
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
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.
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.
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 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.
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
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?
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.
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.
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.
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.
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.
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?
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 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.
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.
G point on elliptic curve x=0,1 vote for one of two candidates r true randon number at least 200 bits output = (x + r)*G X sum of x (result of election), R sum of r X*G is calculated as (X+R)*G - R*G X is found comparing X*G with G, 2G, 3G, ... N*G, N number of votes Server publishes R, and R*G (only possible if R is calculated correct) From R'*G the value of R' cannot be calculated, so the server cannot publish a wrong value of (R'*G) and R' corresponding to a false value of X.
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 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.
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
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.)
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.
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.
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.
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 have got a question for you guys. Why (1*1)+(1*4)=5 and (1*2) +(1*3) =5. If you keep going you will get the same answer for other numbers. Let's take (1*4) + (1*7) = 11 and (1*5)+(1*6)= 11. It works for all numbers. Could you please explain what does it work this way?
You still cant trust the computer.. Lets say I vote for A, the PC makes it into B and when I double-check my ballot the PC tells me it's A because the computer remebered that it manipulated my ballot?
That was the first part: You can perform the same combining operation on all of the votes that the officials use. If it doesn't come out the same, you know there were shenanigans.
I'm confused as to how a confirmation receipt of a vote allows for the kind of voter fraud that you suggest it does. How would selling one's vote confirmation(or selfie of them voting) be equal to selling their vote beforehand? Arrangements would have to be made prior to voting, where the receipt or selfie is offered as proof. This kind of voter fraud would easily be traced, and the subsequent vote nullified.
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
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.
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.
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?
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?
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.
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.
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.
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.
Can't the vote buyer verify your vote using a similar matchbook method? If I want you to vote for Bob I'll watch you verify your vote and see if it's Bob. After you revote, I can have you verify again, etc. To change your vote to Alice without me knowing you'd need to guess how many times I'd ask for verification.
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?
Interesting idea, but that system would be giving out a massive list of plaintexts and ciphertexts to potentially everyone. How do you prevent the encryption key being worked out by fraudsters?
I think that with the current methods of encryption the encrypted data doesn't help u, so doesn't matter how many plaintexts u have, it will still be as hard as having few kb of data. but i'm not totally sure about this
Can you please make a second RSA video? Dr. Grimes begins the explanation, but doesn't really explain the whole equation, or explain why the 3 was chosen.
What's to stop someone from multiplying all the coded votes and getting an "Alice 6" result, then omitting Brady's vote and multiplying them all again? Then they get an "Alice 5" result and know what his votes is.
How do you publicly verify the decryption without giving away the key so that anyone can decrypt any of the other votes? If you use a separate key for the final summation decryption, how can you know that key decrypts the message properly and isn't just designed to make one candidate win? :/ Wouldn't it be better to use the same method as when you verify that the machine actually encrypts your message correctly to make sure the final counting decryption is accurate? By which I mean that once everyone has cast their vote a key to decrypt votes in the same homomorphic way is released to the public and now everyone can separately ask the entity tasked with decrypting/counting all the votes to decrypt all the real votes + a bunch of "fake" votes you've also asked it to decrypt and it will give you back the sum of those votes (both the real and fake ones). Since you know what the fake votes were you can just take the sum - your fake votes and you get the real votes. If you simply send in two different sets of fake votes you can GUARANTEE that you have the real sum for the the real notes since the entity counting the votes cannot know what the sum of your fake notes is so if it tries to tamper with the result it can only do so by tampering with the sum of the real votes which will show up when you compare what the real sum is between the two different counts. This assumes you can make sure there's no way for the entity to work out what the fake votes are by using the public key. This would directly allow for online voting :) The system is end to end secure, and if someone tries to coheres/bribe you into voting one way by standing next to you and watch you cast your vote, you can just change it once that person is no longer watching you ensuring privacy when voting. Sure, you could in theory kidnap a lot of people and force them to vote and then take away their electronics and keep them locked up until the voting is over, but doing that on a large enough scale to impact the election without it's being very obvious that hundredths of thousands of people have been kidnapped seams very very unlikely and requires complete corruption in the police to not intervene. Basically in order to tamper with peoples vote you would have to deprive them of their freedom which is much harder to do unnoticed than just giving them some money. If you're thinking "You could just deprive people of their freedom/bribe them at the very last hour or so before the election closes" this can easily be solved by keeping the day when the election closes a secret. So you say "This week will be election week, and some day during the week after that the election will close". This would require the "bad guys" to keep people captive for up to a week which is notable by friends and family and they will report the person as missing.
Doesn't this matchstick method thing require you to trust the voting-machine software not to say "This would be an Alice vote" but secretly have the ciphertext mean a Bob vote?
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.
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...
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 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.
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
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?
That vote-a-tron is definitely CGP grey
Haiiry Cake +
anp/yswexb-b
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.
can't believe this is THE guy who invented using Bob and Alice as example person names 50 years ago. Wild
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...
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.
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.
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.
A CGP Grey voting machine (Vote-a-tron-6000)
First thing I noticed. Very appropriate. And inside is STV. ;-)
+
*BOB 2016*
MAKE NUMBERPHILE GREAT AGAIN
☻/
/▌
/\
It's already great Donald Brump
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.
Totally thought that said homoerotic.
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.
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.
See the second video with Ron Rivest about how to check an election result: ua-cam.com/video/ZM-i8t4pMK0/v-deo.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.
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.
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.
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.
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.
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.
2 Numberphile videos a day! You surely know how to satisfy your Numberphiles Brady.
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.
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.
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?
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.
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!
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!
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
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
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.
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.
This was fascinating! I would love to see more videos with Ron!
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
Grey approved this voting machine.
Isn’t anybody going to mention that at 19:00, the Vote-a-tron 6000 has the image of CGP Grey?
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 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
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?
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.
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.
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 :/
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.
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.
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.
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?
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 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.
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.
G point on elliptic curve
x=0,1 vote for one of two candidates
r true randon number at least 200 bits
output = (x + r)*G
X sum of x (result of election), R sum of r
X*G is calculated as (X+R)*G - R*G
X is found comparing X*G with G, 2G, 3G, ... N*G, N number of votes
Server publishes R, and R*G (only possible if R is calculated correct)
From R'*G the value of R' cannot be calculated, so the server
cannot publish a wrong value of (R'*G) and R' corresponding
to a false value of X.
How do you tally when there's 16 candidates?
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
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?
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 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
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.)
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 happens to the audio at 5:47?
but if the text can be decrypted, can't the people who had access to the software then decrypt everyone's receipt?
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.
The problem is that the user interface can be programed to display any kind of behavior you want.
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.
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 have got a question for you guys. Why (1*1)+(1*4)=5 and (1*2) +(1*3) =5. If you keep going you will get the same answer for other numbers. Let's take (1*4) + (1*7) = 11 and (1*5)+(1*6)= 11. It works for all numbers. Could you please explain what does it work this way?
You still cant trust the computer.. Lets say I vote for A, the PC makes it into B and when I double-check my ballot the PC tells me it's A because the computer remebered that it manipulated my ballot?
That was the first part: You can perform the same combining operation on all of the votes that the officials use. If it doesn't come out the same, you know there were shenanigans.
I'm confused as to how a confirmation receipt of a vote allows for the kind of voter fraud that you suggest it does. How would selling one's vote confirmation(or selfie of them voting) be equal to selling their vote beforehand? Arrangements would have to be made prior to voting, where the receipt or selfie is offered as proof. This kind of voter fraud would easily be traced, and the subsequent vote nullified.
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.
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
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.
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.
Anyone else notice that Grey is the vote-o-tron?
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
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?
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?
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.
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.
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.
I'd like to see an explanation of whether (and how) this sort of scheme could be applied to Condorcet voting systems.
x² = (x-n)(x+n)+n²
just thought i'd let this formula down to help you calculate square numbers
ex. 49² = 50x48+1 = 2401
ex. 55² = 50x60+25 = 3025
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.
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.
Now lets have a debate with the "Electronic voting is a bad idea" video from computerphile!
Can't the vote buyer verify your vote using a similar matchbook method? If I want you to vote for Bob I'll watch you verify your vote and see if it's Bob. After you revote, I can have you verify again, etc. To change your vote to Alice without me knowing you'd need to guess how many times I'd ask for verification.
Great idea but I don't think it would gain much support as I suspect many people would find it too complex.
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?
Interesting idea, but that system would be giving out a massive list of plaintexts and ciphertexts to potentially everyone. How do you prevent the encryption key being worked out by fraudsters?
I think that with the current methods of encryption the encrypted data doesn't help u, so doesn't matter how many plaintexts u have, it will still be as hard as having few kb of data. but i'm not totally sure about this
Can you please make a second RSA video? Dr. Grimes begins the explanation, but doesn't really explain the whole equation, or explain why the 3 was chosen.
Does this account for a possibly compromised vote-a-tron? Couldn't a machine add votes to a candidate without anyone actually voting?
Any updates? The second explanation of the process seems to be incomplete feels like half the problem's solved!
What's to stop someone from multiplying all the coded votes and getting an "Alice 6" result, then omitting Brady's vote and multiplying them all again? Then they get an "Alice 5" result and know what his votes is.
How do you publicly verify the decryption without giving away the key so that anyone can decrypt any of the other votes?
If you use a separate key for the final summation decryption, how can you know that key decrypts the message properly and isn't just designed to make one candidate win? :/
Wouldn't it be better to use the same method as when you verify that the machine actually encrypts your message correctly to make sure the final counting decryption is accurate? By which I mean that once everyone has cast their vote a key to decrypt votes in the same homomorphic way is released to the public and now everyone can separately ask the entity tasked with decrypting/counting all the votes to decrypt all the real votes + a bunch of "fake" votes you've also asked it to decrypt and it will give you back the sum of those votes (both the real and fake ones). Since you know what the fake votes were you can just take the sum - your fake votes and you get the real votes. If you simply send in two different sets of fake votes you can GUARANTEE that you have the real sum for the the real notes since the entity counting the votes cannot know what the sum of your fake notes is so if it tries to tamper with the result it can only do so by tampering with the sum of the real votes which will show up when you compare what the real sum is between the two different counts. This assumes you can make sure there's no way for the entity to work out what the fake votes are by using the public key.
This would directly allow for online voting :) The system is end to end secure, and if someone tries to coheres/bribe you into voting one way by standing next to you and watch you cast your vote, you can just change it once that person is no longer watching you ensuring privacy when voting. Sure, you could in theory kidnap a lot of people and force them to vote and then take away their electronics and keep them locked up until the voting is over, but doing that on a large enough scale to impact the election without it's being very obvious that hundredths of thousands of people have been kidnapped seams very very unlikely and requires complete corruption in the police to not intervene. Basically in order to tamper with peoples vote you would have to deprive them of their freedom which is much harder to do unnoticed than just giving them some money. If you're thinking "You could just deprive people of their freedom/bribe them at the very last hour or so before the election closes" this can easily be solved by keeping the day when the election closes a secret. So you say "This week will be election week, and some day during the week after that the election will close". This would require the "bad guys" to keep people captive for up to a week which is notable by friends and family and they will report the person as missing.
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?
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 many such encryption trials should be done to reach a confidence of 1 - 1/10000 that the machine is not lying to you ?
Doesn't this matchstick method thing require you to trust the voting-machine software not to say "This would be an Alice vote" but secretly have the ciphertext mean a Bob vote?
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.