Cryptography Pioneer Seeks Secure Elections the Low-Tech Way

Ronald Rivest sports a white beard, smiles with his eyes and bestows his tech gifts on the people of the world. The Massachusetts Institute of Technology professor is the “R” in RSA, which means that he, along with Adi Shamir (the “S”) and Leonard Adleman (the “A”), gave us one of the first public key cryptosystems. It’s still common today: Nearly all internet-based commercial transactions rely on this algorithm, for which the trio was awarded the 2002 A.M. Turing Award, essentially the Nobel Prize of computing. In recent decades, Rivest has continued to work on making it computationally hard for adversaries to break a system, though he now focuses on ensuring that votes in democratic elections are cast as intended, collected as cast and tallied as collected. Elections, he has discovered, have stricter requirements than nearly any other security application, including internet-based commerce.

Unlike online bank accounts and the customer names with which they are affiliated, ballots in an election must be stripped of voters’ names because of voting’s secrecy requirement. But the ballot box’s anonymity sets conditions for real or perceived tampering, which makes proving the accuracy of tallies important to voters, election officials and candidates. Another requirement is that voters can’t receive receipts verifying their candidate selections, lest the practice encourage vote selling or coercion. But without a receipt, voters might wonder if their votes were faithfully and accurately counted. It’s a tough problem to crack, and Rivest thinks the solution lies not with fancier computers, but with pen, paper and mathematics.

“I mainly argue for some process by which we have confidence in our election results,” he said. “No one should say, ‘It’s right because the computer said so.’”

A decade and a half ago, Rivest designed ThreeBallot, a voter-verifiable method that allows transparent, secure elections that can be openly audited. It’s an example of end-to-end voting methods, which employ cryptography to provide individual voters with receipts that don’t reveal their choices but allow them to verify that their votes were tallied as cast.

Here’s how it works. In a ThreeBallot election, a voter receives three identical ballots with different, random identification numbers. This means every candidate appears three times in total, and a voter fills in two of the three ballots, picking whichever ballots they want and voting for their preferred candidate. Then, counterintuitively, the voter must also fill in one bubble for each of the other, undesired candidates; again, they could use any of the three ballots, even one with a vote for the desired candidate. So on their full ThreeBallot, the desired candidate gets two votes, and every other candidate gets one. Election officials record all three ballots, and the voter retains a copy of one of them as a receipt.

The result, if everyone follows directions, is that every candidate receives one additional vote from every voter. Therefore, to determine final tallies, election officials subtract the total number of voters from the total number of votes for each candidate.

Finally, election officials post the anonymous ballots online, which allows voters to verify that their votes were cast as intended and counted in the tally. To do this, an individual voter looks for their ballot online, identified by its number from the ballot receipt, and makes sure it is unchanged and among the collection of ballots that were counted. The voter’s single ballot receipt isn’t enough to reveal who they actually voted for, and it offers a 1-in-3 chance of detecting manipulation, in the event that the vote was changed. That assurance may sound modest, but when an adversary changes a large number of votes, every one of the altered ballots will also have a 1-in-3 chance of detection by the voter. As a result, the likelihood of detecting fraud increases exponentially with the number of altered ballots — and does so without revealing candidate choices on ballot receipts. Furthermore, since all ballots are posted, any voter may verify the total tally counts and make sure the math is right.

If this all sounds a tad cumbersome and low-tech, it’s because Rivest was more concerned with creating a new system to study, rather than a viable means of counting votes. More recent end-to-end voting schemes involve fancier cryptography and may prove more voter-friendly, but ThreeBallot endures as a pedagogical tool for understanding voting systems that foster integrity at each step in the electoral chain, from voter intent to final tally.

Quanta Magazine recently spoke with Rivest about his research, including his latest work developing k-cuts, a new way to draw a random sample of ballots efficiently. The interview has been condensed and edited for clarity.

What will more secure elections in the U.S. look like?

The transition to more secure voting methods is going in stages. Stage one is converting to paper ballots. This country has done a good job of converting voting situations to paper ballots. Most voters — 80% of them — are voting on paper ballots now. On a paper ballot, a voter can check that the ballot recorded what they want. In stage two, the paper ballots serve as a check of the machine tabulation. An audit may use them to check one or more contests thoroughly across the entire state.

We’re at the beginning stages of states, cities and counties doing some form of audits. In 2020, we may see a lot more.

These audits don’t even have to be too big, since you’ve found that auditing national elections can involve checking less than 1% of paper ballots. What do you say to skeptics who don’t think that’s enough?

I love the metaphor that Philip Stark — a statistician at Berkeley — uses. He’s the inventor and promulgator of risk-limiting audits. He says that if you want to test if a big pot of soup is too salty, you don’t need to test all of the soup to see if it’s salty everywhere. Instead, you stir it up nicely, take a spoonful, and see if that spoonful is too salty. We’re talking about something similar. If the sample you take is representative of the whole population, then it suffices.

What are some of the drawbacks of different forms of verifiable voting?

With paper ballots plus postelection statistical audits, the voters cast votes on paper and the machine counts them. Then, to audit them, you do statistical sampling on the scanned and tabulated paper ballots and some math on a random sample to see if the results are likely to be right. That’s the near-term approach we should take for most elections today, especially as it works with ballots voters know. But there are issues. For example, is there time to squeeze in the audit between the tabulation and the result?

End-to-end verifiable voting, like what ThreeBallot represents, is an alternative. With this approach, a voter submits not just an ordinary ballot, but an encrypted ballot. It works, but there’s some unfamiliar technology in the casting process that would have to be explained to the voter. After you cast your ballot, you get an encrypted receipt. Taking home and using that receipt is a new step.

ThreeBallot has usability issues in practice. Are there other end-to-end verifiable voting methods?

David Chaum was the main innovator of a method called Scantegrity II. [Rivest co-authored this research.] You fill out your oval with a special pen. You vote as usual by filling in ovals. However, when you darken an oval, a number appears. The embedded numbers are not sequential and are different for every candidate and on every ballot. You can write down your ballot number and the numbers that appear as your receipt, which doesn’t reveal how you voted. Then you look online later and verify, for example, that on ballot 3454605, the bubbles corresponding to numbers 327, 567 and so on were recorded properly. There’s no table anywhere that says 327 is a vote for so-and-so. It looks and feels a lot like ordinary voting. We ran a trial in Takoma Park, Maryland, that went well.

It sounds as though, ultimately, end-to-end verified voting is a kind of “audit by the masses”?

Sure. That’s a new term.

I just made it up!

There are three things you want for a system that’s checkable all the way through.

Step one is checking that a vote was cast as intended. In the case of a traditional paper ballot, you complete the ballot and see that you’re marking the right oval.

Step two is ensuring that votes are collected as cast. In a typical paper ballot scheme, you put the ballot into a machine and then simply trust election officials to collect and tabulate the ballots. With an end-to-end scheme, you check that the receipt of your encrypted ballot is the same as what’s on the website of encrypted ballots. That’s an audit by the masses, if you like.

The final step is to verify that the tally for the entire set of encrypted ballots gives the right answer. With end-to-end voting, voters have a process for checking the tabulations on the website.

ThreeBallot and Scantegrity offer models for end-to-end verified voting, but where’s the cryptography?

In ThreeBallot, the copy of one of the three ballots that the voter takes home is an encryption of the cast vote. On a Scantegrity ballot, the copy of the light-colored, three-digit number that appears after a voter marks an oval next to a preferred candidate is also an encryption of the cast vote that the voter takes home. These are low-tech ways of encrypting the voter’s choices.

Then what does the cryptographic part typically look like, if it’s not this low-tech approach?

Other voting schemes use more complicated mathematics. For example, a ballot might be turned into a long number with fields for each contest and candidate, processed by one of the well-known public key encryption schemes to become a voter’s cipher text, and then later appear on the website for verification. It’s a challenge to describe to the typical voter.

One can reasonably ask if the technology and voting schemes that support a democracy should be understandable by everybody. That would rule out the use of cryptography. You could instead have paper ballots that are hand counted everywhere. People can run a democracy however they want as long as they’re getting the right answers. As a technologist, I’m exploring mathematical alternatives.

Do you see election integrity as a problem to be solved, just like a math or computer science problem?

Voting is a complicated political process to be improved, more than a problem to be solved. But you can formalize pieces you might improve if you use math. For example, there’s the question of how you sample from a collection of paper ballots. If I give you 10,000 ballots and ask you to draw 200 at random, how do you do that well and efficiently?