« home

Election Mania and Crypto

10 November 2016

Weeell. Here we are. Frankly, I’m still in shock - so many things had to go wrong to get us where we are now. I’m mostly afraid for our environment, and if you are too, maybe check out Protect Our Winters. In any case, I’ll avoid making this too political a post and focus on crypto.

Goals

I’ve been toying with this idea for some time now. Voting systems that exploit homomorphic encryption have been discussed and proposed, but have not come to fruition, for various reasons. Here, I’ll propose a system that relies only on existing schemes - probably the best implementation would be a minimal wrapper around nacl.

First, let’s identify our goals. A crypto-voting system must:

  1. Be verifiable - you should be able to see your own vote.
  2. Be auditable - anyone should be able to tally up the results of the election.
  3. Be secure - it must not leak anyone’s vote to anyone else.
  4. Be genuine - it should be cryptographically impossible to commit voter fraud.
  5. Be tamper-proof - it must be impossible to forge results from the inside.

Mechanism

The gist is this: voters input their voter ID number and social security number - that should be enough to uniquely identify a person. Those two inputs are encrypted (call the encryption E) for their county’s public key and an ephemeral secret key, and paired with your vote (call it v). The voter is given a receipt with a printout of E. The (E, v) pair passes through the county board of elections for verification, and upon verification is posted to a public blockchain.

From the voter’s perspective

When the voter goes home, they can search the blockchain for E and see that 1) it is there at all, and 2) that it’s paired with the proper vote. So we’ve satisfied verifiability. Since the votes are all in plaintext, the voter can tally up every vote and obtain an election result, which they can compare against the official announcement. So the system is auditable. And given a strong enough cipher, the system is as secure as the cipher.

From the government’s perspective

The government can fairly easily guarantee that the election is genuine. When an (E, v) pair is cast and comes to the county board of elections, the incoming E is automatically decrypted. Then, the board can verify that 1) it exists in their voter registration database, and 2) they have not received a prior vote with that information. If the incoming E passes those checks, the (E, v) pair is passed on to the blockchain - if not, the vote is thrown out. So the system is genuine. And so long as the counties can protect their secret keys, the whole process is automated, so it would be very difficult to tamper with from the inside. And furthermore, since voters can verify their votes, any tampering would be immediately detected.

Potential weaknesses

The first possibility that springs to mind is that it’s possible to register more than once. There are a couple ways to combat this, I think. First, fix voter registration systems! They’re broken and designed for suppression as-is, so implementing this kind of system would be a great time to audit and fix our existing voter registration infrastructure. The second way is to have the federal government decrypt the entire, supposedly “final” blockchain, either by having each E be encrypted for both a county and federal public key, or by having the federal government collect each county’s private key. It is then possible to check, for example, that no social security number exists more than once with different registration numbers.

Another possibility is that of a DDOS attack on the counties that verify E’s before passing votes on to the blockchain. This, I think, can be solved with enough engineering: strong hosting infrastructure combined with extremely harsh IP blocking should do the trick. This introduces (or perhaps exposes) another problem: what happens if someone doesn’t have access to a computer, or if their IP is mistakenly blocked? Easy: just host computers at existing polling locations. That way, people can either vote from home via a website or an app, or they can vote from polling locations.

Crypto

I think the best candidate for the actual cryptograhy is nacl’s box construct, with an ephemeral private key used for encryption. There’s precedent for this in keybase’s saltpack protocol, and has a number of advantages:

So I think it’s the right choice. But honestly, as long as we are comfortable with the assumptions going into the cipher, it doesn’t really matter what cryptosystem we use. I’d love to hear other suggestions!

Scope & Discussion

This proposal doesn’t fix structural problems with the US presidential election, such as the continued existence of the electoral college, gerrymandering, and voter suppression. But it does provide the capacity for such solutions: for example, this system could easily be adapted to be a pure, federal, popular vote - no more counties and districts, no more electoral college. And most importantly, regardless of those problems, it eliminates the possibility of election-rigging and gives us a way to alleviate the stress of elections (poll lines, absentee voting, manual counting, etc).

There are also some philosophical questions at play here. For example, unlike a system using homomorphic encryption, the government can know who individuals voted for. In my mind, this is a problem only if the keys fall into the hands of the candidates - there are, in fact, politically neutral parties within the government who can be trusted with the keys. Suggestions for improvements in this regard would be very welcome!