December 9, 2021

Archives for November 2018

Two cheers for limited democracy in New Jersey

When I voted last week in Princeton, New Jersey, here were the choices I faced, all on one “page”:

I had to vote in 7 contests, total: for Senator, Congress(wo)man, County board, County board unexpired term, City council, Statewide referendum, School board.  Put another way, I had to select 13 choices out of 27 options (not counting write-in options).  The ballot is so short because: New Jersey elects its governor and legislature in odd-numbered years, does not have initiative-and-referendum by petition, does not elect judges.

In contrast, a voter in Los Angeles was given a 76-page packet, in which the 9-page ballot contained optical-scan bubbles to fill in.  The voter had to select 55 choices out of 229 options.

The founders of our democracy designed a Constitution in which (at the Federal level) voters elect representatives and executives who pass legislation, nominate and confirm judges, and so on.  That is, we have limited democracy, in the sense that it is representative.  But some States, especially California, ask voters to decide legislative questions (“propositions”) and elect judges.  Political scientists and informed citizens debate whether that’s a good idea.

Here I’ll consider a particular aspect of that constitutional difference:  Auditability of elections.  It is a clear scientific consensus, and it is becoming a consensus among the citizenry and the States, that we should vote with paper ballots that are recountable by human inspection, and we should have random audits by human inspection of (a random sample of) those paper ballots, just to make sure the voting machines are not malfunctioning or cheating.

Random audits take time, effort, and money–not an enormous cost, but not trivial either.  The cost and difficulty of risk-limiting audits surely increases as the number of contests on the ballot increases.  Auditing New Jersey’s 7 contests (more or less, in different towns) will not be very difficult.  Auditing Los Angeles’s 52 contests will be quite a chore.  Surely that’s one argument for keeping the ballot short.

In practice, risk-limiting audits of California elections are likely to be done in such a way that Federal, statewide, and countywide contests are checked to a specified risk limit (perhaps 5%), but on all ballots examined, all contests are audited.  That will audit many more contests to a risk limit that is not predetermined, and may or may not be small, but will at least be reported as a result of the audit.  In that manner, even LA’s long ballot can be audited.

Why only “two cheers” for New Jersey?  Well, in New Jersey we have “limited democracy” in a different form as well:  we use paperless direct-recording electronic (DRE) voting machines.  The computers in those machine get to decide what to report about the buttons we pressed, and there are no paper ballots to recount.  We have delegated our representation to whomever was the last to install a computer program in those machines, whether legimitately or illegitimately.  Surely that’s not what the founders intended by “representative democracy.”



When the optical scanners jam up, what then?

In the November 2018 election, many optical-scan voting machines in New York experienced problems with paper jams, caused by the rainy weather and excessive humidity.

Also, this was the first time New York used a 2-page ballot that the voter had to separate at the perforations.  This doubled the number of sheets of paper that the optical scanners had to process.

These two factors caused long lines, and voter frustration, at some polling places.  At some polling places, there were not adequate “emergency ballot boxes” for deposit of not-yet-scanned paper ballots.

New York, like many other states, uses a robust, trustworthy, and reliable means of balloting:  optical-scan paper ballots, hand-marked by the voters (except for those voters who choose to use a ballot-marking device), which the voter deposits directly into an optical scanner.  That is, “precinct-count optical scan” (PCOS).

No voting method is perfect, but PCOS is less imperfect than other methods.  Here are some important principles of precinct-count optical scan:

  1. Feedback: if the voter inadvertently overvotes the ballot (marks too many bubbles in the same contest), the scanner can alert the voter to this problem, giving the voter the chance to correct it by filling in a fresh ballot.
  2. Immediate count:  vote totals are reported as soon as the polls close.  Unofficial (but informative) precinct totals can be reported immediately to the county, to the news media, and to members of the public present at the polling place.  Also, there’s at least one count of the votes before any transportation or handling of ballot boxes.  The paper ballots are legally the ballot of record for recounts, with random audits of paper ballots necessary to detect and deter cheating via hacking of optical scanner software.  But if there is interference with the paper ballots in the chain of custody between the precinct and the audit or recount, the in-the-precinct totals are at least evidence that an investigator or court of law might find useful.
  3. Robustness:  if the power fails, or the optical scanner fails for some other reason, voters can still hand-mark their optical-scan ballots, and deposit them into a ballot box for later counting.

You might notice that “deposit into a ballot box for later counting“ conflicts with ”feedback” and “immediate count.”  What should we do about that?

[Read more…]

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.