secure elections, electronically

At eschaton, avedon writes

I join with tech-savvy supporters of democracy everywhere in saying that there is only one appropriate means of making elections secure: Paper ballots, hand-counted on the night, in public.

I hope it doesn't disqualify me as tech-savvy, but I think there are ways to make e-voting more secure, reliable, and open than paper voting. The problem with today's e-voting systems is not that they're electronic, but that they're black boxes. The vote enters the box and disappears. It doesn't have to be that way.

To avoid fraud, a voting system needs to be auditable. Ballots, once cast, must be retrievable. Their content must be tamperproof. Ideally, any voter should be able to check whether their ballot has been counted and counted correctly. Paper ballots achieve the first of these, but as the Florida chads showed, they don't achieve the last two.

Non-secret ballots achieve all three. Voters cast ballots, and since the association between voter and ballot remains, voters can themselves audit the results of elections. They can see their ballots as well as everyone else's. Tampering with votes is nearly impossible (no one ever worries about voter fraud in Congressional votes). Intimidation and retribution, unfortunately, are not.

Suppose, however, that a voting system could be designed that assured privacy, while making ballots themselves public and allowing individuals to audit their votes. Such a system would be strongly resistant to tampering, even if electronic. An electronic system would, in fact, make tampering more difficult by making it easier for more voters to verify their votes. If half the population did so, tampering with a single vote would lead to detection half the time.

What might such a system look like? Let's start with the ballot itself. A ballot is a series of boxes, some checked, some not. A ballot with 100 candidates and 50 propositions (I live in california) has 200 boxes, each with a potential value of 1 or 0. A 200-digit binary number. 25 bytes. In the 2004 presidential election, about 120 million votes were cast. That's 3GB without compression, or about one DVD's worth. Most ballots would be significantly smaller. Any state election would fit on a CD-ROM. Any county's results could be downloaded quickly over the net.

Those are, of course, only the ballots themselves, not the identifiers that would allow voters to verify their results. How would those come to be? Here, things start to get a bit technical.

How would voters verify that their ballot is in the public record? Give each voter a secret key. When they vote, combine that key with the ballot and pass the resulting string of digits through a cryptographic hash function. One key property of such functions is that it is extremely difficult to generate a given hash result without knowing the hash inputs, making it infeasible to generate a pair for a particular voter without access to the key. Append the result of that hash function (not the key) to the ballot. Hash values used for such verification purposes are commonly referred to as digital signatures. Voters wishing to verify that ballots with their choices and their key are in the database can do so by locating ballots with their signature. They can also verify that their key has not been used only once.

Since every ballot can be (at least potentially) verified and the total number of ballots must match the voter rolls (the same mechanism we use today) attempts to change results run a high risk of detection. In a 10,000 voter election where only 1% of voters verify their ballots, an attempt to move results by 1% would be detected about two-thirds of the time, and the detection rate rises dramatically with increases in either the rate of ballot checking or the number of voters in the election.

So, what would be the problems with an approach like this? The main ones appear to be false attacks on the integrity of the system, and the initial verification and distribution of completed ballots. When any voter can challenge the accuracy of an election by claiming that a valid ballot hasn't been counted, it is important to ensure that their claims can be verified, that they did in fact cast the ballots they claim are missing. Ballot verification and distribution is important because the "ballot" the voter will take home is merely a long number. Voters will not be able to look at the number and determine whether it accurately reflects their votes, nor will they be able to remember the number for later verification.

The same technique used to verify that a ballot exists can be used to prevent false attacks on election results. Voters add signatures to their ballots so that they can verify that ballots they created are in fact recorded properly. The voting system can add signatures to ballots to ensure that ballots voters present for verification do in fact represent votes cast. In this case, since the key used to mark ballots valid must remain private, but it should be possible for anyone to verify a ballot, the signature should be based on a public key system.

Completed ballots can be distributed to voters using any printer and verified using digital scanners, the same techniques used today when people print movie tickets or airline boarding passes at home. Such systems encode a number in machine readable form, then validate that number when the ticket or pass is presented. In the voting case, the printed ballot could be verified by a scanner and the results checked by the voter, before the voter left the polling place.

One objection to a system of this type is that the anonymity of voting might be degraded. While the system itself keeps ballots anonymous, voters can reveal votes themselves, raising the prospect of vote selling or intimidation. While this is a legitimate concern, it should be recognized that this prospect exists in any system where monitors do not verify the secrecy of the voting process. Any system that allows people to vote from their homes, for example, allows people to reveal their votes to third parties. Even systems where people cast ballots in carrels then carry them to vote readers allow some amount of vote sharing.

Nowhere in this discussion have I described the security of the voting machines themselves. Instead, the goal has been to make the integrity of the overall system as independent as possible from the integrity of the voting machines. Instead of attempting to verify that a voting machine correctly records a voter's intent, for example, verification occurs externally, using an independent system. Verifiers could, for example, be provided by independent election monitors rather than those in charge of the election.

Is this a complete solution? No. Distribution of secret keys to voting machines for the purposes of signatures is a potential problem. Are there holes? Almost certainly. I've never seen a communication protocol that achieved security without extensive review. A system based on open protocols and public records, however, can get that review. The closed, secretive systems being deployed today cannot.