In order to audit a ballot, an auditor or a voter would use the original ballot key to disclose all possible codes for all candidates, thus revealing the entire computational chain to prove whether the votes were recorded and tabulated accurately. And to verify that a person hasn’t cheated during any step of the process, one of the pointers can be revealed to assure that the proper connection between the results and the anonymized encoded ballots is maintained.

Scantegrity II is not a replacement voting system, but works with either precinct-based or central scan systems, a feature that Chaum says makes it attractive to public officials. The printing of ballots, however, requires the capability to print with invisible ink and to print each ballot differently.

Scantegrity II might be used in an upcoming municipal election in Ta-koma Park, MD, a suburb of Washington, D.C., but the city council has not yet made a final determination.

Different approaches, same Goal

While Scantegrity II appears to be the most public election-ready system, there are several replacement systems—most notably Prêt à Voter (or Ready to Vote), Scratch & Vote, and ThreeBallot—that use different cryptography-based approaches to achieve the same goal of end-to-end voter verifiability.

Developed by Peter Ryan of University of Newcastle upon Tyne, Prêt à Voter does not rely upon the voted values to be encrypted and randomized, but uses a random candidate order that varies from ballot to ballot. Once a vote is cast, the side of the ballot with

end-to-end auditable
voting systems
could put the
controversy about
the merits of
electronic voting
versus paper ballots
to rest.

the list of candidates is destroyed.

The bottom of the non-discarded side of the Prêt à Voter ballot contains a cryptographic string with information on the discarded candidate list order. In order to decrypt the candidate list order and determine the value of a vote, voting officials or party representatives use a series of secret keys to decrypt the ballots.

Prêt à Voter was successfully used in student elections at the University of Surrey last year, and Ryan plans to test Prêt à Voter again in upcoming student elections at the University of Newcastle upon Tyne.

Scratch & Vote was developed by Ben Adida, a research fellow with the Center for Research on Computation and Society at Harvard University, and Ron Rivest, a professor of computer science at MIT, and its format is similar to Prêt à Voter.

A Scratch & Vote ballot is perforated down the middle, and the left side has a list of candidates’ names and the right side has a series of cor-

news

responding check boxes. Beneath the check boxes is a 2D-barcode. A scratch surface is positioned below the barcode, and a perforation separates the scratch surface from the rest of the right half of the ballot.

If the voter wants to audit the voting process, she selects a second ballot and removes the scratch surface, thereby voiding the ballot, which the voter gives to a trusted party on the premises. The trusted party scans the barcode, reads the randomiza-tion data previously hidden under the scratch surface, and can confirm the ballot is correctly formed.

The voter now makes her selection on the first ballot, discards the left side of the ballot (which contains only the randomized candidate order), and gives the ballot to an election official. The election official ensures the scratch surface is intact and de-taches the scratch surface for the purpose of discarding it. The voter enters the ballot’s remaining checkmark (to indicate her vote) and barcode, which is effectively the encrypted ballot, into a scanner.

The voter can take the remainder of the ballot home and check on a public Web site that her ballot was correctly tabulated, and if it wasn’t, she still possesses the remainder of the ballot. In addition, the voter can audit the tally process and the verifiable decryption conducted by the election officials.

With Scratch & Vote, each vote is recorded as an encrypted value by using the box that was checked to determine which encrypted value to use. The values are tallied using homomorphic encryption, which allows for the sum of two encrypted values to be equal to the

Artificial Intelligence
Cooperative Robot Swarms

An enterprising group of undergraduate students at the University of Southampton unveiled a group of inexpensive and identical, matchbox-sized robots at the recent Artificial Life XI conference. The robots communicate with each other via an infrared technology used

in mobile phones, and can independently divide up tasks, without instructions from a central control program.

In a demonstration at the conference, the robots, which have green and red lights, autonomously divided themselves into two groups, 80% red and 20%

green. When some of the “green” robots were removed from the group, the remaining robots reorganized into an 80/20 split.

Swarms of robots have certain advantages over a single, self-contained robot, according to some roboticists. “You might have some complex robot that

is sent to Mars, has a technical problem, and then the mission is basically over,” said Claus-Peter Zauner, the leader of the swarm robot project, in an interview with the BBC News. “With swarm robots, even if a percentage of them fails, they’ll still be able to achieve their goal.”