How you can conduct a voter-verifiable election online, right now

Cryptographers around the world have come up with new theories about how to improve elections.

By Cyrus Farivar
Published October 23, 2008 6:00PM (EDT)

I'm sorry, but if you're secretary of state in, let's say, West Virginia, and you have to state publicly (as was the case yesterday) that there are no problems with your electronic voting machines, that makes me all the more suspicious. And that's aside from the fact that I'm suspicious of electronic voting in general, at least in this country. (That said, I've been extremely impressed by the online voting system used in Estonia -- but that system couldn't work in the U.S. for reasons I won't get into here.)

One of the basic problems of voting technology, whether electronic or not, is that there's no real way for anyone to verify that their vote was counted properly. Regardless of whether I push a button on a screen, or I drop my paper in a ballot box, I'm essentially taking it on faith that my vote was recorded and tallied accurately. Even if voter monitoring groups had people in every precinct, it still wouldn't be possible.

However, I'm here to tell you that there's a new trend in voting technology that you're going to start hearing a lot more about -- it's called end-to-end voter verifiability.

The premise is mind-bogglingly counterintuitive: to be able to be sure, with a high level of certainty, that your vote was recorded and counted accurately without revealing whom you voted for. And that you (yes, you) can verify that this happened exactly as it should have.

One of the strange things about E2E verifiable voting is that it involves cryptography -- usually something used to keep things more secret -- as a tool to make voting more open and more secure. (Weird, I know.)

Up until a couple of months ago, I'd never heard of voter verifiability. But I got an assignment from Communications of the ACM -- a famous computer science journal trying to refashion itself as a popular magazine -- to write about it. (You can read my article in the October 2008 issue, here.)

After spending a lot of time on the phone, on e-mail, over Skype and even some good old-fashioned in-person interviews with various people in this field, I started learning about E2E voter verifiable systems from people scattered across the country (and some  overseas). It took me a long time to finally understand it, and to understand all the players (mostly academics) who are involved in pushing this research forward.

It turns out that the first paper published on a voter verifiable system was actually written back in 1981, by one David Chaum, then a graduate student at the University of California, Berkeley. However, within the last few years, many mathematicians, cryptographers and computer scientists (including Chaum himself) have picked up where he left off.

To date,  various iterations have been trying to figure out how to make verified voting actually work. There have been a few examples of small, binding (although non-public sector) elections, but nothing on the scale of even a local city election.

How do these voting systems work?

The idea is that when you vote, your vote gets encrypted in some way, such that "Candidate A" gets turned into some meaningless string like "XYZ," or "e3S4fqV5ft8q." In other words, there's no way to know once that value is encrypted whom exactly you voted for. Then those encrypted strings can either be shuffled around, or added in a particular way to be able to determine the total vote count. The exact method depends on whether you're using Chaum's latest proposal, known as Scantegrity II (which is awaiting approval for a trial run in an election in Takoma Park, Md.), or a similar, but rival, system called Helios, created by the cryptographer Ben Adida, who has a doctorate in cryptography at MIT. You can think of Chaum's Scantegrity II, Adida's Helios, and another similar system, being developed in England by professor Peter Ryan of the University of Newcastle upon Tyne, as essentially three variations on the same theme.

It can then be mathematically proven that they were encrypted and then decrypted accurately. Now, while it may take a fair amount of knowledge of mathematics to know exactly why it can be proven that this particular election system is working properly, and that your vote was encrypted and tallied accurately, it is something that, at its core, is fundamentally knowable.

OK, but pencil and paper is something that we all can understand. The vast majority of us aren't going to get a Ph.D. in cryptography in order to understand a simple election. But in a phone interview yesterday, Adida told me that we don't have to.

"It's a wrong assumption that we're shifting trust from the average person to something only a cryptographer can trust," he says.

He points out that any group, be it the Republican Party, the ACLU or Joe the Professor, could study up on its own about the underlying math, or could find a cryptographer they  trust to make sure that the votes were formed and tabulated properly. This currently is not the case, even in an entirely analog system -- there is no way for any group to be involved, even as an observer, in the entire voting process.

In fact, after a few different versions of his own E2E setup, Adida has recently come up with a new and easy way to conduct your own secure, safe and totally verifiable election -- online. It's called Helios and is open-source and free. Adida says that Helios isn't quite ready for prime time, like something on the scale of a presidential election, so he aimed for a slightly lower target.

"Let's target a different kind of election where you need the secrecy of the votes and you want verifiability but you're not going to worry about people coercing you," he says. "The market for Helios is your local book club that wants to elect a president, your synagogue or church or mosque that wants to elect an advisory board, [or] your online software community. [It's an election where] no one's going to buy anybody's votes but they still want to have a real election."

In fact, Helios was recently used in the ICF Community Steering Members election, a software group that works on electronic ID card standards. In fact, you can verify that the election was conducted properly simply by copying and pasting the election fingerprint ID (agxoZWxpb3N2b3RpbmdyDwsSCEVsZWN0aW9uGIERDA) into the verifier page.

So what's the point of Helios?

Adida says: "It's to provide a feature that doesn't exist today: verifiability. [Also,] to get people accustomed to what it means to verify their vote -- when you experience it, a lot of folks get the feeling that something different is going on."

While I conducted my own trial election with Adida by phone, I'd like to try this out with readers. The first 10 people who e-mail me [cfarivar at salon dot com] with the word "Helios" in the subject line, I will invite you to our little election, just so you can try it out for yourself.

Or heck, you don't want me involved? Check it out yourself and report back, ya hear?

Now, I think there is an argument to be made that voting officials and perhaps even the voting public may have a hard time swallowing this idea. (To his credit, Chaum has ingeniously designed Scantegrity II so that it can run on top of an existing paper-and-pen optical scan system -- it needn't involve computers in the process of actually voting.)

Indeed, in order for public officials to definitively show that this cryptography works the way it's supposed to, they would need to provide an advanced mathematical proof, known as a "zero-knowledge proof." Even if the science is ultimately proved to be sound and bulletproof, David Wagner, a professor of computer science at U.C., Berkeley, pointed out to me in a previous interview: "Will voters accept something that uses mathematics that they won't understand?"

It also doesn't help matters that Adida and his MIT advisor Ron Rivest note in their 2006 paper that "the sheer size of the proof precludes printing it on the ballot alongside the ciphertexts."

Both Adida and Chaum point out that there are lots of technologies that we use all the time that we don't understand, ranging from airplanes to the Internet. Only a small number of people actually  care how they work, and can educate themselves about it, much the same way they can with these types of systems -- in other words, it's just math, plain and simple.

Still, Adida and Chaum have convinced me that their ideas are sound. We'll see if they go anywhere in the public sector anytime soon.

Cyrus Farivar

MORE FROM Cyrus Farivar

Related Topics ------------------------------------------