Approach towards anonymous e-voting

I want to implement an internet-based e-voting system. Voters shall be able to cast their vote for one out of n possible candidates. Each candidate has his own ballot-box kept by and at a trustworthy third party. This third party is absolutely trustworthy insofar as it can be trusted to attend to his duties of supervising the cast diligently. However it is not without bias and hence under no circumstances must be able to see which voter voted for which candidate.

This problem can be approached using homomorphic encryption. Votes are homomorphically encrypted and homomorphically added to the ballot-boxes. In order to prevent the third party from gaining any knowledge of any vote cast every voter puts one vote into every ballot-box. n-1 times this vote will be "0" for "no vote for this candidate" and only one time it will be "1" for "vote this candidate".

One unpleasant side effect of this approach is that the third party apparently is not able to check the correctness of every single vote. A voter may try to give a "1" to more than one candidate or a "2" to a single one. Of course the third party could hand out pre-signed voting coins in advance that the voters would use for casting their votes. However the third party would recognize these coins, i.e. their values, and hence still know who voted for whom.

Do you have any idea how to solve this problem relying on as few possible other (trusted) third parties as possible?

-
heliosvoting.org might help ? their source code is available too –  sashank Aug 8 '12 at 4:00

Using exponential Elgamal as the encryption function,

1. Define the list of candidates: e.g., Alice, Bob, Carol
2. Voters submit an encryption of their vote: e.g., to voter for Alice: $v=\langle\mathsf{Enc}(1),\mathsf{Enc}(0),\mathsf{Enc}(0)\rangle$
3. Use an OR-proof (Fig 2) to show each ciphertext encrypts a 0 or a 1: e.g., $\langle \pi_1, \pi_2, \pi_3 \rangle$
4. Under encryption, add up the ciphertexts in the vote: e.g., $v_t=\mathsf{Enc}(1)\cdot\mathsf{Enc}(0)\cdot\mathsf{Enc}(0)=\mathsf{Enc}(1+0+0)=\mathsf{Enc}(1)$
5. Use the same OR-proof to show $v_t$ encrypts a 0 or a 1 (a 0 means the voter abstained)
6. Submit $\langle v, \pi_1, \pi_2, \pi_3, v_t, \pi_t \rangle$

Anyone can check the validity of $\pi_1, \pi_2, \pi_3$. Anyone can add up $v$ to see it is $v_t$. Anyone can check $\pi_t$.

The election officials take $v$ from everyone, add them up element-wise. Then the results are decrypted (usually with a shared key) using a protocol that proves it was decrypted correctly (see same paper for how to do this).

-

Yes. There has been extensive research on this question: there is even a community of cryptographers who work on building voting schemes of this sort (see end-to-end auditable voting system). I'll give you some advice based upon the experience from that field.

Don't design your own. Don't try to design your own. There has been extensive research into this subject and if you try to invent the wheel it is likely you will end up with something that is either insecure or inferior.

Instead, if you are not using this for a public election, I recommend you use Helios. It is a state-of-the-art system, with among the best security that it anyone knows how to achieve for Internet voting -- and it has a high-quality implementation that you can just use, with almost no effort on your part. It has been vetted more thoroughly than anything you will be able to design on your own.

Internet voting is not safe enough for public elections. If you are planning to use this for a public election for public office, my recommendation is: don't. Just don't. The security risks are too grave. To learn more about this topic, I recommend reading the following: Online Government Elections System - Is it possible? and Secure Internet Polling and this and this and this.

-
+1 for Internet voting is not safe enough for public elections. Two simple arguments, among many: a) If voting is possible in privacy, it is easy to sell one's vote and give to the purchaser a demonstration of the vote casted. This becomes an issue when more than a small fraction of the votes is casted in this way. b) Unless there is a trusted device with human-perceptible feedback, an honest voter has no mean to insure the integrity of whatever computer/browser is used to cast the vote, and that could be pwned to give the impression of voting for A, when externally the vote is cast for B. –  fgrieu Aug 8 '12 at 10:45
Designing your own isn't categorically bad. I can think of a number of reasons to design your own. 1) learning, 2) improvements over existing systems, 3) school homework. That said, I wouldn't use something I designed until it has been published and peer-reviewed. –  mikeazo Aug 8 '12 at 11:40
I see D.W.'s point that re-inventing the wheel is rarely a good idea. However as mikeazo pointed out I'm trying to learn and experiment and this always includes making mistakes. –  Thomas Lieven Aug 9 '12 at 7:30
Also the system I'm planning is not 100% a real e-voting system and that is why not all requirements for such a system need to be satisfied. In fact some features of an e-voting systems are not desired at all. –  Thomas Lieven Aug 9 '12 at 7:34

Something along these lines could be accomplished with zero-knowledge proofs. The voter proves that each one of the ballots is in the set $\{0,1\}$ and that the sum of the ballots is $1$.

Prove this to each of the $n$ trusted third parties. Each of the third parties signs the ballots once the proof is done. Then the voter casts the ballots. Signatures can then be checked to make sure a vote hasn't changed after the proofs.

-
I think this would require stronger computational assumptions, but computational NIZK arguments (www0.cs.ucl.ac.uk/staff/J.Groth/MultiStringModelFull.pdf) could be used to remove that part of the interaction. $\:$ –  Ricky Demer Aug 7 '12 at 19:06
How would such a NIZK proof look like? I thought about this but everything I came up with either violated privacy/secrecy of a vote and/or did not rule out that the sum of the ballots might contain negative votes. –  Thomas Lieven Aug 7 '12 at 20:28
Well, my understanding is that they would look like one [publicly verifiable two-message computationally witness-indistinguishable argument that [[sufficiently many of certain strings (specific parts of the strings provided by the authorities, one from each authority) are in the range of a specific pseudo-random generator at the relevant security parameter] or [the list of n votes satisfies the necessary conditions]]] $\;\;\;\;$ for each authority, each one using as its verifier message the main part of that authority's string. –  Ricky Demer Aug 7 '12 at 21:07
Paillier is patented so it is questionable if you can use the Baudron et al. approach for an implementation. It inherently requires Paillier because of the way multiple candidates are packed into a single ciphertext. A slightly less efficient but much simpler approach is given by Hirt in Chapter 5 of his dissertation: ftp.inf.ethz.ch/pub/crypto/publications/Hirt01.pdf –  PulpSpy Aug 13 '12 at 15:36
P.S., since you are correct about the billions of e-voting systems (slight exaggeration perhaps), I summarize the literature in Chapters 3 and 9 of my dissertation. The bit you are asking about is in 3.3.5: people.scs.carleton.ca/~clark/theses/phd_electronic.pdf –  PulpSpy Aug 13 '12 at 15:38

You can use blind signatures: "Blind signatures can also be used to provide unlinkability, which prevents the signer from linking the blinded message it signs to a later un-blinded version that it may be called upon to verify. In this case, the signer's response is first "un-blinded" prior to verification in such a way that the signature remains valid for the un-blinded message."

A trusted party gives each voter one valid blind signature. That party has no idea what it's signing, but it does know that each voter gets only one.

Each voter encrypts his vote and sends it to the trusted signing party to get it signed. The trusted signing party signs exactly one ballot for each voter. The voter can then decrypt the signed vote and hand it to the ballot boxes. The ballot box checks the signature and counts one vote for each unique signature. Neither the ballot box nor the signer has any way to know which voter gave which vote.

-
I thought about blind signatures, too. Blind Signatures guarantee anonymity and authenticity of the ballot. What they do not guarantee is correctness. So to guarantee correctness you need to check the ballots in advance or afterwards. Afterwards becomes problematic if ballots are to be added homomorphically. Checking in advance would require an extra trusted third party, something I'm desperately trying to avoid. –  Thomas Lieven Aug 9 '12 at 7:39
What do you mean by correctness? What would an incorrect ballot be? –  David Schwartz Aug 9 '12 at 7:40