6
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ heliosvoting.org might help ? their source code is available too $\endgroup$
    – sashank
    Commented Aug 8, 2012 at 4:00

5 Answers 5

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm confused as to how you add the encrypted votes, when each voter is supposed to have encrypted his vote with his own private key. ElGamal addition results can be decrypted only using the same key that was used to encrypt the parts no? $\endgroup$
    – PentaKon
    Commented Aug 1, 2019 at 18:05
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ +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. $\endgroup$
    – fgrieu ♦
    Commented Aug 8, 2012 at 10:45
  • 3
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented Aug 8, 2012 at 11:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thomas Lieven
    Commented Aug 9, 2012 at 7:30
  • $\begingroup$ 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. $\endgroup$
    – Thomas Lieven
    Commented Aug 9, 2012 at 7:34
  • 1
    $\begingroup$ Late comment: experimentation is not bad, but I would start off by learning (at least the basics of) what is already there. You aren't going to invent cryptography as well, aren't you? That's already done!. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 14, 2015 at 12:45
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Thomas Lieven
    Commented Aug 9, 2012 at 7:39
  • 1
    $\begingroup$ What do you mean by correctness? What would an incorrect ballot be? $\endgroup$
    – David Schwartz
    Commented Aug 9, 2012 at 7:40
3
$\begingroup$

Encryption based voting will always suffer for a different reason.

As a human, I cannot look at a numeric token to know if the value is "Yes" or "No". I have to 100% trust that the voting system is telling me this number is a vote for my candidate or not.

It doesn't matter if there's a solidly convincing mathematical proof. As an ordinary voter, I cannot perform the math that would convince me, Joe Failed-Algebra, of the validity of the system. It doesn't matter if the tokens arrive in the form of paper slips handed to me by an election judge, barcodes, buttons on a little black box, or anything.

The encryption based systems are impressive, they are fascinating, they are mental challenges. But they are not acceptable to humans.

Something we've lost in the rush to automate our lives is that the world actually functioned prior to the arrival of digital computers and 24-hour news. Our election system provides an entire month for votes to be tallied and carried to the nation's capital. In order for democracy to function, we do not need instant election results, despite the strong desires of the news networks to deliver them. Our only valid requirements are for a simple, fair system.

Improve this answer
$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Visual_cryptography can address some of these concerns. $\endgroup$
    – Alok
    Commented Jun 1, 2015 at 17:44
  • $\begingroup$ @Alok, visual cryptography is not a very good solution for two reasons. One is the complexity - how do I know that lining up two bits of paper proves anything? To counter it, consider that XOR has no inherent security, so I can produce a matrix of dots that displays "JOHNSON" when combined with mask A, but displays "SMITH" when combined with mask B. (Consider the cheating section of that same article.) The other problem goes back to election secrecy, and that you must not be able to leave the polling place with evidence of how you voted (or else you could sell your vote.) $\endgroup$
    – John Deters
    Commented Jun 3, 2015 at 21:40
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\:$ $\endgroup$
    – user991
    Commented Aug 7, 2012 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Thomas Lieven
    Commented Aug 7, 2012 at 20:28
  • $\begingroup$ 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. $\endgroup$
    – user991
    Commented Aug 7, 2012 at 21:07
  • 1
    $\begingroup$ 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 $\endgroup$
    – PulpSpy
    Commented Aug 13, 2012 at 15:36
  • 1
    $\begingroup$ 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 $\endgroup$
    – PulpSpy
    Commented Aug 13, 2012 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.