Big Data/Analytics Zone is brought to you in partnership with:

David Pollack founded Visi.Pro, Cloud Computing for the Rest of Us along with the Visi Language open source project. David founded the Lift Web Framework and continuously contributes to Lift. David has posted 37 posts at DZone. You can read more from them at their website. View Full User Profile

Verifiable Electronic Voting is Easy as Prime

  • submit to reddit

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.

(Side note: Haven't figured out voting by mail yet.)

Published at DZone with permission of its author, David Pollak. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)


Howard Lewis Ship replied on Tue, 2012/11/06 - 5:01pm

It's funny, I also was musing about how to do voting by mail. I don't have an answer for ballot-box stuffing yet, but I do have a secure, reasonably-anonymous way to ensure that your mailed-in ballot makes it to the counting location. See my blog for details.

Jonathan Fisher replied on Wed, 2012/11/07 - 12:09am in response to: Howard Lewis Ship

My coworkers and I were discussing if there's a way to modify this scheme to protect from coercion  Another words, is there a way you can prove your vote was counted correctly without revealing how you voted?

Robert Lauer replied on Thu, 2012/11/08 - 8:51am

Primes as a voting mechanism sounds like a good idea at first, but there is a number of issues.

The greatest problem is secrecy. No one is supposed to keep a record of "your" prime number so you don't face repercussions for voting (people may not deem this very important anymore, however if you read the tweetstorm following Obamas reelection you may think differently about this).

Also, as long as the voting registration issues in the US are not fixed, thinking about nifty voting mechanisms won't help anyone.

Voting is all about trust. Low-tech solutions like paper help a great deal with that.

Jonathan Fisher replied on Thu, 2012/11/08 - 12:33pm

Here's three things the ideal voting system would do:

  1. Allow a voter to see their vote was counted
  2. Disallow a voter to prove how they voted to a third party
  3. Prove no extra votes were added

I don't think you can do #1 and #2 simultaneously without a trusted party involved.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.