Archives for 2018

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…]

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.

In my previous article, I discussed 10 ways that voting machines could cheat, in ballot-marking, ballot-scanning, and ballot tabulating; and I discussed which of these cheats could be caught and corrected during risk-limiting audits and recounts of the paper ballots.  In particular, cheat-methods 1, 2, 5, and 7 will be detected/corrected by audits/recounts; methods 3,4,6,8,9,10 will likely not be detected/corrected.  Therefore I argued for hand-marked optical-scan ballots (which can’t be cheated by methods 3,4,6,8,9,10).

Now let me discuss cheat methods 11 and 12:

How to cheat, method 11:  Hack the software that is used in the audit/recount process to make it cheat.

Solution 1:  Don’t use computers in the audit/recount process.  This solution is extreme and, for some audit methods, impractical.  For example, we may have print a spreadsheet listing the “manifest” of ballot-batches, how many ballots are in each batch; we may use a spreadsheet to record and sum the tallies of our audit or recount.  How much of a nontrivial “business method” such as an audit, can we really run entirely without computers?

Solution 2:  Use computers during the audit/recount, but in a limited, software-independent way.  That means, any time a computer program is used in some part of the process, the inputs, algorithm, and outputs of that program should be public and transparent.  Any member of the public should be able to recalculate the results of the program, independently.  For example, if a spreadsheet is used to sum up the vote totals in the precincts, print out the spreadsheet, and anyone can add it up themselves using a pencil, a mechanical calculator, or their own computer with their own computer program.  (In the June 2018 risk-limiting (ballot polling) audit performed in Orange County, CA, audit teams-of-four entered all their observations onto paper spreadsheet forms, for tabulation by computer but which could be independently tallied by anyone.)

How to cheat, method 12:  Steal the entire ballot box and replace the paper ballots with fraudulent ballots marked differently.  Or just ignore the paper ballots entirely.

This used to happen on a regular basis.  In Duval County Texas, 1948, “Parr was the Godfather.  He had life-or-death control.  We could tell any election judge, `give us 80 percent of the vote and the other guy 20 percent.'” [Campbell, Deliver the Vote, 2005, p. 224]  That is, in some counties, the party bosses who controlled the polling places and ballot boxes would just report whatever counts they wanted, regardless of the ballots. [See also: Robert Caro, Means of Ascent, 1991, Chapter 13]  In the 19th and early 20th century, insider election fraud was widespread in the U.S. [Saltman, The History and Politics of Voting Technology, 2006]

Solution 1:  Pollwatchers from both (or all) political parties present at the polls and during the vote counting, as witnesses.  Definitely a good idea.  But it wouldn’t have worked in Duval County 1948, or Jersey City 1968, where physical intimidation kept the opposition party away; and where the most important elections were primary elections, not general elections.

Solution 2:  Supervision of elections by the State government, or by the Federal government, or indictments by Federal prosecutors, to restore democracy to the process.  In 1870-76, there averaged ten indictments per week nationwide for election fraud.

Solution 3:  Professionalization.  Over the past 150 years, as election administration has developed into a profession with best practices, standards, codes of ethics, and so on, we could hope that gross frauds (with everyone “in the know”) would no longer be tolerated.

Solution 4:  Shorten the “chain of custody” of the ballot box to an absolute minimum.  Immediately after the polls close, in the presence of witnesses, open the ballot box, count the ballots by hand, and make the results known.  The ballot box, and the ballots, are never out of sight of the witnesses.   (This is standard procedure in many countries that use hand-counted paper ballots–but in those countries, hand counting works well because there’s only one contest on each ballot.)

How to cheat, method 13:  While working in a recount (or audit) of paper ballots, hide a bit of pencil lead under your fingernail.  Surreptitiously mark overvotes on ballots marked for the candidate you don’t like.  (A traditional American method.)

What this all illustrates is that paper ballots with audits and recounts, by themselves, are not a panacea.  They need careful and transparent chain-of-custody procedures, and some basic degree of honesty and civic trust.

Solution 5:  Precinct-count optical scan.  Votes are recorded and tabulated by the voting machine immediately as they are cast; paper ballots are saved in a sealed ballot box for later audit or recount.   In case of disagreement, the paper ballots are considered the official ballot of record.  But still, the disagreement, all by itself, is strong evidence that something went wrong: either the machines are cheating, or the machines are miscalibrated, or the paper ballots were altered.  The election fraudster will find it more difficult to make fraudulent paper ballots that exactly match a fraudulent voting machine’s report, than to hack just the voting machine or just the paper ballots.  Although the paper ballots are the default ballot of record, serious discrepancies can lead to investigations.  Once it ends up in court, the judge can hear evidence; perhaps there will be reason to rule that the machine counts are trustworthy where the paper ballots are not.

Notice that central-count optical scan, where the paper ballots go through a nontrivial chain of custody before the first time they are scanned, does not permit Solution 5.

All the solutions I described here take the form, we can never fully trust that the computerized voting machines haven’t been hacked to cheat, so we must have trustworthy human processes to make sure that the paper ballots, marked by the voter, are preserved unaltered and recounted accurately.  But what if there were a way to audit and trust the election results, independent of trusting the very human process of recounting paper ballots?

Solution 6:  End-to-end-verifiable voting.  In a future article I’ll discuss E2E-verifiable, methods by which each voter can trace his or her own ballot through the process to gain assurance that has been recorded and counted correctly.   Perhaps some of these methods can increase the assurance and efficiency of our elections, especially those E2E-V methods that use paper ballots that can also be audited using random audits by human inspection, providing belt-and-suspenders assurance.