• In last week's municipal election in Takoma Park, Maryland, voters voted by exposing three-digit numerical codes printed on their ballots in invisible ink. By later verifying the codes online, they could help minimize the possibility of election fraud.

    Photo: Alex Rivest

    Full Screen

Cryptographic voting debuts

A new system for ensuring accurate election tallies, which MIT researchers helped to develop, passed its first real-world test last Tuesday.


Last week, in Takoma Park, Md., a new cryptographic voting system that could ensure accurate vote counts was used for the first time in a real election. MIT’s Ron Rivest, the Viterbi Professor of Electrical Engineering and Computer Science, helped develop the system and says he’s quite pleased with how the technology worked. Takoma Park’s city clerk, Jessie Carpenter, agrees that the trial “went very well.”

To minimize the disruption of existing voting procedures, the system, called Scantegrity II, was designed to work with ordinary optical-scan voting technology. Optical-scan voting — which has become the dominant technology in the United States since the 2000 presidential election — usually requires the voter to fill in bubbles printed on a ballot next to candidates’ names. With Scantegrity II, the voter instead uses a special pen to expose a code printed inside the bubble in invisible ink. Thereafter, the ballot is fed into an ordinary optical reader, which simply determines which bubbles have been darkened.

Any voter who’d later like to confirm her vote can simply jot down the code that’s in the exposed bubble, along with the ballot’s serial number, and take that information home. (In the Takoma Park election, voters could record their codes on cards stacked in the voting booths, which were printed with the names of the contested offices — mayor and city councilor.) The voter can then look up that serial number on the election commission’s website and confirm that it’s correlated with the code inside the bubble she marked. Although on the website, the code is never associated with the candidate’s name, Scantegrity ensures that if just 2 percent of voters confirm their codes, it’s statistically almost impossible for vote tampering to go undetected.

The key to the system is that before the election, the election commission prepares a set of tables that, taken together, link the ballot codes and the candidates’ names; but that link can’t be deduced from any one table by itself. Then the commission publicly releases a set of digital signatures that cryptographically describe all the entries in the tables without actually revealing them. That way, the tables can’t be tampered with after the ballots are cast, but neither do they reveal any information that ballot stuffers could use before the election.

After the election, the election commission releases some of the information contained in the tables — including the codes exposed on all the recorded ballots — along with encryption keys that verify its authenticity. The partially revealed tables conceal enough information to preserve voter anonymity: There’s no way to figure out which ballot went for which candidate. But they reveal enough information that anyone interested in performing an audit can ferret out fraud. How the system works

Going into the Takoma Park trial, the crucial question was whether 2 percent of voters would bother to write down their codes and check them online. According to Poorvi Vora, a member of the Scantegrity team at George Washington University, 1,722 votes were cast and 66 people checked their codes — almost 4 percent.

Carpenter says that she would have liked that number to be higher. But “that’s not the fault of the Scantegrity system,” she says. “We needed to have done more education of the voters.”

Another question was whether the decoder pens would hold up over the course of the day. “The smudging issue was one we were slightly concerned about,” Rivest says. “You know, if you take a highlighter and you run it over newspaper, it will collect the black ink.” Poll workers, he says, were instructed to check the decoder pens occasionally to make sure they were in good working order. But “the ink seemed to be lasting fine,” Rivest says, and “smudging wasn’t much of an issue.”

Carpenter adds that a very small number of voters refused to use the decoder pens, instead pulling out their own ink pens and filling in the bubbles. But since the Scantegrity system requires no modification to the optical scanners, that kind of improvised procedural change didn’t affect the final tally.

“I was a little bit afraid that we’d have a lot of invalid ballots,” Carpenter says. “But we didn’t. We had some, but I don’t think it was high compared to any other ballot-marking system.” Rivest confirms that, according to the Scantegrity team’s research, the fraction of invalid ballots was consistent with that seen in conventional optical-scan voting.

“I don’t think the system slowed us down at all,” Carpenter adds. Slightly after 5 p.m., she says, a large wave of voters hit the polls, and the wait got up to about 15 minutes, she says. But Carpenter believes that the sudden surge was the result of a story on a local National Public Radio affiliate describing the Scantegrity trial. “I think we got a little publicity boost that made people come out who might otherwise not have come out,” she says. “We just had tremendous lines once that story hit, and I can’t believe it was coincidence.”

When Takoma Park decided to use the Scantegrity system, “we certainly took notice of that,” says Matthew Masterson of the U.S. Election Assistance Commission, which oversees voting technologies and procedures in the United States. “The National Institute of Standards and Technology, who’s our partner in developing the standards, just held a conference on end-to-end cryptographic systems [like Scantegrity II], and we’ve started the process of looking at systems like that and how to test them.” Masterson adds that “anytime a jurisdiction takes a look at new technology like that —the cryptographic end-to end system in this case — that’s a great conversation for voters and election officials to be having. And in that sense, it’s very positive for democracy.”


Topics: Computer science and technology, Cryptography, Computer Science and Artificial Intelligence Laboratory (CSAIL), Electrical engineering and electronics, Voting and elections

Comments

So how does this prevent stuffer from highlighting unused ballots and stuffing these extra votes?
Hi, It seems to me the biggest issue here is that the end-user (voter) must write down the codes. What if you simply printed and perforated the ballots so that there would be 2 identical bubbles for each vote. Then you could just instruct the voter to mark both adjacent bubbles and tear off the strip containing the codes, serial number and a URL to check at if they would like to do so. If someone chooses not to do so, the extra pieces can simply be removed and safely discarded or possibly folded over to fit the scanning machine (not sure on size specs on these scanning machines) <i><b>In earlier tests of the system, the ballots did indeed have detachable receipts at the bottom, with the serial number printed on them. But according to one of the sources for the story, voters didn’t like them; they found that kind of modification of the ballot itself too radical, or perhaps too intrusive. There are several reasons, though, that having a second set of bubbles on the receipt wouldn’t work. The main one is that it would give the voter access to the codes corresponding to the names of the candidates he didn’t vote for. The difficulty of figuring out what those codes are is, in fact, of the one of the things that ensures the reliability of the system. Say, for instance, that a voter wanted to fraudulently call the validity of the vote into question. He could claim that, when he checked his ballot number at home, he got a code other than the one that he revealed in the booth. But then he would have to report what the code he revealed in the booth actually was. The chances of correctly guessing a valid code are very low. —Larry Hardesy</b></i>
It doesn't prevent it, but it makes it harder. Someone would need to take some or all of the people who could vote but did not vote, pretend those people came in and presented photo ID and voted, and vote for them. Sounds simple on the surface, but there's a problem: when do you perform this step? If you add fraudulent votes randomly during the day, you are caught when one of the people you fraudulently voted for comes in to vote for real. If you add the fraudulent votes all at the end, the vote timestamps would look strange -- people would be voting after polls close, or there would be tons of voter throughput at the end. Plus, if voter turnout ended up being much higher than actual, anecdotal reports would likely spawn local gossip and local news stories, prompting people who didn't vote to check if a vote was cast for them. So depending on voter turnout it may still be possible to fraudulently vote for perhaps 1% or 2% of the voters who didn't show up, but any more than that risks being caught. This does nothing for fraudulently eliminating otherwise-valid voters whose votes you can somewhat predict -- but that's outside the scope of what this is trying to accomplish.
hanmas...ballets with serial numbers can be tracked, and only when someone shows up to vote would the ballot be introduced into the tally pool. Because each ballot is unique stuffing will not work.
What is MIT doing about the chain of custody of the hardware? Do they have 100% chain of custody from the point of where the chip was doped all the way 24/7/365 until the live election? NO? Then the hardware can not be trusted. Get out your electron microscopes and start doing destructive reverse engineering looking for kill switches, hidden logic, etc. Oh wait, you have to destroy every voting machine to do that! That will be expensive. The results from this system are only what's presented, not necessarily what the actual tabulation is. All your doing here is adding levels of complexity to a problem which doesn't have a solution besides OUTLAWING ALL ELECTRONIC VOTE TABULATION DEVICES. Electronic signals are invisible to humans. The moment you go from an analog vote to a digital copy representing that vote you no longer can validate what's happening. The Serial number on the ballot is an identifying mark. Identifying marks (even if you have to use a stupid pen) = No transparancy As you already stated some ballots failed. That means a voter was denied the right to vote. Unacceptable! Even if a voter writes down the serial number of the ballot and the id number of the vote field, there's no integrity or plan in place to fix a bad marked vote for whatever reason. There's no way to validate the output of such a device is the same as what is internally stored. Not all voters have web access. This electronic vote tabulation device does not solve these problems... No plan in place for failures. Except that voters lose their votes. While MIT students certainly mean well, this is not a solution, and it won't protect our constitutional republic. It's completely faith based voting. It's unacceptable, and history will show all such electronic vote tabulation devices must be outlawed. The SOLUTION: Paper ballots hand counted by humans (made up of the public) with an unbroken chain of custody. No local law enforcement and officials shall be allowed to hassle/arrest poll watchers and by proxy break the chain of custody. No electronic voter registration poll books. No electronic vote tabulation devices. Voting has to be transparent. Ballots which have serial numbers are not transparent. Voting has to have public oversight. Not abusive law enforcement and officials! Nobody should be trusted. No electronic vote tabulation device should ever be trusted. The article says, "But they reveal enough information that anyone interested in performing an audit can ferret out fraud. " Outright lie. If fraud is found there's no way t fix it. This is electronic dictatorship, not positive for democracy. You all better check yourselves. <i><b>Scantegrity is, among other things, a way to protect against the sabotage of the scanner hardware. That’s one of the several kinds of fraud that the system would detect. When Jessie Carpenter says that the number of invalid ballots didn’t seem high relative to “any other ballot-marking system,” she’s including hand-counted paper ballots, which is in fact the system that Takoma Park used prior to the Scantegrity trial. The kinds of invalid ballots she’s talking about are ballots where people vote for two different candidates, or that kind of thing — the type of invalid ballots that occur in any election, with any voting technology. —Larry Hardesty</b></i>
I think that sort of fraud is already accounted for by requiring voter registration, name, address, etc. In other words, to do that, someone would have to use an old trick like voting under the names of dead people. Presumably we have independent ways of tracking that.
that's awesome. but i'd be a bit scared of mafioso types standing outside waiting for the person they previously contacted to say "give me your code so we can verify you voted for the person we told you to vote for" <b><i>Please see reply to rogmorri, below. —LH</i></b>
If your number doesn't match, how can you distinguish between voter fraud and your own mistake in copying the number? If millions of people are checking their numbers won't this result in thousands of accusations of fraud even when there is none? And conversely even if there were actual fraud and I discovered it, I would probably say nothing, assuming (correctly) that it was more likely that I had erred in recording the number. <i><b>As I mention in my reply to dclaw, it’s very difficult to guess the code for an unexposed bubble. If someone wrote down her code incorrectly — say she missed one digit — it’s extremely unlikely that the result would be a valid code for one of the other candidates for the same office. So innocent transcription errors would be relatively easy to identify. For this election, the Scantegrity team used a simple three-digit numerical code, precisely to minimize the risk of transcription error. —Larry Hardesty</b></i>
This fails the following scenario... Carlos the brute tells Alice "If you know what's good for you, you'll vote for Bob and you'll tell me the code number so I can verify that you voted for Bob!"
The term "public elections" means that the public must be able to see and authenticate ALL essential processes. This does not meet that test, but instead transfers the problem of "trust" to a different place -- still not a public place. The German high court got it right when it banned their e-voting system and didn't choose crypto solutions either. Instead, because the court deems any system that does not allow the public to see ALL essential parts of the process and authenticate them, WITHOUT need for special expertise, the nation of Germany hand counted its last election in public. In addition, the German decision requires that all parts of the election be understandable by the election without need for special expertise. This is a key difference between a truly democratic system and one that pretends to be democratic. I think you will find, as I have, that the Scantegrity advocates place very little value on the public right to know and understand their own elections, and indeed, place little value on the Constitution or the principles in the Declaration of Independence as well. You see, in all cases our founding documents honored the PUBLIC right to know, rather than some elite subset of cryptographers, internet web site hosts, or government officials. When we keep the public right to know in mind, these systems miss the mark rather badly. The only response I've gotten from their proponents is that the public really doesn't need to know or understand.
This is VERY similar to a system I have been proposing to friends for YEARS now (since the 2000 election mess, in fact). My proposal is much simpler, though: 1) Each ballot has a serial number; 2) Each ballot has one "white" copy that goes in the ballot box and one "yellow" copy that is retained by the voter 3) The election results are published in cross-reference table form in print and on the Web. This allows DOUBLE verification for the public, as a) all voters may verify their vote was correctly cast simply by locating the row marked with their ballot number and comparing to their vote "receipt" and b) anyone can (if they want to go to the trouble) tally the votes themselves, as the results are public. Combined with effective voter identification methods, this method would ensure 100% verifiable voting results. <i><b>Your proposed system runs into the problem that rogmorri identifies above: it opens the possibility of vote buying or coercion. Scantegrity is specifically designed to avoid that problem. —Larry Hardesty</b></i>
Here's another advantage... now we can finally automate the vote-buying process. "Enter your bubble code to claim your coupon for a free pizza!" <i><b>There’s no way to tell from the code number whom you voted for. That’s the point of the system. —Larry Hardesty</b></i>
Oh, I see. So, one can only confirm that my choice on a particular ballot was counted; one can't confirm which candidate a vote was cast for. <i><b> I think the best way to say it might be that if you confirm that your code is correct, you ensure that any attempt to tamper with your vote can be detected using publicly available information. For the details, you might want to click "How the system works," above. --LH</b></i>
I worked as an "Election Judge" (i.e. polling place worker) so I can address some of this. Much of the security of the ballots and ballot box depends on having multiple people, including representatives of both major parties, present whenever the ballot boxes are not sealed. All these people are observing the supply of ballots and the flow of ballots into the box at all times. This is what we have to ensure the integrity between the point where the voter's identity is checked and the ballot goes into the box, i.e. that no extra ballots are introduced that are not associated with a particular voter. Also, the count of people appearing to vote is compared against the count of ballots in the box. At least where I worked, there aren't any timestamps reflecting when a ballot goes into the box -- it's just dropped in, and the box is opened later at election HQ and the ballots fed into a machine. Again, there are multiple observers. In between, the box is sealed. Of course we depend on the integrity of the sealing system.
Phil's comments have some errors. For example, if the ballots are paper and are preserved, and their counting is called into question, they can be recounted, by hand if necessary. It is simply untrue that "you can no longer validate what's happening". This is not true of any fully-electronic system, so I agree that such systems are unacceptable. The fact is that historical studies have shown that hand counting has higher error rates than, for example, electronically scanning paper ballots. The crux is which of these errors are just random noise (effectively inevitable) and which are intentional bias. Intentional bias could be done either electronically or during hand counts. With electronic counters, there is some hope for detecting and proving the bias by, among other things, recounting the same ballots, either on different machines or by hand. The suspect electronics could then be subjected to intense scrutiny for evidence of tampering. How can one prove that a human intentionally mis-counted ballots by hand? It's true that ballots intended to be counted electronically can be mismarked and thus miscounted or not counted. But this is just as true with hand counting -- voters circle candidates names, scribble on the ballot, place marks outside the designated box, you name it. Refusing to use electronic systems won't cure this fundamental problem of voters mis-marking ballots. The notion that we should have "public" oversight that is not "law enforcement" or "officials" is nonsensical. Exactly what will the overseers be enforcing, if not the laws protecting the integrity of the election process? If the overseers are not officials, who are they -- any random person who walks in and proclaims themself a member of the public, and takes control of a ballot box?
Back to the top