Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
119 lines (114 sloc) 4.42 KB
---
layout: post
title: 'A simple, auditable and anonymous voting scheme'
permalink: '/simple_auditable_anonymous_voting_scheme/'
tags: ['voting', 'algorithm']
---
<div class="lead">
<p>
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).
</p>
<p>
<a href="http://en.wikipedia.org/wiki/David_Chaum">David Chaum</a> solved this problem more than 30 years ago using
<a href="http://en.wikipedia.org/wiki/Blind_signature">blind signature</a>.
His solution can however be difficult to understand as it involves
mathematics and cryptography.
</p>
<p>
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.
</p>
<p>
Credits to Manish Jethani and Shaanan Cohney for helping me put all
this together.
</p>
</div>
</div>
<section>
<h3>A few assumptions</h3>
<ul>
<li>
We have N people who want to cast a vote on a given matter, e.g.
"which color should we paint the bike shed?".
</li>
<li>
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.
</li>
<li>
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.
</li>
<li>
Everyone is communicating annonymously using a technology like tor.
The scheme can be adapted to not require tor.
</li>
</ul>
</section>
<section>
<h3>Two phase scheme</h3>
<p>
The voting process involves two phases.
</p>
<ol>
<li>
<p>
In the first phase, everyone chooses a random number and casts a vote of
the form <code>(random_number, vote)</code>. E.g.
<code>(1912, blue)</code>, <code>(7821, red)</code>, etc.
</p>
</li>
<li>
<p>
Once exactly N votes have been cast, everyone checks that the votes
contains their unique <code>(random number, vote)</code> pair and sends
<code>signed(privkey, [vote1, vote2, ..., voteN])</code>.
</p>
</li>
</ol>
<p>
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.
</p>
<p>
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.
</p>
<p>
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 <a href="http://en.wikipedia.org/wiki/Dining_cryptographers_problem">dining
cryptographers problem</a>.
</p>
</section>
<section>
<h3>Other approaches</h3>
<p>
Besides this simple scheme, it is possible to leverage blinding
signatures, polynomial computation or homomorphic cryptography
to achieve the same properties.
</p>
<p>
I'll let Shaanan write up his solution.
</p>
</section>
<section>
<h3>Links</h3>
<ul>
<li><a href="http://en.wikipedia.org/wiki/End-to-end_auditable_voting_systems">End-to-end auditable voting systems</a></li>
<li><a href="http://en.wikipedia.org/wiki/David_Chaum">
David Chaum</a></li>
<li><a href="http://en.wikipedia.org/wiki/Blind_signature">Blind signature</a></li>
<li><a href="http://crypto.stackexchange.com/questions/3474/approach-towards-anonymous-e-voting">Approach towards anonymous e-voting</a></li>
<li><a href="http://politics.stackexchange.com/questions/17/what-challenges-remain-for-online-voting">What challenges remain for online voting?</a></li>
<li><a href="http://politics.stackexchange.com/questions/24/is-it-possible-to-implement-an-electronic-voting-system-which-is-as-secure-as-pe">Is it possible to implement an electronic voting system which is as secure as pen-and-paper voting?</a></li>
<li><a href="http://en.wikipedia.org/wiki/Dining_cryptographers_problem">Dining cryptographers problem</a></li>
</ul>
</section>