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.
