Let’s be honest: The 2016 election wasn’t a sterling display of American democracy. Its problems extended beyond Russian hackers and trolls trying to thumb the scale, and the winner’s baseless, ongoing claims of voter fraud. For computer scientist Ben Adida, the most troubling part came afterward, when voting security experts and Green Party candidate Jill Stein called for a recount of the vote in three thin-margin swing states, raised millions of dollars to do it—and still mostly failed.
While Stein successfully triggered a Wisconsin recount, federal judges in Pennsylvania and Michigan put an early stop to her efforts. In the latter case, a judge ruled that Stein had “not presented evidence of tampering or mistake” in the electronic voting machines. It was a vexing catch-22, says Adida, an engineer and applied cryptographer at the education startup Clever. If the Michigan vote was tainted, the paper backup ballots Stein wanted to recount were the evidence that could prove it. But Stein didn’t have any evidence to justify looking at the evidence.
“Recounts don’t actually happen, because if you can’t bring a shred of evidence to the table that something went wrong, you sound like a lunatic,” Adida says. “That’s what 2016 proves. We need to build a voting system that inherently provides that evidence in case something goes wrong.”
Encrypt the Vote
At the Enigma security conference next week in Oakland, Adida will make the case for a decade-old voting system that provides that inherent evidence, what Adida and other voting security experts call “end-to-end verification.” Since 2007, thousands of people, including organizations like the Association of Computing Machinery and Greenpeace, have used Adida’s election software, called Helios to solve that core problem. Helios encrypts every vote, and then publishes an online list of encrypted results by voter in a form that allows anyone from an election-monitoring organization to individual voters themselves to check the results.
“The whole idea that paper ballots are going to save us is well-intentioned but flawed,” says Adida. “I think we can do better. We can provide true end-to-end proof that an election works.”
Now that same system will be put into practice for the first time in actual government: A voting scheme, known as STAR-Vote—for Secure, Transparent, Auditable, and Reliable—uses a similar cryptographic system to Helios, but with real, physical voting machines and ballots. One Texas county is even set to implement it before the 2020 presidential election.
“STAR-Vote allows the general public to verify the vote themselves,” says Dana DeBeauvoir, the county clerk of Travis County, Texas, which includes the city of Austin. “We’re trying to build a better mousetrap and share it with everyone else.”
How It Works
Here’s the clever—and somewhat convoluted—way that end-to-end verified voting system works: Registered voters input their vote on a touchscreen machine. When they’re done, the machine prints their ballot with their choices, along with a “receipt” at the bottom that they can take home. That input machine also encrypts the results, shares the encrypted vote data with all the other voting machines at the polling place, and also enters it into a database of all the encrypted votes that will be published online at the end of the election day. Then voters feed their printed ballot into a ballot box with a scanner that reads a barcode on the ballot and confirms to the network that the vote has been cast.
After the votes are published, anyone can use a tracking number on their receipt to look up their vote online and confirm that it was registered. But crucially, no one can see who voted for whom. Not even the voter can decrypt their own vote; if they could prove who they voted for, they might be coerced or paid to vote for a certain candidate.
In fact, thanks to some mathematical sleight-of-hand known as “homomorphic encryption,” not even the election officials counting up the results can decrypt any individual votes. Homomorphic encryption allows simple arithmetic to be performed on encrypted data without decrypting it. So the encrypted votes can be added up and published online to produce an encrypted, public total tally that remains accurate without ever exposing anyone’s vote. Election officials decrypt only that final result, and even they can only do so when a certain number of overseers combine their secret passwords. After the results are decrypted and declared, anyone can re-encrypt them to check that they match the online encrypted tally, to prevent the officials from colluding to falsify the count.
That somewhat mind-bending process still leaves another question: How can voters check that the STAR-Vote machine not only registered their encrypted vote, but registered the correct vote rather than slyly switching it? To solve that problem, the system offers voters one more feature it calls a “challenge.” When the vote is encrypted and declared to the other voting machines—but before the voter scans it and puts it in the ballot box—the voter can choose to challenge it instead of confirming it, essentially declaring the ballot to have been a test of the system. If a ballot is challenged, it’s not counted, and the machine where the voter input their choice uses a special key that only it possesses to decrypt the encrypted vote it just declared to reveal who that challenged vote was for; it’s then shared with the local network and the public database. (The voter, meanwhile, starts over and votes again.)
Before the voter has even left the voting place you have all the information you need to catch the machine cheating. Dan Wallach, STAR-Vote Inventor
Thanks to some proven cryptographic math, there’s no way for the computer to believably decrypt the ballot without revealing which candidate it was about to register a vote for. So if the machine’s answer in the public database doesn’t match the voter’s choices, the voter can look up the challenged vote, spot the mismatch and report the machine’s fraudulent behavior. That makes any attempt at tampering with voting machines highly risky. “Before the voter has even left the voting place you have all the information you need to catch the machine cheating in its electronic representation of your ballot,” says Dan Wallach, a cryptographer at Rice University and one of STAR-Vote’s inventors.
Baking in the Evidence
All of those cryptographic checks aren’t meant to replace paper ballot backups, Wallach and Adida say, which would still serve as the ultimate record in any recount. But with STAR-Vote, the hints of tampering that trigger that recount would be far easier to spot. And just as importantly, says Travis County Clerk Dana Debeauvoir, all that cryptographic complexity remains hidden from any voter that doesn’t want to deal with it. “It has to be something that mom and pop can operate,” she says.
Next month, Travis County, which has about 720,000 registered voters, will reveal the results of a request-for-proposal it issued last year for tech firms to code and build its STAR-Vote machines. Debeauvoir hopes to put the system to use for the first time in local elections in 2019, so that any bugs will be worked out before the 2020 presidential election. She says she expects the system to cost between $8 and $12 million to develop, but argues that’s still less in the long run than licensing the currently available, less-verifiable systems.
Supporters hope that if it catches on, STAR-Vote could serve as a key reassurance for the American electoral system, and save millions of dollars spent on wasted paper recounts. Rather than lawsuits, sore loser accusations, and expensive audits, the audit would be baked into the system, says Adida. “Instead of having to seek the evidence, the system would provide evidence of correct operation by virtue of the process of voting itself,” says Adida. Imagined voter fraud and Russian trolls aside, that might actually be a system all Americans can trust.