Secure, Transparent, Auditable, and Reliable Voting

Homomorphic encryption: the picture helps a little

Protecting voting systems against hacking is difficult, and the principal reason is not government incompetence or corruption but the requirement of the secret ballot:

modern elections enshrine privacy at the cost of transparency, and try to compensate for the loss with a host of bureaucratic patches: voter-registration schemes to prevent people from voting twice, tally systems that ensure the number of voters matches the ballot total, and centralized polling places where rival election monitors can scrutinize the proceedings, all to impart legitimacy to a system of vanishing ballots.

“If you want to understand why elections are hard, it's because of the secret ballot,” says [MIT Comp Sci PhD Ben] Adida—that's the single variable “that introduces all of the operational complexity and trust.” Not for nothing did a leading technology conference recently declare voting the “hardest problem in IT security.”

A promising solution lies in homomorphic encryption, related to the same technology that produced bitcoin.

In 1987, [Microsoft cryptographer Josh] Benaloh's thesis at Yale spelled out how a homomorphically encrypted voting scheme would come to life. First, voters would need access to a machine that could perform advanced cryptography. When they cast their ballot, each digital vote would start out as a simple binary—1 for Biden, 0 for Trump—but its ciphertext might be thousands of characters long. Rather than send voters home with a binder full of hexadecimal gibberish, the computer would print the ciphertext as something much smaller: a hash code, much like how a URL is shortened into a Bit.ly. That would serve as the voter's unique receipt, which they would keep and carry away with them.

At the end of the night, when the computers stopped whirring, all those encrypted votes would be added together. A small number of election officials—the county clerk, the secretary of state—would possess a key that allowed them to decrypt the sum. They'd compare the columns of votes for each candidate and reveal the winner.

Thanks to the nature of the math involved, those resulting sums would also be verifiable by independent outside observers. After the election, all the encrypted votes could be posted on a public, online bulletin board for all to inspect. Using a set of mathematical operations called Chaum-Pedersen protocols, auditors would be able to crunch all those ciphertexts to arrive at what cryptographers call a non-interactive zero-knowledge proof: “Proof that the vote is correctly captured,” Benaloh explained, but without any way to know whose ballot said what.

But the thing that excited Benaloh most was what this scheme would mean for individual voters. When a voter left the polling place, clutching a receipt that bore their unique hash code, they could go home and perform a search for its twin among all the encrypted ballots on that massive public bulletin board. For the first time, elections would not only be verifiable, but people could be certain whether their specific vote had been counted, all without violating the secret ballot.

Even if STAR (secure, transparent, auditable, and reliable) machines could be produced, convincing election officials and the general public that they perform according to specifications will require extraordinary wisdom and patience. To non-experts--which are most of us--the mechanism looks like a black box, and everyone knows that black boxes 1) can be hacked and 2) have "back doors" built in by the makers.

Maybe homomorphic encryption will be too hard a sell and we should just go back to the way we used to do it. Yes, elections were stolen back then, but the methods weren't mysterious. And paper voting systems can have STAR qualities, too:

the reliance on paper in key states may strengthen voter confidence this year. Arizona, Florida, Georgia, Michigan, North Carolina, Pennsylvania, Virginia and Wisconsin all have voter-verified paper trails in place for November. This changes the total number of voters using a paper trail to almost 95 percent, according to voting experts. That’s up from 75 percent during the last presidential election.

In two or more weeks the votes will be tabulated. The continuity of the American experiment will depend upon 60 million voters trusting the process even though their candidate lost. Never in the past 160 years has that trust seemed so fragile.