Electronic Voting System Proposal: What are the flaws?

Question

I just thought of an electronic voting system and wanted to write it down. After writing 1 line in a text editor, I thought I should share it here and ask you about the flaws in it. Let's see if you can find some.

The goals of this system are:

• to make it harder to rig elections.
• to make the flow of the casted votes less obfuscated.
• to give every voter a way of verifying that their vote has been counted.

It's not about finding a perfect method of voting. It's about finding one which is better than the ones currently being used.

The process

1. All voters have registered a public key at the state's authorities. Those keys are already being used for legally binding communication and they are used for every election so people only have to do this once.
2. All parties create a key pair and register and publish the public key.
3. The election authority (I named it to be able to refer to it later) creates 1 256 bit nonce per voter, adds 256 0 bits before it, as well as 256 bit more random data and encrypts those 768 bit with the respective voter's public key. The nonces are put into a random order and saved.
4. The election authority publishes a hash of all the saved nonces.
5. The election authority publishes a list of all encrypted 0 bits + nonces per constituency.
6. Every voter downloads the list of their constituency.
7. The software the voters are running finds the nonce of the user by splitting the file into 768 bit segments, decrypting them with the user's private key, and recognizing a nonce as the user's when it finds the first 256 bit of the plain text to be all zeros.
8. The user enters their vote into the software.
9. The software encrypts the nonce along some new 256 bit nonce with the public key of the party the user voted for and does the same with made-up nonces for all other parties.
10. The software sends all the encrypted messages to the servers of the respective parties in random order.
11. The parties' servers decrypt the messages and store it in plain text.
12. After everyone voted, the parties calculate a hash of all the massages the received and publish it.
13. The election authority publishes the nonce files mentioned in point 3.
14. The parties publish their nonce files.
15. All correct nonces only 1 party has in their file are counted, the others aren't. List of all nonces which have been counted for a given party are published.
16. Because of some stupid post-past the pole per constituency "democracy", the same party as last time wins unless the way the winners are chosen is better until then.

Possible problems and why I think they aren't problems

A party can force people to give them their nonces and punish them if they gave them incorrect ones after the correct ones are published in step 13 or if the people gave them their actual ones but also voted for a different party.

This would be obvious election fraud and a single case of this being made public would harm a party seriously so the profit-to-risk ration should be undesirable for all parties.

Someone opposing a party can flood their servers with fake messages.

A party has an interest in gathering votes. It can use anti-spam techniques to a reasonable extend and for example don't accept extraordinary amounts of messages from a single IP address. To verify the sender actually controls that IP address and doesn't just make source IP addresses up, using TCP is enough.

DDoS

People can make a sit-down strike in front of a polling location.

Why I think this method of electronic voting is superior to voting on paper

I don't have enough fingers and toes to count how many times I heard that voting on paper is so great because everyone can just become an election observer and check whether everything goes the correct way at their local polling station. That's of course stupid argumentation because all one can do as an individual is to make sure that about 1000 of about 100'000'000 votes (orders of magnitudes) aren't rigged. Those 0.001% must be really awesome so that they're being talked about so much. And that's only of one stands by the ballot box all the time, giving no one a chance to take some ballots out of it or to dump a lot of them into it as many of you have probably seen in that recent video of a Russian election. You don't have these problems with the process described above because everything is public.

Furthermore, this is always assuming perfect conditions, for example people going to polling locations, not voting per absentee ballot, and things like identification often aren't even discussed.

Proving that one has voted for a specific party is possible with ballots, too, since we live in a time in which there are tiny cameras and people can just film the process of casting their vote and then send the video to whomever payed or threatened them. I see people spying on what other people voted for without their consent as a much bigger difference between the system described above and using ballots.

It's often discussed that there can be malware on people's computer. But there can also be surveillance in polling locations. There are plenty of countries in which people vote with pen and paper and if you're taking the issue seriously, you probably are familiar with the reason England uses pencil and paper. The big difference is: One as an individual has control over one's computer but doesn't have control over the paper and the pen/pencil used. The pen one is given my have ink which vanishes after a few minutes, the ballot may be made in a way so that after some time a cross one hasn't made appears, making the vote invalid in either case.

Election assistants are just assumed to be able to count the votes correctly (and to not manipulate them) even though they historically have been wrong a lot with recounts yielding different results.

Election results often are transported over an insecure channel. The have seriously been sent via unencrypted email and been given through via telephone.

And it goes on. One has absolutely no guarantee that one's vote has been counted when voting on paper. Not if one chooses absentee voting, not if one goes to a polling location. One's ballot can always just go missing and be replaced by a different one. With the process described above, everyone can check whether their vote actually has counted towards the party they voted for.

My question

Are there any actual problems making this method less desirable than voting on paper?

Note that point 1 is a prerequisite so simply saying that there are people who don't use public-key cryptography is not valid argumentation. Furthermore, let's assume time has progressed far enough for people to be familiar with computers or there to be a rule in place for old people to no longer be eligible to vote (I've heard proposals on this several times but this is not the right place to discuss political opinions on it).

Answer 1

I haven't analyzed your protocol but there are glaring flaws in your methodology which make it unlikely that you achieved a decent voting protocol.

Your post has a detailed description of the protocol, but it's missing an assessment of the requirements. Without precise requirements, you might solve some problem, but it's unlikely to be the problem you set out to solve. Voting involves many threats, and an analysis of the requirements would take several pages.

In addition, what little requirement analysis you performed is not very good: your critique of paper voting has some critical flaws.

That's of course stupid argumentation because all one can do as an individual is to make sure that about 1000 of about 100'000'000 votes (orders of magnitudes) aren't rigged.

No, your argument is the stupid one. Voting doesn't rely on a single individual being able to assess the sincerity of every vote. You can't achieve that with any voting method because you can't check that every voter was correctly identified and cast their vote without coercion. That is not a requirement.

An important property of paper voting systems is that fraud requires massive collusion, and the bigger the fraud, the more massive the required collusion. Ballot boxes are attended by representatives of at least two opposing factions: the watchers watch each other. Anybody can declare themselves an interested party, which makes it hard for potential fraudsters to prevent others from observing any tampering.

Proving that one has voted for a specific party is possible with ballots, too

Yes, and that is a big problem with any electronic voting: it's a lot more difficult to enforce the absence of snooping. Even with the miniaturization of cameras, it's still easier to hide a recording device inside an electronic device.

Election assistants are just assumed to be able to count the votes correctly (and to not manipulate them) even though they historically have been wrong a lot with recounts yielding different results.

Paper ballots have some nice properties in this respect. Tampering is more evident: you need to smuggle these masses of papers, not just run a command on a computer. Counting errors will only make a small difference, at most on the ballots being counted at a particular polling station, and a recount can set things right. Ballot material cannot be destroyed so casually, and destroying the material will produce evidence, not like deleting a file on a computer.

And there's a critical problem with any electronic voting system whatsoever: only a few mathematicians can understand why it works. Anybody can understand the paper voting system, and can observe what is going on and convince themselves that the system is working. This is not true of any electronic (or even electromechanical) system: the voter has to take it on faith that the machines are operating correctly, that any cryptography involved does what the mathematicians pretend it does... Even if there was an electronic voting system that actually worked, which is in itself difficult, it sill would not obviously work, and that's a show-stopper.

Answer 2

I'd like to second Gilles' point wrt methodology. When considering many somewhat standard properties in the area (Privacy, Integrity, Verifiability) it is often not clear what the requirement is and which part of the mechanism fulfils it. Here are some issues that come to mind:

• As zedman9991 mentioned, the vote selling/coercion issue is too serious to hand-wave.
• Parties will know who voted for them and who didn't. This sets the privacy bar much lower than usual.
• If the authority generating the nonces does not like you, they can give the same nonce to another person or use it themselves. In either case it will end up in the pools of multiple candidates and thus invalidated.
• Candidates can trade votes. Candidates polling low can simply sell to those polling high.
• DoS in your system is a bigger issue than most: you can selectively target candidates. In other systems you can try and target individual voters (easy to DoS, but hard to pinpoint at scale) or the election itself (which, in the naive case will not change the result). Here, you can simply target candidate X and if successful, make sure they lose.
• There's a significant barrier to entry in the election: unless you can run your own IT, you are at the mercy of your contractor.

Also, regarding your comparison between the proposed system and paper:

One as an individual has control over one's computer but doesn't have control over the paper and the pen/pencil used.

It's pretty simple to bring your own pen/pencil. Furthermore, it is much easier to audit pens and paper stocks as they are physical objects in a somewhat centralised location that can't simply disappear vs the security of random people's computers.

Answer 3

Disclaimer: I might well have misunderstood or missed some critical point.

As I understand point #13, the list of NR's (NR = {nonce, random ballast}) is disclosed after the vote to allow verification of actual vote cast:

13. The election authority publishes the nonce files mentioned in point 3.

...

3. The election authority (I named it to be able to refer to it later) creates 1 256 bit nonce per voter, adds 256 0 bits before it, as well as 256 bit more random data and encrypts those 768 bit with the respective voter's public key. The nonces are put into a random order and saved.

At that point, if I wanted to know who you voted for - for example to see whether you did what I paid/threatened you for -, I could get your public key (it is public), and try encrypting all published NR's with it using the same algorithm of point #3, and see when the encrypted value matched one of the published values for your constituency.

I would need to run as many encryptions as there are voters, but no more; so whatever encryption algorithm is used, my problem would be no more expensive than the one tackled by the voting authority when it generated one encryption for every voter, plus the constituency-matching part, which could be significantly optimized (e.g. by using a Bloom filter).

I believe that it would only take very few public exposures to convince the public that such a scheme is not private enough, and assuming that I will have, and always will have, significantly less computing power than the voting authority is unreasonably optimistic. Ideally I'd like my vote to remain secret for (at least) the rest of my lifetime. Destroying paper ballots is easy - erasing data from anyone who might have downloaded it is not.