Was YOUR vote counted? (feat. homomorphic encryption) - Numberphile

How to be sure your vote was counted ---- "End to End Verifiable Voting" with cryptopgraphy expert Professor Ron Rivest.
More links & stuff in full description below ↓↓↓
See our other election video with Professor Rivest: • How to Check Election ...
Problems with e-Voting via Computerphile: • Why Electronic Voting ...
RSA Encryption: • Encryption and HUGE nu...
Some suggested reading from Professor Rivest:
arxiv.org/abs/...
people.csail.mi...
people.csail.mi...
www.usenix.org...
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/...
Other merchandise: store.dftba.co...

[@jackblade8796]

The QR code next to "You voted for: Alice" links to Tom Scott's e-voting video

[@alexd3693]

I will video record myself voting for the same party every year and in primaries.

[@Postcinct]

Is that a little CGP Grey face on the VOTE-A-TRON?

[@TitanOfClash]

Upfade Must be an alternative vote-a-tron

[@HiThere-qu2tf]

Henry Tompkinson HAHAHAHAHAHAH😂😂😂

[@alejandronq645]

Yeah, it is

[@netravatpendsey]

Upfade isn't the symbol above it almost the symbol of his podcast

[@Timon-IrishFolk]

Do I spot a mighty Nail and Gear there?

[@lewiskaminski2836]

I saw some definite stick figure glasses.

[@djngdhn]

confirmed. vote-a-tron-6000 is grey

[@y__h]

Mass produced by Grey Industries.

[@wdarkfenix]

Primo Zerajo from the same creators of the fit-a-tron6000

[@ahensley]

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).

[@Walter-mr5hd]

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.

[@SkySpiral7_Lets_play]

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)

[@entropie-3622]

@@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.

[@16m49x3]

That vote-a-tron is definitely CGP grey

[@allisonmundy2581]

Haiiry Cake +

[@andlux]

anp/yswexb-b

[@igNights77]

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?

[@yinge101]

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.

[@collinwhittaker9122]

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?

[@BrandonMarshall32]

How would you know that the machine didn't change the key or algorithm when it is being tested? Like with the Volkswagen emissions

[@SkySpiral7_Lets_play]

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.

[@TonySmith-jj9fv]

You have to add a verification mechanism.

[@joshmc5882]

@@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.

[@SkySpiral7_Lets_play]

@@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.

[@syphonuk]

Totally thought that said homoerotic.

[@Xylos144]

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.

[@david21686]

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.

[@david21686]

***** 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.

[@treyshaffer]

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.

[@jorgenitales4128]

A public database with all the names and votes? Who controls this database? You just defeated the whole system...

[@bonbonpony]

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.

[@NielsHeldens]

*BOB 2016* MAKE NUMBERPHILE GREAT AGAIN

[@Muskottih]

☻/ /▌ /\

[@911gpd]

It's already great Donald Brump

[@Harlequin314159]

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?

[@deadlygenga]

Harlequin314159 or multiplying everyone but one person and seeing how that changes the tally

[@raosprid]

You seem to be forgetting that people run the government

[@Frank01985]

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.

[@EpsilonRosePersonal]

If that were the case, you wouldn't be able to verify the final tally, so the creators could easily lie.

[@Frank01985]

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...

[@slikrx]

A CGP Grey voting machine (Vote-a-tron-6000)

[@Drosophilax]

First thing I noticed. Very appropriate. And inside is STV. ;-)

[@jakepeterson8552]

+

[@Pikopati]

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

[@hart-of-gold]

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.

[@hart-of-gold]

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).

[@zubirhusein]

You can have both with this system, I don't see how it can hurt other than someone breaking the encryption

[@jlap94]

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).

[@MrNacknime]

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.

[@Double-Negative]

Grey approved this voting machine.

[@douggwyn9656]

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.

[@kranser]

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!

[@kranser]

So to make it confidential you just need to put the encrypted code on the Internet - not the person's name!

[@BookofAeons]

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?

[@kranser]

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!

[@Chew1964]

How do you sell your vote after you've already voted?

[@numberphile]

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...

[@Squablicious]

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.

[@Sopel997]

You don't have to tell someone that you have voted already.

[@JakesGuitarThing]

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.

[@mikethegreat4296]

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.

[@Hamstray]

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?

[@Stericify]

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.

[@Hamstray]

Stericify that does not resolve the issue. voting is supposed to be completely anonymous.

[@Stericify]

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.

[@supermaster2012]

What if the machines were made by George Soros? Then the DNC will have the decryption key.

[@KeenanTims]

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.

[@ceruchi2084]

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.

[@levi12howell]

Could you do a longer video about how the encrypted vote would be counted through multiplication of the numbers? I'm really confused

[@pleasedontwatchthese9593]

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.

[@4.0.4]

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?

[@EmilioAlmansi]

thx, same question here

[@666Tomato666]

you know decryption of only one ciphertext - the one that is the overall tally

[@whiteflagstoo]

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.

[@666Tomato666]

whiteflagstoo that's why both the tally and the decryption of it is published together - you can calculate the tally yourself

[@BucketCapacity]

If you remove one vote, it doesn't decrypt to an interpretable plaintext.

[@jakeroosenbloom]

2 Numberphile videos a day! You surely know how to satisfy your Numberphiles Brady.

[@jfb-]

The only problem I can think of is, what would stop someone from adding a bunch of fake receipts to the final tally?

[@bolerie]

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

[@Frank01985]

+ZarZDodge But a rigged machine would...

[@matthewhartley3147]

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.

[@danielwesser9881]

If fake receipts were added, there would be a discrepancy between the number of voters who came in and the number of receipts.

[@jorgenitales4128]

The voters are registered cryptographically, which means one vote per key per person, and the key cannot be forged.

[@brboLikus]

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?

[@joshmc5882]

I dislike this system, the government can decrypt your votes.

[@olehermanse]

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.

[@ShilleR2044]

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

[@Kaepsele337]

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.

[@ShilleR2044]

Tyler Johns, if you can't decrypt the sum everything is pointless because nobody can check if the result of the election is correct.

[@niter43]

+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.

[@ShilleR2044]

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

[@efeyzee]

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

[@Robertlavigne1]

This was fascinating! I would love to see more videos with Ron!

[@GamesFromSpace]

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.

[@aliasmask]

The test vote is the real vote, until you try to verify it. Then it's invalidated for the new vote.

[@igornoga5362]

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

[@chsxtian]

+Igor Noga That implies that the counting authority can always be trusted, in which case paper ballots work fine as well.

[@efeyzee]

But Igor what if the vote counting authority is the one coercing people? Happens more than you think in real life.

[@PINGPONGROCKSBRAH]

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.

[@Mrtnlys]

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.

[@JesseBusman1996]

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?

[@Dsiefus]

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).

[@JesseBusman1996]

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

[@Dsiefus]

That's exactly the point, because if you could, it can serve as a proof, and thus you can sell your vote.

[@JesseBusman1996]

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.

[@bolerie]

Check whether or not the public record of everybodies votes decrypted match the election result that is published

[@jayyyzeee6409]

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.

[@psiphiorg]

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.

[@JohnnyYenn]

Yay!!! Nobody said "first!" :0 Speaks very highly of the numberphile audience.

[@y__h]

That would be plain wrong. Zeroth of course.

[@zaephou2843]

kth!

[@HuleAbhishek]

K+1 th

[@brokenwave6125]

nth!

[@TSPxEclipse]

that is because I am Graham's-Numbereth... idek don't listen to me :/

[@vonkruel]

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?

[@marshalice]

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?

[@chx1618]

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.

[@loganfields562]

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.

[@Verrisin]

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?

[@jakobburgos6990]

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]

You have no way to decrypt, only the voting authorities have

[@Czeckie]

@@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.

[@whoisamp620]

@@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

[@keramidasceid]

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?

[@NickInts]

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.

[@BookofAeons]

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.

[@NickInts]

BookofAeons Then you can sell your ballot.

[@BookofAeons]

Selling a ballot requires being able to prove who you voted for. Anonymous ballots explicitly prevent this.

[@RFC3514]

They also explicitly prevent you from knowing if your vote was counted, which was what this video was about.

[@JoJoModding]

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?

[@willtor]

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.

[@velikiradojica]

How do you tally when there's 16 candidates?

[@earthbjornnahkaimurrao9542]

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.

[@cscott024]

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.

[@cscott024]

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.

[@nsiivola]

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.

[@BookofAeons]

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.

[@ddimin]

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.

[@anderslauridsen601]

Eastereggs in the VOTE-A-TRON-6000. Love it

[@brownbearkidd]

Nice CGP Grey reference on the Vote-a-tron-6000

[@000pett]

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

[@fablungo]

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.

[@thenewkanata]

Love the Hello Internet logo on the ballot machine

[@curtism.2353]

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?

[@jaketeen1987]

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.

[@brodaclop]

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.)

[@SimpleLivingHigherThinking]

Thank you for such a simple explanation 😁😁

[@sillyfly9530]

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.

[@ddimin]

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.

[@122mlb]

He said the ciphertext is non deterministic, that means you get a new ciphertext every time you encrypt your vote.

[@ddimin]

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.

[@122mlb]

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.

[@ddimin]

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.

[@QweRinatrtY]

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

[@PlasmaHH]

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?

[@Robbedem]

I think the current hybrid system of a computer that prints a piece of paper that you have to put in a box is better. - The voter can very easily verify if his vote is registered correctly because it's written on the piece of paper - It's anonymous because no name is registered by the computer, nor on the paper - Votes can't be sold because you have to deposit the piece of paper The only downside is that there need to be random checks to see if the computer votes match the paper votes.

[@Rheologist]

I like the nail and gear on the ballot machine!!

[@MysteryHendrik]

Joshua Anderson The flag election was rigged.

[@danhorus]

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.

[@markhagerman3072]

I'd like to see an explanation of whether (and how) this sort of scheme could be applied to Condorcet voting systems.

[@deepsheep9102]

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.

[@athanasiuscontramundum4127]

The timing of this video is fitting.

[@franzscheerer]

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.

[@TonySmith-jj9fv]

This is fantastic. I've recently become interested in secure Governance.

[@singami465]

#AliceForPrison2016

[@y__h]

Alice's real identity is Mallory.

[@snubbelbuff1471]

+

[@tedchirvasiu]

#Bob2016

[@barnowl2832]

Make Alice Mallory again

[@getmilked6216]

we have a bit more to tackle before we do wonderful things like this

[@yinge101]

Numberphile and E2E verifiable voting? I'm in heaven!

[@error.418]

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.

[@1ucasvb]

I love the sound effects.

[@andykillsu]

I like how the QR Code takes you to the numberphile website!

[@PaulPaulPaulson]

TheWioreks Except one

[@andykillsu]

Paul Paulson Really they all looked the same to me?

[@SithBowman]

The one at 1:20 lead to the computerphile video about voting

[@CarterColeisInfamous]

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

[@OriginalDeathpill]

Oh snap, that's Ron Rivest!

[@actmgr9786]

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.

[@Tadokat]

Anyone else notice that Grey is the vote-o-tron?

[@Alex-Lay]

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?

[@ShilleR2044]

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

[@numberphile]

See the second video with Ron Rivest about how to check an election result: kzbin.info/www/bejne/kH6QmmuqadWAgZI

[@eduardofreire8609]

loved the video!

[@WouterWeggelaar]

Nice QR code!

[@WouterWeggelaar]

And for anyone checking, they are all the same as well as far as I could tell, except the first one!

[@Silvanx]

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.

[@WouterWeggelaar]

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.

[@ragnkja]

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 you know how to decrypt just a single value...

[@ragnkja]

666Tomato666 Which doesn't exactly strengthen the system...

[@666Tomato666]

it does in that if you remove any vote (in particular, your own), you will get a different tally

[@ragnkja]

666Tomato666 And that strengthens the system how?

[@666Tomato666]

Nillie because you can independently verify that your, and by extension, everybody's else vote was counted?

[@tritonmole]

But i don`t want to vote for Alice nor for Bob! I want to vote for Ed.

[@GraafBerengeur]

Ed is nice and all, but I really want Jamal to just proclaim himself the Emperor of Numberphile.

[@TheRedstoneTaco]

#JAMESGRIMESFORPRESIDENT

[@Tfin]

Vote for Rocky Roque. Or whatever his name is. My vote? Counted, sure. But my body counts as a vote for the other person.

[@MasterHigure]

How do you manage a valid public decryption of the total tally without giving away how a given single vote can be decrypted?

[@Xeverous]

MasterHigure read what are hashing functions Many things are hashed, not encrypted

[@MasterHigure]

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.

[@MasterHigure]

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.

[@666Tomato666]

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

[@ErikratKhandnalie]

I think public verifiability is more important than preventing vote buying. I think that the voting receipt hash should also hash with something like one's SSN, such that you could decrypt your individual receipt with your SSN, essentially using the voting receipt as a public key, and the SSN as a private key. That way all of the voting receipts can be published, and everyone could verify that their vote was cast the way the wanted it to be cast. Once everyone has verified their vote, all of the votes are published, but with a new hash attached to them - at this point, it becomes anonymous, except for area demographics.. So every vote is now made completely public to see, except that you can't see who made that vote. The new hash can also be verified with the SSN,, so that you can look up the anonymous hashes for your voting precinct, and find your hash to verify that it says what it should say. Then, once the anonymous vote is verified, the anonymous, publicly available votes are tallied together and the winners are announced.

[@RouletteRog]

Very cool :-) We've done some work with an FHE implementation in my work (cloud security, cybersecurity). This is a fun intro to what quickly gets to be a nasty subject.

[@Sathrandur]

Great idea but I don't think it would gain much support as I suspect many people would find it too complex.

[@DustinRodriguez1_0]

I especially like that this system has no need for a unique ID being issued to voters which they then have to keep secret. Of course, we would have to start a new country for such a system to be adopted. We've known that First Past the Post voting is fundamentally flawed for ages, but we can't change it because those who benefit the most from it are the ones who would have to be responsible for dismantling it.

[@UnPuntoCircular]

I see Nail and Gear

[@MysteryHendrik]

UnPuntoCircular The flag election was rigged.

[@maxuix2]

Now lets have a debate with the "Electronic voting is a bad idea" video from computerphile!

[@f1f1s]

Isn’t anybody going to mention that at 19:00, the Vote-a-tron 6000 has the image of CGP Grey?

[@jayyyzeee6409]

I see some comments on here questioning the validity of the approach. I don't want to insult people, but if a guy like Ron Rivest and others in the encryption community says something is secure, then it's secure. Having said that, the meaning of "secure" usually is shorthand for "reasonably secure". Encryption can often be theoretically broken with hardware from the future. For example, it might be possible to find out who Alice voted for 40 years from now. Is that important? Well, certainly not as important as ensuring an trustworthy vote in the present.

[@chaimss]

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.

[@BillRoberts5]

The problem is that the user interface can be programed to display any kind of behavior you want.

[@a.a7907]

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?

[@Thorinbur]

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.

[@fatimarosario1649]

desde la Rep. Dominicana. increible, att. bohane rosario

[@ZbyszekMichalak]

Very timely video, good job.

[@FeinryelRavenclaw]

What is the derivative of the absolute value of X to the power of X?

[@salvefrater2582]

Jaedon McDonald y

[@invaderpopz]

IS THAT EVEN CONTINUOUS??

[@FeinryelRavenclaw]

Gabriel Pulido GREAT! Now what's the derivative of that?

[@FeinryelRavenclaw]

:D

[@ulmeydasmile]

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?

[@Utharas]

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.

[@ulmeydasmile]

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.

[@sabriath]

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.

[@theatheistpaladin]

Interesting but could this work with rank choice voting?

[@Arkalius80]

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.

[@bbonvallet]

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".

[@thealliedhacker]

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.

[@bbonvallet]

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.

[@mitchelllevy1207]

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.

[@christianaustin782]

Dude, he got Ron Rivest on here lol, that's like a celebrity man lol