Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I was reading wikipedia about homomorphic encryptions, and one part got me a bit confused:

"The homomorphic property of various cryptosystems can be used to create secure voting systems, ..."

How would you possibly use homomorphic encryption to secure the voting process? Of course, you won't be able to intercept the results, but what if someone "injects" their own ciphertext into the ballot ciphertexts?

Wouldn't it be possible to forge an election, by tampering with the encrypted data?

share|improve this question
7  
4  
+1 for interesting question. –  Christoffer May 13 '13 at 8:06
    
I would expect it should have read "can be used to create more secure voting systems" or rather solve some problems of e-voting. However, the privacy issues and the transparency issues are still present, so you still won't end up with a result that's usable for largescale voting. –  Fake51 May 13 '13 at 8:25
2  
It's not an exact duplicate (I'm saying this to prevent unnecessary flags being raised), but your question was already at least partially answered in the In what ways does Full or Partial Homomorphic Encryption benefit the cloud? thread by three top rated answers there. If you could expand more on what's discussed there, that would be great IMO. ;) –  Noordung May 13 '13 at 9:06
3  
And for those new here who might not get @Lucas' joke: meta.security.stackexchange.com/a/884/485 –  Rory Alsop May 13 '13 at 9:17

2 Answers 2

up vote 12 down vote accepted

Homomorphic encryption is one of the two main structures for e-voting protocols, but the encryption part is not the whole protocol.

What homomorphic encryption does well is tallying. In such a system, each voter encrypts his vote (a zero or a one). Since the vote is encrypted, it can be managed rather easily: there is no problem in associating the vote with the voter. So the votes can be accumulated on a public bulletin board and everybody can check that his own vote is taken into account, or that nobody voted twice. When all the votes are obtained, homomorphism is applied to get the encryption of the sum of the votes, and the sum is then decrypted; the decryption private key is split among a few partially trusted authorities, who collaborate only for this single decryption. As long as at least one of the authorities is honest, the individual votes cannot be decrypted, and vote anonymity is maintained (we cannot know who voted what).

The tricky part in such systems is how to make sure that an encrypted vote is really the encryption of a 0 or a 1, and not the encryption of something else. Practical protocols for e-voting which rely on homomorphic encryption, use non-interactive zero-knowledge proofs, which are rather technical but boil down to the following: with sufficient mathematics thrown at the problem, it is possible, for some asymmetric encryption algorithms and with the cooperation of the voter himself, to prove that an encrypted value is really the encryption of a 0 or a 1 but not of anything else. This, of course, cannot be done without the cooperation of the voter himself, otherwise it would be a gross weakness of the encryption system.

The other main structure for e-voting protocol is mix networks: the votes go through a sequence of entities who shuffle them randomly (this has applications others than e-voting, e.g. Tor). Nested encryption is used so that the shuffling cannot be traced externally. At the output of the last mixer, the votes are decrypted, but cannot be associated with the voters, as long as at least one of the mixers is honest. Since the votes are decrypted, they are trivially verified to be syntaxically correct (a 0 or a 1, nothing else). On the other hand, convincing voters that their vote was not lost, or that nobody voted twice, becomes much harder -- solutions for that involve, again, some ZK proofs.

The International Association for Cryptologic Research, when it must vote to elect its directors, uses Helios Voting, which relies on homomorphic encryption (with the ElGamal algorithm, and Chaum-Pedersen ZK proofs).

share|improve this answer
2  
I think I understand what Lucas meant with "bear territory". Thank you. –  asdasdasd May 13 '13 at 15:44

You are right, the problem with e-voting is validation, not encryption. One can change values on the fly prior to encryption. What is important is the ability to check the votes after the fact.

Scantegrity has this all worked out, they use a one-time-pad to assign a code to each candidate that is unique to each ballot.

Sample ballot

The codes and ballot numbers are published publicly. Only some tiny percentage of votes need to be checked to get very high statistical reliability of the election results. If there are discrepancies, the physical ballots can be hand-counted again.

The online voting version mails physical ballots similar to the above type. On the website, the user enters in the code that correspondents to the ballot and candidate. As each ballot/candidate voting choice is unique, the malware cannot simply change the vote because it does not know the code that corresponds to the preferred candidate.

As with Scantegrity, the ballots and candidate numbers (but not the candidate names they correspond to) are posted publicly. The mail-return acts as a futher verification and (in the case of technical problems) a remediation step.

share|improve this answer
2  
In the link from the above comment from TildalWave, Ben Adida talks about how the problem with e-voting is that your computer can contain malware that does the voting for you. So, in that case; it could change the values prior to encryption... What i'm asking is; isn't that still possible after the encryption? Being homomorphic 'n' all. –  asdasdasd May 13 '13 at 9:41
    
That's why they do ballot mailings on the back-end. They only need to then scan a tiny fraction of the ballots to tell if the computer value and the mailed ballot to get the same level of confidence as a hand recount. –  Indolering May 15 '13 at 20:09
    
Is it possible to only look at a portion of the encryption to know something about the encryption? –  asdasdasd May 16 '13 at 7:33
    
Does the above revision answer your question? –  Indolering May 17 '13 at 1:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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