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