Detailed explanation of how the voting encryption system works


Last week, in Takoma Park, Md., a new cryptographic voting system that ensures accurate vote counts was used for the first time in a real election. A general description of how the system performed on Election Day is here; this article provides more details about how the system actually works.

Called Scantegrity II, the system is a variation on conventional optical-scan voting. But instead of filling in a bubble next to a candidate’s name, the voter uses a special pen that exposes a code printed inside the bubble in invisible ink. A voter can write down that code, along with the serial number of her ballot, to later verify the results online.

She can’t, however, offer a would-be vote buyer proof that she selected a particular candidate, since the code isn’t associated with the candidate’s name. If enough people confirm their codes — about 2 percent of voters — it’s 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 link the ballot codes and the candidates’ names. Then, it 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.

In the Takoma Park election, the election commission used 20 distinct sets of tables, with three tables in each set. In each set, the first table listed the codes printed on each ballot. The codes were listed in a random order to make it impossible to tell which code was associated with which candidate. The third table featured only the candidates’ names at the top — it was simply a grid for recording the votes assigned to each candidate. The second table mapped each code in the first table to a unique slot in the third table. This second table ensured that the slot fell under the right candidate’s name, but the mapping was otherwise random to make it impossible to tell from a slot’s location which ballot it corresponded to.

After the election, for each of the 20 sets of tables, the election commission web site posted the final tally using the grid in table three. It released the codes in table one that were actually exposed in the voting booth, along with encryption keys that verified their authenticity. And it randomly released half of the information in table two: either the half that pointed backward, to the codes in table one, or the half that pointed forward, to the slots in table three. Finally, it flagged all the entries in table two correlated with recorded votes — with exposed codes in table one and slots checked in table three.

Exposing only half of table two preserves voter anonymity: There’s no way to figure out which ballot went for which candidate. But it also provides enough information that any attempt to tamper with the results can be detected. To change the final tally, a ballot stuffer would have to insert fake votes into table three. But that would entail spuriously flagging the corresponding entry in table two. And that would entail revealing the corresponding code in table one — which a voter who checked her code online would notice.


Topics: Computer science and technology, Cryptography, Computer Science and Artificial Intelligence Laboratory (CSAIL), Technology and society, Voting and elections

Comments

I don't understand
"There’s no way to figure out which ballot went for which candidate." So how can I determine if my vote was counted the way I voted? <i><b>I think it’s probably accurate to say that you can’t determine if your vote was counted the way you voted, but the system can ensure (with 99.9999 percent certainty) that everyone’s vote was correctly counted. The technical explanation in the article was already getting too detailed — which is why we split it off on its own page — but I’m happy to elaborate further here. As we say above, there are 20 sets of tables, and for each set, table two is partially exposed after the election. Let’s call those 20 table twos either backward-facing (if the correlations with table one are exposed) or forward-facing (if the correlations with table three are exposed). The exposure of one half or the other is done in truly random fashion, on the basis of the stock market’s close that day. But on average, about 10 of the tables will be forward-facing, and 10 will be backward-facing. For each set of tables, any vote on any ballot (recorded in table one) has exactly one slot in table three. If a ballot stuffer wants to add a vote, he has to put it in a slot in table three. But then the corresponding entry in table two must be flagged. If the ballot stuffer tries to avoid detection by leaving the corresponding entry in table two unflagged, then there will be discrepancies in all the forward-facing tables. If the ballot stuffer flags the entry in table two but doesn’t reveal the corresponding code in table one, then there will be discrepancies in all the backward-facing tables. If the ballot stuffer flags the entry in table two and does reveal the corresponding code in table one, then there are two possibilities. One is that two codes have been exposed for a single ballot, which would be evidence that something has gone awry. The other possibility is that the ballot stuffer has actually changed the vote on a particular ballot — deleted the proper entry in table three and added a spurious one. But then the wrong code would show up in table one, which a voter who checked her code online would notice. So it’s not so much that the proper code in table one shows that your vote was counted correctly; it’s that an improper code in table one shows that something is amiss. There could still be something amiss even if your code is correct in table one; but then there would be a discrepancy in the forward-facing tables, and the fraud would be exposed. —Larry Hardesty</i></b>
How does the system handle errors such as wrong ballot serial number or wrong code? What if very few voters verify & one has made an error copying?
What implications (if any) would the success of this type of cryptographic voting have for voting online in future? <i><b>Good question! If the article hadn't already gotten so long that we had to split it in two, I would have addressed it. Basically, Ron Rivest said that online voting could be made cryptographically secure, but that the system would probably end up being more complicated and costly than keeping track of paper ballots. And, he said, the biggest problem with online voting isn't cryptographic security: it's the risk of coercion or vote-buying if someone can look over your shoulder as you vote online. —Larry Hardesty</i></b>
I am not sure how much this will do to improve voter confidence as I find the description quite difficult to follow and I am fairly knowledgeable about this stuff. I don't think the average voter would do a whole lot better. From the description it sounds like if a crooked election official were to release the entirety of table two, then secrecy of the entire election would be compromised. Worse, if a voter were ever worried that this MIGHT happen he could be easily intimidated. Putting an serial number on each ballot seems like a step in the wrong direction since an intimidator could demand to know the ballot number of a voter and then check the physical ballot. The same could be done with the candidate code. The voter would need to have confidence that no crooked person could gain access to the physical paper ballots. Any doubt would lead to the possibility of intimidation. One of the easiest forms of fraud is for a crooked election official to cull the ballots that left an entry blank and fill in his favorite candidate. This scheme gives no protection to that. Is it possible that an attacker of this system could read the "invisible ink" for the candidate he did not vote for and falsly contest an otherwise valid election? What does a voter do if the serial number he wrote down does not match the reported result? If it doesn't match the other candidate's number either he would likely assume he copied the number incorrectly, but there is lingering doubt as there is no way to rule out that the ballots or tables were tampered with pre-election so as not to match and allow undetected fraud.
Back to the top