  |
ERCIM News No.48, January 2002 [contents]
|
|
|
eVote: Practical Electronic Large Scale Electionsby Douglas Wikström The primary aim of this project is to create a secure and cost-efficient electronic balloting system that makes it possible for voters to vote from their PCs at home. Traditional election systems are costly, inefficient and error prone. Consider for example the US presidential election! It often takes days of vote counting before the result can be announced. Some countries have problems with corrupt election administrators who either report false results or try to coerce the voters. These are problems that could be solved by cryptographic protocols. When asked, most people would list the following as the most important requirements on an election:
It turns out that the traditional method for ensuring anonymity also implies that it is impossible for a voter to prove that she voted in a specific way. This makes it impossible for a buyer of votes to verify that the seller voted the way she promised. Additionally the traditional method implies that a voter can not correlate his vote to an arbitrarily chosen other vote. For many protocols proposed in the literature these implications do not hold. This shows that the requirements listed above are not sufficient to ensure that an electronic voting protocol should be considered secure, and formal definitions are needed. Another important issue is correctness. In traditional elections there are many physical obstacles that prevent large-scale cheating in most situations. These obstacles are not present in the electronic world; if an adversary can mount a successful attack once he can do it many times, with marginal additional effort. Consider also the counting of votes. In many traditional systems the votes are counted at least twice by independent groups of people in different physical locations. We assume that at least some of the officials will protest publicly if the results differ. The above and other similar problems highlight that there are many implicit assumptions that make the traditional election system secure. To construct a secure electronic election system we need to identify these assumptions. Electronic Election Systems When constructing an election protocol system we try to mimic traditional elections, in that the trust is distributed. To do this we apply traditional cryptographic primitives like encryption, commitments, and computational proofs. There are different approaches to the problem, and they all have their advantages. SICS has focussed on protocols based on a construct called a mix-net. A mix-net can, if properly constructed, ensure anonymity of the voter and at the same time correctness. The advantage of mix-nets is their flexibility, and that they can be applied in other scenarios too. The idea of this approach is simple. Each candidate holds a secret key and has published a public key. From these public keys a joint public key is computed which corresponds to a joint secret key that is unknown to all candidates. To cast her vote the voter encrypts her vote using the joint public key of the candidates and sends the encrypted vote to the candidates. Then the candidates perform a protocol, where they sequentially mix the encrypted votes. Each candidate gets a list of encrypted votes as input and produces a new list containing encryptions of the same votes, but in a different random order. After having done this they jointly decrypt the list of encrypted votes. Now the connection to the voter is broken, and anonymity is ensured. To ensure that only valid votes are counted, each voter holds a secret key, for example on a smart card, and a public key is associated with the voter. The voter can use her smart card to digitally sign her encrypted vote, and the candidates can verify that the data was indeed signed by a specific voter. Unfortunately the use of digital signatures and mix-nets allows the voter to sell her vote, since during the encryption and signing process, she computes data that prove that she voted in a specific way. There are some partial solutions to the selling problem, but they are all very impractical, and mainly of theoretical interest. Ensuring correctness efficiently is the other big challenge. How can we do this without forcing the candidates to disclose anything about the exact choice of reordering the inputs? It turns out that this is difficult to solve efficiently, and even harder to prove to be secure. A number of published constructions have been broken. Interestingly, solving this problem also gives a solution to the problem of handling software bugs or hardware errors as they will be discovered as well with high probability. Future Research Link: |
