ABSTRACT
Electronic voting is probably the single most controversial application in the field of information security. Almost any area in information security, from computer security and cryptographic issues to human psychology and legal issues, is brought together when designing secure electronic voting systems. Not surprisingly, a wide variety of approaches have been used and a multitude of voting systems have been proposed. This chapter is about cryptographic schemes for electronic voting, or voting schemes for short,
whose main task is to facilitate a secure and private way of casting and counting votes.∗ The first wave of interest in voting schemes started in the early 1980s with the publication of Chaum’s paper on anonymous communication [8]. Subsequently, approaches to voting were discovered, where the emphasis was on concepts and feasibility, much like other work in cryptography in that decade. A second wave started in the 1990s with the emergence of the World Wide Web, which created a huge interest in remote voting. Also, the emphasis shifted to efficiency concerns resulting in quite
15-1
practical schemes. And, currently, we are experiencing a third wave because of the “Florida 2000” U.S. election fiasco, which renewed interest in voting from polling stations leading to voting schemes that combine cryptographic and physical aspects. Voting schemes are intended to form the cryptographic core of electronic voting systems. The
general goal of these schemes is to eliminate as many security problems as possible, thereby limiting the number and the extent of the residual assumptions needed to ensure the security of the overall voting system. For example, proper encryption and authentication of votes ensure that no illegal modifications of
existing votes and insertions of extra votes are possible, whereas appropriate redundancy techniques from distributed computing (realizing Byzantine fault tolerance; see also Chapter 29 of Algorithm and Theory of Computation Handbook, Second Edition: General Concepts and Techniques) ensure that no votes can be deleted from the system. However, these basic techniques which are commonly used to implement the main goals in information security, namely, confidentiality, integrity, and availability (CIA) are not sufficient for the special combinations of security properties found in electronic voting. For example, a strict level of ballot secrecy and full verifiability of the election result can only be achieved by using special forms of encryption and authentication rather than conventional ones. The strongest voting schemes thus employ advanced cryptographic techniques, such as threshold cryptography, homomorphic encryption, blind signatures, and zero-knowledge proofs, thereby eliminating the need for trusting individual (or small groups of) entities. This goes beyond what is common in the votingmachine industry, where the design, the implementation, and the operation of voting machines are essentially split between a very limited number of key players (often, involving just one company, at best two or three companies). The challenge is to find the sweet spot with the best trade-off between cryptography and other security measures.
