11

Electronic voting has been considered technical infeasible for a long time. And recently I watched a video from the channel Computerphile on YouTube where they bring up all the problems that come along with e-voting.

But with distributed ledgers and homomorphic encryption in my mind I could find any problem that cannot be solved. To be fair this video is one and half year old, but still one can guess that this guy has heard of these techniques.

I am not a security expert yet I could imagine a system, that guaranties both anonymity and trust in the result:

  1. Setup a block chain where every node agrees on the voting algorithm. (Not hard at all and this already solves the problem of trusting the software)
  2. Generate Private and Public encryption key. Give the public key to anybody that is allowed to participate in the vote. Spread the private key among authorities you trust not to collude.
  3. Every participant has an account on the block chain with a private key that signs the voting "transaction". Every account has one vote, which is ensured by the voting software that every node on the block chain agreed on.
  4. Because all the transactions are on a block chain every voter can trace his/her vote and verify it got added to the overall result. (Which solves another major problem: Ensure every vote is added to the overall result.)
  5. A primitive voting algorithm could look like this: For every party a participant may vote he encrypts a zero or a one together with some salt (so no lookup can be performed) with the election public key. Then he signs his transaction or vote with his block chain public key and his vote gets processed: The zeros and ones are added to each of the party counters. For every vote the sum of the vote is calculated and decrypted. In that way you can tell for sure only one one is added to one of the party counters (sum must be one), but you cant tell which party the participant voted.
  6. Decrypt the final result.

Of course for any decryption the authorities who hold a part of the private key must agree on that decryption.

So what in the world is the problem that cannot be overcome with electronic voting?

Anders
  • 64,406
  • 24
  • 178
  • 215
flxh
  • 229
  • 1
  • 6
  • Comments are not for extended discussion; this conversation is definitely going to be a long discussion, so it has been [moved to chat](http://chat.stackexchange.com/rooms/45394/discussion-on-question-by-flxh-why-is-e-voting-still-a-problem). – Rory Alsop Sep 15 '16 at 09:14

2 Answers2

9

Technically, your solution is pretty similar to CGS97 (note the date) which is the base of Helios and its descendants. As a general approach it's very reasonable, but completely lacking wrt to preventing vote-selling and bribery/threats (Receipt Freeness and Coercion Resistance in the literature):

Lack of RF example: Suppose I promise to give you $100 if you vote for my candidate, and show me the randomness you used (i.e. a receipt) to encrypt your vote as proof. This is a known issue with textbook Helios (mentioned in the original paper) which is fixed in various degrees in later works.

Your suggestion to use a blockchain to implement the bulletin board is reasonable but I would argue people active in the area are aware.

There are a few more issues with your solution:

  • It's trivial to copy other People's votes. This is considered to be bad for privacy. Malleability attacks as well.
  • Requiring that a person's ballot sums up to one is not adequate. Suppose I give -100 votes to candidate X and +101 votes to candidate Y.
  • Combining the above, take all posted the votes on the board and add them up. Let's say there are n of them. Invert the sum. That will produce a ballot summing up to -n. Add n+1 votes to your candidate. You now have a ballot that negates all the previous ballots and moves all their votes to your candidate.
  • Most of the above is solved with Zero Knowledge protocols demonstrating the individual parts of the ballot are 0/1 in addition to summing up to 1, plus some non-malleability requirements.
  • Having the authorities decrypt a mini-sum for every voter can be inefficient. Also, how do you verify they behaved correctly? If your answer is ZK, why not move that to the voter?
  • When you talk about salts and encryption, I think you mean IND-CPA. You probably need NM-CPA though (also take a look at IND-CCA, but it's not strictly necessary).

Going back to big picture stuff, we also want to consider voting from compromised PCs, having an verification process that people can and will follow, the fact that elections would attract state-sponsored adversaries, and the fact that a do-over in case of failure would be extremely costly (in terms of public trust as well as $$$).

TL;DR: There is extensive literature in the area (both in-booth and internet), but it's also a very hard problem.

Nolyc T'nega
  • 146
  • 4
  • Very good answer, however the **n+1** and **-n** issue you mention isn't really a problem if only one bit is encrypted for every party, and I'm not a cryptography expert either, so I'm sure there are smarter people than, who already have a better solution for this one. The thing with vote selling and having a **proof** for the guy who paid your vote is a problem I didn't think about, indeed. Many thanks for your extensive answer :) – flxh Sep 20 '16 at 07:37
  • But how do you enforce or check that parties only encrypt a 0/1? In paper voting, if you find an envelope with 2 ballots you throw it away. In homomorphic tallying, you don't get to see that, so you need some sort of guarantee that each "envelope" is indeed a 0/1. – Nolyc T'nega Sep 20 '16 at 08:46
  • I think you're right with homomorphic addition you can't ensure that. But what you could do is only allowing positiv numbers (unsigned ints). The plain text you encrypt is 3723400001 or 2389900000. Here the first 5 digits are random noise. If each counter for a party receives such an encrypted vote. All the votes from a voter can be added, then decrypted. The modulo of all the votes added up and divided by 100000 must then be 1. Again this is just a primitiv example. – flxh Sep 20 '16 at 10:02
  • 99999 = -1 mod 100000 – Nolyc T'nega Sep 20 '16 at 10:10
  • Know what you want to say 50000 to candidate A + 50001 to candidate B ads up to 100001 mod 100000 = 1 ... You're right again. But as I said I think there is mathmatical way to solve this problem. The main issue with my system is the lack of receipt freeness I guess. – flxh Sep 20 '16 at 10:14
2

This algorithm you have proposed is surely a good one. But perhaps it lacks the concept of privacy. This perhaps is the reason, why e-polling is avoided overall.

Privacy here refers to the set of responses/plain text a user might send. {0,1}. This refers to 'known plain text attack'. An adversary, laying a man in middle attack might intercept the cipher code. Now, knowing the plain text, public key and the cipher text, he can use many sophisticates tools, or maybe by simple brute force attack to crack the salt as well as the key used for encryption!(Of course, the time taken to crack would definitely depend upon the length of key and salt).

Penguine
  • 165
  • 6