End-to-End Verifiable Elections

As of 2018, the clear scientific consensus is that

Elections should be conducted with human-readable paper ballots.  These may be marked by hand or by machine (using a ballot-marking device); they may be counted by hand or by machine (using an optical scanner).  Recounts and audits should be conducted by human inspection of the human-readable portion of the paper ballots. … States should mandate risk-limiting audits [of a statistically valid random sample of the ballots] prior to the certification of election results. With current technology, this requires the use of paper ballots.

Even so, no technology, no methods of election administration, will perfectly assure the accuracy of our elections.  Risk-limiting audits of paper ballots are the best method we know, but as I’ve reminded you recently, fraud can be perpetrated on paper ballots, too.

End-to-end verifiable voting is a quite different way to audit whether election results follow the voters’ choices, in a way that does not require trust in the chain of custody of paper ballots.  E2E-V methods were developed by several computer scientists over the past 35 years or so.

E2E-V allows the voter to trace an individual ballot through the system to make sure it was counted correctly, and allows anyone to see that those ballots were added up correctly.  Much of the technical wizardry of E2E-V is devoted to doing that without compromising the secret ballot.

The secret ballot–to protect the voter from being coerced to vote a certain way–was introduced in the late 19th century in response to severe coercion of voters (by employers, by local political machines) and vote buying.  It’s important that no one should be able to learn how a voter voted, even with her consent (else she can be coerced or bribed).  (Of course, it’s fine to say, “I proudly voted for Candidate X”, but you must not be able to prove it.)

To explain E2E-V, first let’s pretend that we don’t need secret ballots, that every vote is public.  Then it’s easy.  The voter signs her ballot, sends it in, and all ballots are posted in a public, electronic bulletin board–each ballot identified with the name of the voter.  Any voter can check that board, to make sure her vote is listed correctly.  Any member of the public can check that board, to make sure all the votes are added up correctly.  We don’t have to worry about the chain of custody, how the votes were transported and handled on the way to being posted on the public bulletin board.  (We do have to ensure that everyone sees a consistent view of the bulletin board–there are plenty of details to worry about.)

But of course, we need the secret ballot, so real E2E-V systems use cryptographic protocols to probabilistically guarantee that votes are accurately posted on the board, without any individual voter able to prove how she voted.

One modern E2E-V system (StarVote) works like this:  At the polling place, the voter uses a voting terminal (touchscreen or other accessible computerized device) to prepare two pieces of paper:  the ballot and the receipt.

• The ballot lists a human-readable summary of the voter’s choices, and a random (nonsequential) serial number;
• The receipt contains a 20-character code that commits to the voter’s choices and serial number.
• In addition, the voting terminal encrypts the ballot, and stores the encrypted ballot in its memory, linked to the serial number and the code.

What does that mean, “commits”?   The computer has applied a one-way function to the encrypted contents of the ballot, to compute the code.  It’s not possible to calculate the ballot-contents from the code, but it is possible for the voting terminal to prove that the code summarizes the ballot-contents.

Now the voter has a choice:

1. Deposit the ballot into the ballot box and take home the receipt;  or,
2. Make the voting terminal prove it wasn’t cheating, that the code correctly summarizes the ballot; and void (“spoil”) this ballot, and start the process from the beginning, casting a new vote (and still take home the receipt).

I’ll explain this choice below.  For now, suppose the voter chooses (1), cast the ballot and take home the receipt.

When the polls close, all the encrypted ballots are published, along with all the serial numbers in the ballot box.  Using sophisticated cryptographic techniques (e.g., “homomorphic encryption”), it’s possible to add up the votes (just those that correspond to serial numbers of cast ballots) without decrypting the ballots.  That preserves the secret ballot.  Anyone can perform this add-up-the-votes on their own computer, using their own software (if they are a crypto wizard) or using software from a crypto wizard whom they trust.

After the election, the voter can look up her receipt (by its code) in the public bulletin board and make sure it’s present.  But how does she know that the code is an accurate summary of her votes?  If she could check this herself, then she could (therefore) prove to anyone else how she voted; then the secret ballot is lost, and she can be coerced to do this.

So therefore, the voter can only check the correctness of commitment on spoiled ballots that won’t count.  An especially diligent voter may go into the voting booth and flip a coin.  If heads, vote her true preferences and cast the ballot, keeping the receipt (without having a proof that her votes are accurately recorded).  If tails, vote a random ballot and make the voting terminal prove that it recorded her preferences accurately; this voids the ballot, and then she can repeat the process, eventually casting her true ballot.

The point here is that the voting terminal can’t know in advance whether the coin was heads or tails.  If the voting terminal cheats regularly (by recording the votes inaccurately), then eventually (and often enough) it will be caught by a voter taking choice 2.  This works even if only a few voters “challenge” the voting machine by taking choice 2, as long as the voting terminal can’t guess which voters will do it.

Does this actually work?

The mathematics does work:  one-way functions implement checkable commitments (that protect the secret ballot), homomorphic encryption implements adding up the votes (while protecting the secret ballot), cryptographic signatures implement the voting system’s commitment to the public bulletin board, zero-knowledge proofs implement the assurance that the encrypted ballots are well formed.

But does the human interface work?  Can voters understand what is expected of them?  (It’s true, not every voter has to understand, not every voter has to flip that coin; even if only a small proportion of voters exercise option (2) then the voting terminal will be deterred from cheating.)  Can the public understand how to trust the result of an election, based on cryptographic mathematics instead of chain of custody?  And what are the dispute-resolution procedures, in case a voter produces a receipt whose code is not listed on the bulletin board?

These are problems in usability, and the solution is in user studies.  Myself, I am not convinced that E2E-Verifiable voting is understandable enough to voters, to election administrators, to the public.  If people can’t understand something, how can they trust it?  But I do believe it’s worth finding out, by usability studies in real elections, if only that were possible.

E2E-V  +  audits of paper ballots

The good thing about the StarVote proposal is that, in addition to all the E2E-Verifiable crypto, it produces human-readable paper ballots, counted by machine but auditable and recountable by humans.  That is, you can trust the crypto, or you can trust the chain of custody of paper ballot boxes, or both.

Travis County, Texas was prepared to implement StarVote.  The county put out a Request for Proposals (RFP) for manufacturers to produce the equipment, but unfortunately they did not get any acceptable bids.  That’s too bad.  A pilot project like this, with the opportunity to assess the human-interface questions of E2E-Verifiable voting while retaining all the protections of paper ballots, would have been a Good Thing.

In fact, the recent National Academies Study Committee Report recommended:

5.10  State and local jurisdictions should conduct and assess pilots of end-to-end verifiable election systems in elections using paper ballots.