Exporting Democracy II

Okay. So what we want to do is design a voting system, suitable for a large national election, that resists clandestine tampering by an attacker with serious resources (possibly the same people running the election), and at the same time is transparent enough that the voters have confidence in the system. Let's get started! :D

Crowdsourced verification

The core element of the system I'm proposing is a live printed display of cast votes. The votes would be displayed so that you could tell who the vote was for, and include a bit of other data such that the person who cast the ballot could see that it was theirs (a random number or picture shown to them after their ballot is cast would work), but should otherwise be completely anonymous. The votes are printed on the top half of a long roll of paper, which slides by after votes are printed on it. The top half of the paper is under glass, so that people can see it but not mess with it; the bottom half is available for people to write on. They would be allowed to write anything they want - a signature, a message, a random drawing, whatever. People would be encouraged to take pictures of the ballot roll at this stage, and take the pictures home with them. (In poorer countries, where people wouldn't have cameras necessarily, a few digital cameras and printers could be provided there.)

After the election, the vote totals would be counted by other means. The printed record, created solely for recounts and verification, would be made public - either by posting high resolution images of it online, in a country where the vast majority of citizens have internet access, or by posting copies in public places. We now have a very strong method of verification. No part of the ballot record could be modified after the election, because people could be holding photographs of any part of it, allowing people to easily prove electoral fraud. If the computer numbers are questioned, recounts are possible, because a full record of all votes cast is available. Even if the numbers aren't questioned, I fully expect suspicious people to recount some ballots in their own region anyway.

Furthermore, the system so far still preserves the secrecy of individual ballots, assuming closed voting booths. An attacker that wants to target people voting for a certain candidate could monitor the printed votes as they go by, but this is both obvious and imprecise, and can be countered by adding an unpredictable delay of a few minutes before the vote is actually printed. An attacker could also hide tiny cameras in all the voting booths. This is harder to counter, but can be mitigated by making the voting booths closed on all sides, and as spare as possible on the inside. Overall, though, this provides a very robust method of verification.

Voting Machines

With a strong verification system, you could really use any old voting machines for the electronic vote count. Even a Diebold or PES machine might be good enough. On the other hand, having just one layer of security is no fun - let's go ahead and make bulletproof voting machines too.

The TPM is usually understood to be a device to protect copyrights or some nonsense, by preventing tampering with some DRM scheme. This is largely because of a lack of imagination on all sides. There are several very general security problems in computing which a TPM can address. Malicious hardware added by an enemy is difficult to detect, but a TPM can remotely attest to the hardware in a machine. It's nigh-impossible to prevent people from running modified versions of software, so if somebody joins your network with a malicious version of your code, you either have to design a Byzantine fault-tolerant protocol (which is difficult and can be computationally expensive), or give up. A TPM can prevent unsigned software from running, on the other hand, and remotely attest to the software's validity. A TPM can also provide secure storage, through hardware-based encryption. Yes, all of these things can be used to restrict what you can do with a computer, but that's kind of the point.

Let's look at what this gives you in a voting machine.

Initially, you have a set of private keys, which are kept separate from each other and secured individually. Every device used in an election would have its built-in public key signed by all these keys, and hold those signatures. When the machines are networked together for an election, any device can recognize and verify any other device, by requesting its public key and the signatures, along with a remote attestation. (Devices aren't just restricted to the voting machines themselves - you also need to authenticate the printers, for example, or an attacker could use modified ones that print whatever.) In this way you can verify that every device used in an election isn't tampered with in various ways.

Each vote would be recorded, along with the machine it's taken on and the time of day, in a secure encrypted file, and distributed to all the other machines in the polling place. Recording extra data allows for data analysis if the result of the election is called into question (this machine only recorded votes for this candidate? this machine was active during times when the polling place should have been closed? HMM); distributing the results to other machines provides insurance in case of hardware failure. A gossip protocol could be used here, so that putting two machines on the same network would automatically have them exchange votes. This could be applied over a network to automatically send votes to a central location, or if there's no network connectivity, the votes could be sent on a burned CD, or a flash drive, or whatever. Having the votes signed by the individual machines means that transmission over an untrusted medium isn't a problem, as long as they're signed in aggregate and not individually. (Would it be problematic to have every machine store potentially every vote for the whole election? Assume 32 bits for a timestamp, 32 bits for a unique machine ID, and 32 bits for the vote itself - twelve bytes to record a vote. A few hundred million votes would fit comfortably on a large flash drive, even if you add in cryptographic signatures of the votes from each machine.)

Gossip protocols are neat. Let's designate one machine as the master machine; it will collect the final tally. (I say one, but there's no reason it can't be a set of machines, for fault tolerance.) Once it receives all the votes from a given machine through the gossip protocol, it can send back a notification through the same gossip protocol saying "the master machine has received all these votes from X". When X receives that message, it knows that all the votes recorded on it are included in the final tally, and can turn on a light or something to let poll workers know. (I'm assuming, obviously, that all messages are signed and encrypted; it would be extremely silly for them not to be.)

Weaknesses

I think this system is pretty good, but no system is perfect. Even though we have two parallel counts going on which support each other - the documented paper count, and the signed electronic count - I'll count something as a vulnerability even if it could only affect either of these in isolation. After all, sticking vulnerabilities together is easy.

This sort of system is only really useful in places that actually profess to be democratic - if some despot insists on staging an election, but still wants to fake the results, all this system will do is prove what everybody already knows. It'd be nice to put together a system that generates accurate vote totals in the face of open electoral fraud, but I'm far from convinced that that's even possible. Again, if the attacker is sufficiently motivated and doesn't care about appearing democratic, they could just post armed guards inside every voting booth.

Letting people write on the running sheet of votes is important, since it makes the whole sheet significantly harder to later reprint and fake, but it also introduces a vulnerability: vandals could simply destroy the printout, in which case we'd be dependent on the electronic tally. More generally, if somebody wants to wreck the polling place, a strategically-placed bomb could halt voting in a given location. This issue is better addressed by law enforcement.

The electronic security of this system depends on how much you trust your hardware manufacturer, especially the people making the TPM chips. This can be mitigated by purchasing from different manufacturers, making sure that the distribution of hardware between machines is random, and then analyzing the final results for correlations between hardware components and voting patterns. This type of analysis is well-understood in data mining.

It's possible to correlate tapes from security cameras near or inside the polling place with the public vote record, and get a pretty good (but inexact) idea of who voted for whom. Um, this one is tricky. No idea how to mitigate this, if we want to maintain a public aggregate ballot.