Of Elections and Electrons

P Y A Ryan, University of Newcastle

Abstract

Digital voting technologies are currently very topical and hotly debated, especially in the US with a presidential election looming. It is essential that voting systems are both trustworthy and trusted. Various schemes and technologies have been proposed, and indeed deployed, that take drastically different approaches to achieving assurance. At one end of the spectrum, we have approaches that claim to achieve assurance through system verification and testing. At the other end, we have the run-time monitoring school. Another way to characterize this dichotomy is to observe that the former approach seeks to verify the electoral system, the latter seeks to verify an actual election.

The first approach is typified by the touch screen (DRE) machines currently widely used in the US. Many researchers are profoundly mistrustful of the claims for verification and trustworthiness of such systems and indeed recent reports indicate that such mistrust is well placed, see for example [1].

The second approach is exemplified by the cryptographic schemes proposed by, for example, Chaum [2] or Neff [3]. These strive for complete transparency, up to the constraints imposed by the ballot secrecy requirements, and seek to achieve assurance via detailed monitoring of the process rather than having to place trust in the system components.

In between we find the paper audit trail approach (the “Mercuri method”) that seeks provide the means to check on the performance of DRE machines and recovery mechanisms, [4, 5].

In this talk I discuss the dependability and security requirements of election systems, primarily accuracy and secrecy but also availability and usability. I outline the extent to which these various approaches meet these requirements.

I then discuss in more detail the design philosophy of the Chaum/Neff school and illustrate this with a variant of the Chaum scheme. These schemes support voter verifiability, that is, they provide the voter with a means to verify that their vote has been accurately recorded and counted, whilst at the same time maintaining ballot secrecy. The essence of this scheme is to provide the voter with a receipt that holds their vote in encrypted form. The challenge is to ensure that the decryption of the receipt that the voter sees in the booth is identical to the decryption performed by a sequence of tellers. The scheme combines a cut-and-choose protocol in the booth followed by robust anonymising mixes.

The original scheme uses visual cryptography to generate the encrypted receipts on a pair of transparent sheets. Correctly overlaid in the booth, these sheets reveal the ballot image. Separated they appear just to be random pixels. The voter retains only one of these sheets. The scheme presented here uses a simpler mechanism based on the alignment of symbols on adjacent strips of paper. This appears to be both simpler to explain and understand and to implement.

We also note that the dependability of complex computer based systems depends as much on socio-technical factors as the purely technical details of the design. We briefly describe error handling and recovery strategies for this scheme.

Poorly conceived, implemented and maintained voting technology poses a serious threat to democracy. Confidence in the integrity of voting systems appears to be at an all time low in the US for example. Schemes with a high degree of transparency along the lines of the Chaum or Neff proposals hold out the hope of restoring some of that confidence. In the words of Sylvio Micali at the DIMACS workshop on Security Analysis of Protocols “It is our duty as cryptographers to save democracy!” [7].

References

[1] Avi Rubin et al, http://avirubin.com/vote/analysis/index.html

[2] David Chaum, “Secret-Ballot Receipts: True Voter-Verifiable Elections.

[3] Andy Neff, www.votehere.com

[4] Rebecca Mercuri, http://www.notablesoftware.com/evote.html

[5] David Dill, http://www.verifiedvoting.org/

[6] Peter Y A Ryan and Jeremy W Bryans, “The Prêt à Voter Scheme” Newcastle Computer Science Tech Report, to appear.

[7] http://dimacs.rutgers.edu/Workshops/Protocols/