Design and Prototype of a Coercion-Resistant, Verifiable Electronic Voting System.

In elections, it is important that voters be able to verify that the tally reflects the sum of the votes that were actually cast, as they were intended to be cast. It is also important that voters not be subject to coercion from adversaries. Currently most proposed voting systems fall short: they either do not provide both properties, or require the voter to be a computer. In this paper, we present a new voting system that uses voter knowledge to allow voter verification by using a receipt that is uninformative for a coercer without access to the voting machine or the contents of the cast ballots. Our system does not assume any trust in the voting machine, but requires a few other assumptions which we believe to be reasonable in the real-world situation. A basic prototype of this system is available on our website. I. INTRODUCTION The US presidential elections of 2000 made the general public aware of the problems of producing a voting system that could be trusted by the voters to submit their votes correctly. Despite the public review and control of the US electoral system, many US citizens felt that the system had failed them. Although the problems did not originate in the 2000 election, the situation where a very small number of votes was sufficient to flip the final tally raised the public's awareness of the inadequacy of the system. The problem of producing a fair voting system has been well-known in countries and situations where adversaries have a very high degree of control. In totalitarian societies (or other situations with almost complete adversarial control), it may be futile to attempt to solve this problem. Such societies provide no guarantee that the adversary will comply with the solution, no guarantee that the observers and complainants will be able to speak up, and no guarantee that the situation will be corrected even if there is a valid complaint. However, in a free democratic society in the 21st century, the electoral system is subject to public review and control. Its failures do not have to be possible. If an electronic voting system is to be applied in secret- ballot elections, it has to be receipt-free, i.e. not allow a voter to carry away any evidence of who he voted for, since such evidence would permit vote buying and coercion. Receipt- freeness is hard to combine with voter verifiability: if a voter is able to verify that his vote was counted as he cast it, what could prevent him from proving how he voted to a third party? Cryptography can help address this seeming incompatibility between receipt-freeness and voter verifiability, if the voter has an encrypted copy of his vote and can verify that his encrypted vote made it to the final tally. However, that requires the voter to be able to verify that the encryption of his vote is correct. Chaum's layered receipts (5) (discussed below) solve this problem partially: they allow verification, but only with probability 50%. In this paper, we examine these properties and survey the principal current approaches to electronic voting systems. We then present a new design that improves on the previous work, by being (arguably) the first one that achieves both voter verifiability and coercion resistance, while not assuming the voter is a computer, not relying on correct behavior by the voting machine, and detecting close to 100% of misbehaviour. Section II briefly discusses the requirements for a secure election system. Section III presents a brief overview of methods used in receipt-free election schemes. Section IV discusses the most recently implemented election schemes. Section V presents our election scheme. Section VI discusses the practical applicability of our scheme. Section VII describes our prototype. Section VIII offers some concluding remarks.