Alok Menghrajani

Security engineer at Square. Previously co-author of Hack and put the 's' in https at Facebook. Maker of CTFs.

Home | Contact me | Github | Twitter | Facebook

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

David Chaum solved this problem more than 30 years ago using blind signature. His solution can however be difficult to understand as it involves mathematics and cryptography.

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.

  1. In the first phase, everyone chooses a random number and casts a vote of the form (random_number, vote). E.g. (1912, blue), (7821, red), etc.

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

Other approaches

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.