Intuitively, many people think that you cannot have an electronic voting scheme which is auditable (i.e. everyone can count the votes) while preserving privacy (i.e. each individual vote is secret).
I have come up with a much simpler scheme to show that these two properties are not mutually exclusive. If you want to actually implement such a scheme, you probably want to read David Chaum's work.
Credits to Manish Jethani and Shaanan Cohney for helping me put all this together.
A few assumptions
- We have N people who want to cast a vote on a given matter, e.g. "which color should we paint the bike shed?".
- Every user has a public-private key pair, which can be used to digitally sign messages. I'm going to skip the process to acquire these keys and how the trust is established.
- The communication medium is a public forum, e.g. an irc channel or web application. The scheme can be adapted for peer-to-peer networks.
- Everyone is communicating annonymously using a technology like tor. The scheme can be adapted to not require tor.
Two phase scheme
The voting process involves two phases.
In the first phase, everyone chooses a random number and casts a vote of the form
(random_number, vote). E.g.
(7821, red), etc.
Once exactly N votes have been cast, everyone checks that the votes contains their unique
(random number, vote)pair and sends
signed(privkey, [vote1, vote2, ..., voteN]).
After N people have signed the votes, the process is over. Everyone has confirmed that their vote was included, everyone can compute the outcome of the vote and nobody reveals their individual vote.
If somebody votes more than once, either the number of signatures will not match up or there will be more than N votes, in which case the process ends without any result.
Keep in mind that this very simple scheme has a caveat: any participant can "jam" the system by continuously casting multiple votes. This is similar to the issue discussed on dining cryptographers problem.
Besides this simple scheme, it is possible to leverage blinding signatures, polynomial computation or homomorphic cryptography to achieve the same properties.
I'll let Shaanan write up his solution.