Verifiable Electronic Voting, Easy as Prime November 6, 2012
Verifiable Electronic Voting is Easy
Last night Hilary Mason posted about some "software upgrades to e-voting machines" in Ohio.
That set me off thinking about how we could have verifiable e-voting machines. What I mean by verifiable is that I can test if my vote was counted.
In its Prime
I realized that there's a very simple way to do this.
Each voter is assigned a unique prime number. It's not difficult to generate unique (where unique means 1:2^100 against having two of the same number) prime numbers.
Possible votes will be put in a 2 dimensional matrix of issue/candidate and possible votes. The matrix will be initialized to 1 for valid votes (e.g., Obama for President, Yes or No for Proposition 37) and 0 for invalid votes (e.g., Obama for Proposition 37).
Each vote that the I cast will multiply the current value of the vote cell by my unique prime number.
I will be issued a receipt for my vote which contains: the base 16 text of the SHA-1 hash of my prime number and a 2d barcode of my prime number.
The voting machines will then produce a list of prime numbers with an issuance timestamp and vote matrix and communicate that the the voting authority (e.g., the Secretary of State).
The voting authority will consolidate all the vote matrixes by multiplying the value is each cell and by concatenating the list of primes/timestamps. The voting authority will publish this information, grouping primes by some subset of the total (polling place, district, etc.)
The voting authority will determine the number of votes for each element in the vote matrix by counting the number of primes that will divide into each cell in the vote matrix.
I can verify that my vote was counted if my prime is in the list and if my prime divides into the value in the vote matrix that represents the vote that I cast. This verification can be done locally so my prime is never submitted to another entity (folks can't figure out how I voted). The prime can be recovered from my voting receipt via my phone's camera. For those who don't have a smart-phone, they can type in the hash into a browser, determine their prime based on the list of primes and how they hash, and then check on the votes.
Ballot box stuffing
The above system allows me to determine if my vote was counted. This is important.
But it's also important to insure that there were not extra ballots cast… basically insure that there were not extra votes generated by the voting machines themselves.
That's where the publishing of the primes, timestamps and some geographical grouping comes in. Basically, over the course of elections, it will be possible to see trends and anomalies related to voting density and voting times. This means that if there are 20 votes cast in a 5 minute period in the middle of the day in a polling place with light turnout, the will be some statistical way to identify that as an anomaly.
But having the data in the open means that everyone will be able to review it and look for likely fraudulent patterns.
Voting by mail
Haven't figured that out yet.