« September 2004 | Main | November 2004 »

October 31, 2004

Pumkin Pi Anyone?

pumpkin-pi.jpg
Happy Halloween!

Tinfoil Beanie by Dan | Permalink | Comments (1)

Electronic Voting: reiterating the obvious

We’re heading into our first presidential election with widespread use of electronic voting machines. This has been filled with controversy, both because they haven’t been deployed as widely as some wanted and because many feel that they can’t be trusted as far as Kerry can throw a Silver Star. The irony isn’t that we couldn’t work out this problem in the four years since 2000. The irony is that the solution was obvious, widely known, and largely ignored.

One of the reasons the new electronic voting machines haven’t been rolled out to that many places was money. They are, after all, not free, but there was enough popular support for some kind of improvement that the money would have been there at the federal level. Around 2000, I’d heard numbers of two to four billion dollars being talked about to revamp the voting system nationwide. That would have made a budget of a few thousand dollars per voting machine and still had enough for a massive nationwide rollout. So, I can’t really blame the problem on money.

Instead, it’s about certification, and that’s about trust. While federal dollars could have paid for it, the running of the actual election, i.e. the physical process of taking the votes and processing the ballots, is largely a matter of state law. Thus, it was up to each state to certify any electronic voting machine prior to use. This seemed to be going all right until it was pointed out by some techies that the process was insecure and ripe for tampering. I happen to agree with them, and I am a techie. (A long standing irony is that it’s the folks who understand the technology the most, trust it the least – because they know how fragile it is.)

Why aren’t the machines trusted? Why are they so insecure? After all, the guys who did this are professionals. Some had industry experience in making ATM’s, an area where security literally means dollars. I can only explain it as a mixture of stupidity and laziness, because it would seem that the answer to the security problem is obvious. Of course, I also blame the federal and state governments. The solution should have been obvious to them as well, and they (particularly the fed’s) should have put out a specification, a set of requirements, for any electronic voting system, and those requirements should have ensured a high level of trust. But they didn’t. Instead, they just got out the checkbook and asked what was available.

So, what is the obvious solution? I’ve been keeping you in suspense this long, but you won’t be surprised. After all, it is the obvious solution: paper backups. That’s right, annoying, troublesome, chad-hanging paper. However, this inclusion of paper seems to be an anathema to the electronic voting companies – a surprise given that ATM’s have to produce paper receipts and have done so for over twenty years. Some even say that paper is an invitation to even more fraud, but I just don’t see it. Paper is much harder to forge than bits. It’s physical, and it’s spread out in a lot of places.

So here’s Dan’s fraud-resistant voting system. I’d say fraud-proof, but I can’t be certain. Still, it’s pretty good.

Step 1: Voter steps into the booth. She votes on the electronic screen, using some input device, i.e. touch-screen, wheel, mouse, keyboard, etc.

Step 2: Machine prints a receipt (image below). The user looks at the receipt and the screen and confirms that they match. If there’s a problem, or if she just changed her mind, she can call over the polling official who will enter a code to reset the machine and also destroy the receipt – then go back to step 1.

Step 3: Once the voter is satisfied that the machine and the receipt are in agreement, she hits enter on the machine and puts her receipt into the traditional, locked ballot box.

Step 4: At the end of the day, the votes are uploaded from the machines, moving up the precinct chain to the county and state levels where winners are determined promptly.

Step 5: The day after the election, the paper receipts are tallied by electronic readers (details below). This happens for every election, not just if it’s close, not just if someone asks for a recount. It happens no matter what. If there was massive fraud on the purely electronic version, it will show up immediately.

Step 6: A small percentage of paper receipts are chosen at random to be inspected by hand to make sure that the electronic readers are reading them accurately. If there was massive and matching fraud on the readers, it should show up in this manual inspection.

Step 7: Any major or minor discrepancies between electronic and paper totals can be investigated to look for either fraud or simple mechanical, electronic, or systemic failure.

Step 8: Once any discrepancies have been cleared up or declared trivial, the appropriate state or county official will certify the election results. This is a process that occurs even now, and it’s this action that makes the results official, not the initial reports on election night.

Since I’m asking you for so much faith in this piece of paper, let’s look at it:

eballot.gif

First of all, note that it is in all-caps optical-character-recognition (OCR) font. Given the redundancy noted below, reading this should be very reliable, or at least, it will be highly unlikely for an error to slip through.

It should be printed on either common 8.5 x 11 paper or a common roll-paper. The idea is that if a machine runs out of paper due to heavy turnout, polling officials should be able to purchase replacement at any office supply store.

The top line records the information necessary to track the vote down to the precinct polling station and the individual machine. Thus, any cross checks between paper and electronic can track it down to a specific place and device.

The second line uniquely identifies the individual vote cast by both a number and a time stamp. Those two should proceed forward in tandem.

Next comes the votes themselves, and each vote comes in four columns, which are actually redundant pairs. The first two columns identify the choice being made, both by number on the ballot and by human-readable name. If they don’t match, something is amiss. The second two columns are the choice made, both by number on the ballot and by human-readable name. Again, if they don’t match, something is amiss.

At the bottom is a long string of hexadecimal numbers. This is a digital signature of the vote that was cast. Specifically, it is a signature of the text above it on the receipt, signed with a key that is unique to that voting machine. If the signature is wrong, then something is amiss. In addition to authenticating the paper receipt, this should act as an excellent error detection code.

Combine all of those paper features in the error checking, and discrepancies should be easy to spot and easy to track down. If there is a major discrepancy between the paper and the electronic version, enough to swing the election, then the paper must take precedence. It is harder to forge since it contains both the physical properties (physical existence, paper consistency, printing characteristics, etc.) and the mathematical properties (record of unique instance, digital signature, etc.) that make things hard to forge. And of course, if the computers do become suspect, the paper versions contain enough information to be counted by hand by human beings who are readily accountable to laws governing election fraud.

But ultimately, the best part of the error detection occurs back at step 2, when the voter confirms that the paper vote represents what she voted for electronically. You’ll have about 110 million motivated fact-checkers making sure that the system is working correctly. Everything after that is just to make sure that error-check is honored.

The ironic, nay, the sad part of all this is that I banged out the specifics here in about ninety minutes. A good team of ten or twenty technical folks could work out the software and hardware in a year. But here we sit, almost four years after the fiasco of Florida 2000, and to my knowledge, none of the electronic voting systems are as resistant to fraud or error as the one I’ve just described. I may be smart, but come on guys, I’m not that smart.

Politics /Technology by Dan | Permalink | Comments (3)

Meandering Miscellany

Just wrapping up a few miscellanous bits into an entry.