Awesome new voting system used in Maryland

I'm something of an election geek. I deeply believe that although democracy sucks (including the slightly-less-sucky Republican variant we use), it sucks less than any other system of government. But to make any Democratic system work there must be a good way to determine the will of the people, and that turns out to be very hard to do.

There are two main parts to the hardness. First supposing you can collect everyone's opinions, how do you put them together to make decisions? We generally use the "plurality rules" system; whichever option gets the largest number of votes wins. That system is full of problems, but that's not the subject of this post.

The other problem is collecting everyone's opinions and doing it accurately. Someone who can manipulate the elections has tremendous power, and there are a LOT of ways of manipulating elections. Stalin famously (and apocryphally) said "Those who cast the votes decide nothing; those who count the votes decide everything," and historically that is the BEST way to manipulate an election. Let the people vote as they will and then either just report whatever result you want or, if you're more subtle, just tweak the counts enough to give the desired outcome.

In the US we've recently gone through a somewhat mind-boggling electoral change by deploying electronic voting machines. I say mind-boggling, because these machines are the PERFECT tool to facilitate large scale, undetectable election fraud, and supposedly we're a country that takes its elections very seriously.

If the idea that electronic voting machines are a bad idea strikes you as surprising, or the view of a Luddite, let me point out that I'm a professional software engineer with a career focus on building extremely high security systems. If you wanted to build a very secure electronic voting system, I'm the kind of person you'd hire to do it -- and I would tell you that it is a TERRIBLE idea. And not just me. A few years ago, as the debate was just starting to heat up, several hundred of the world's top computer security experts collaborated on and signed a paper which basically said the same thing. They explained in detail why computer security technology at present and for the foreseeable future was simply not up to the task. The very best in the world said, in effect, "Not only don't we know how to make such a system secure, we really doubt that it's even possible."

By the way, the system that Utah uses is the worst of the worst.

This debate, however, did provoke a bunch of top-flight cryptographers, mathematicians and computer scientists to start thinking hard about how to design an election system that is secure against fraud. They wanted to build something that cannot be manipulated by the people in power without the populace being able to detect it, and which also preserved the anonymity of voters. It's very easy to build a secure voting scheme if you don't mind revealing who everyone voted for, but that enables vote-buying and coercion.

Some very cool ideas were developed, notably originating from Ron Rivest (who is the "R" in "RSA", for those who know what RSA is) and David Chaum (the creator of some very cool untraceable digital cash schemes). It's probably unfair to mention only their names, because there were many contributors, but they were the main "well-known" researchers involved. The first versions of these ideas were theoretically very cool, but completely impractical. Lots and lots of academic security ideas start out exactly that way.

A few years ago, some of the disparate ideas started to come together, along with some refinements that made them more practical. The result was a system called "Punchscan", which was used to carry out some real-world elections for university student body leadership. It was a good test environment because the stakes were relatively low, but the scale was big enough to make the test realistic. A system that works for a few hundred people is a lot different from one that works for tens of thousands, and once you get to that level it's really not that different to scale it up to millions.

The third-generation successor of Punchscan, called Scantegrity II, was used on Tuesday to carry out the municipal elections in Takoma Park, Maryland. This marks the first time these new ideas in election integrity and verification have been applied to a real government election. And it worked well. The security experts said that electronic voting machines were a bad idea, and now their recommended alternative was used for the first time.

The basic goal of the system is to ensure that it is impossible for ballots to be lost or modified undetectably, and to do it in the context of a practical election that is cost-effective, easy to run and easy for voters to use.

It uses optical-scan ballots, with a small twist. The "bubbles" on the ballot are pre-filled with invisible ink. The voter has a marker that contains the chemical that activates the ink, so swiping the marker across the bubble causes it to be visibly filled -- mostly. When the ink is activated, not only is the bubble-filling ink revealed, but a three-letter code is also revealed. The code is "printed" by the absence of the ink.

A voter who wishes to make sure that his ballot is counted correctly takes a moment while in the voting booth and copies down that three-letter code, as well as the ballot serial number. After election results have been posted, he then goes to the election web site, types in his ballot serial number (which isn't associated anywhere with his identity), and make sure that the codes he copied down are among a small list of codes presented to him. If they are, then he knows his ballot was submitted and tallied as part of the final count.

Now, HOW that code's presence on the web site verifies that the ballot was counted correctly is a little bit complicated, and I'm not even going to try to explain it here. If you want to know, a good starting point is this paper. Also, that code-verification is far from the only thing that has to be done to verify the integrity of the election. Ballots have to be audited before and during the election (audited ballots are not used to cast actual votes), there's a pre-election "code commitment" process that the election officials use, and a post-election "randomized partial checking" system that verifies that the ballots submitted and tallied were actually tallied correctly.

The system allows all of these various integrity verification processes to be carried out by ANY interested parties. It's presumed that the candidates and political parties will take part in them, and that democracy watchdog groups will as well, but any interested person can do it. In fact, the system is designed so that anyone who wants to can easily conduct a personal recount of the entire election, just by downloading the data over the Internet and then running some software on it. The software has to do some complex things, including a lot of fancy math, but the detailed specification for what the software must do is available, along with mathematical proofs demonstrating how it assures integrity, so that anyone with the relevant skills can write their own software to do the verification. Those who don't have the skills to write the software just need to get a program from an organization they trust, and use that.

All of this makes it possible to prove to an arbitrary mathematical probability that the election results were accurate. By "arbitrary mathematical probability" I mean that there is always a possibility that the election was fraudulent and that the fraud was undetected, but for any given margin of error you can decide how much auditing needs to be done to make the probability of fraud as small as you want it to be. The smaller you want to make it, the more auditing is required, but you can achieve any desired level of certainty.

In addition, the Scantegrity system allows for manual recounts of the paper ballots. Manual recounts are actually less reliable than the statistical verification the system uses, but they're an option, unlike with electronic voting systems (including Utah's; no one has ever managed to successfuly recount an election from those paper rolls the machines produce).

This is very cool stuff. Of course it doesn't address issues with registration fairness, fraud, etc., or issues with whether or not plurality voting makes sense, and certainly does nothing to address voter apathy, lying politicians, media influence or any of the many other problems with the political process, but it DOES allow us to have confidence that our votes are counted as cast, which is something that has never been very certain, and which the current generation of voting machines has made very, very questionable.