ThreeBallot in the FieldHarvey Jones, Jason Juang, G reg B eloteInstructor: Ronald L. RivestDecember 13, 2006AbstractVoting systems have been the subject of much recent controversy. Due to thedifficulty of securing and auditing electronic voting sys tems, a variety of different paper-based cryptographic voting sch emes h ave emerged. Ronald Rivest has proposed apurely paper-based system called ThreeBallot, which strives to achieve the same level ofsecurity as cryptographic systems without using cryptography. Although ThreeBallothas been subject to academic criticism, it has not been tested in the field. This paperdescribes a paper-based and a computer-aided implementation of ThreeBallot. Anysuccessful voting system must be usable, must be secure, and must preserve the secretballot. To test usability, we held mock elections and observed voters. To test securityand privacy, we executed attacks against these mock elections.In one mock election, 20% of voters successfully sold their vote. One student, whengiven control of tallying the votes, was able to throw the entire election. In our usabilitystudies we confi rmed voter difficulty in using ThreeBallot. We found that about 10%of voters didn’t understand ThreeBallot well enough to check another’s ballot, and inone mock election more than 30% of voters failed to cast a valid ballot on their firsttry.1 IntroductionVoting systems fail for many reasons. They can b e too complex for the average voter touse, they can be run by corrupt voting o fficials, or they can compromise voter privacy. Amodern voting system must avoid these pitfa lls under the pressure of a real-wo r ld election ifit is to be a feasible replacement for current voting technology. Professor Ronald Rivest hasproposed ThreeBallot [1], a paper-based voting system that claims to be private and secure,with a small usability tra de-o ff .ThreeBallot has been subj ect to academic criticism, for example by Appel [2] and Strauss [3],but it has not been used in an actual election environment. With the goals of usability, secu-1rity, and privacy in mind, we conducted several mock elections designed to test ThreeBallotwith actual voters, and to discover where the system succeeds a nd fails.We tested the usability of the system by running elections open to the public in Building32 and the East Campus dormitory. We anticipated usability problems with the vanillaThreeBallot system, so we implemented a computer-based ThreeBallot machine with aninterface similar to a touch-screen electronic voting machine. We recorded our interactionswith voters, the number of inaccurate ballots that were submitted, and users’ understandingof the syst em as measured by a quiz after their vote was tallied. We found that voterswere initially skeptical about the system. We found that a substantia l number of votersexperienced difficulty using paper-based ThreeBallot for the first time, with more than thirtypercent of voters having their ballots rejected on submission. After voters had successfullycompleted one election, they were familiar enough with the system to distinguish correctand incorrect ballots.In order to test the system’s robustness against election-stealing, we r an a mock election forstudents familiar with the system, a nd provided incentives for any student able to producesubstantially skewed election results that were not subsequently repudiated by the class.One student successfully mounted an attack, combining analysis of all submitted ballotswith spying on other voters’ r eceipts. His attack wa s able to change the winner of a ll threeraces in the in-class election.In order to test ThreeBallot’s robustness against privacy compromises, we provided incentivesto voters in the in-class election for proving to us how they voted. We also implementeda proposed privacy attack, which we discuss in Section 2.4.4, and a t t empted to prove howvoters voted, assuming we were able to coerce them into giving us their receipts. We wereable to reconstruct one-third of the ballots cast in the in-class election and five-sixths of theballots cast at the Stata Center election, but could not reconstruct any o f the ballots cast inthe East Campus election.2 Background2.1 Design CriteriaSeemingly contradictory criteria must be satisfied by any successful voting system. The idealsystem is transparent enough to inspire complete public t r ust, yet hides enough informationto ensure the secret ballot requirement. Designs that satisfy both of these requirementstypically sacrifice usability and/or scalability.Privacy A voter’s choice must be kept secret, even if he or she may wish to divulge it. Ifthe secret ballot requirement is not held, voters may sell their votes, or the powerful may2force other voters to select a pa rt icular candidate.Verifiability A voting system should be publicly verifiable. Voters should be able to de-termine, to a very high probability, that their votes were accurately recorded and tabulated.An audit tra il should be available so that the count can be verified.Usability A voting system should be usable by the voting population. Complicated, hardto use, or error-prone systems may disenfranchise some voters.Scalability The voting system should scale well to large numbers o f voters. This includesnot only handling a large number of tota l voters, but a lso a large number of simultaneousvoters, to maintain a short wa iting times throughout the election day. Ideally, any extraresources required to handle a larger number of voters should be cheap and easy to procure,and large elections should not compromise election security.2.2 Cryptographic voting schemesAn ideal voting scheme allows an election to be auditable by any voter, but protects thesecurity of every voter’s ballot. Several ideas have been proposed that use cryptography andzero knowledge proofs to provide privacy and verifiability.David Chaum proposed such a scheme [4] employing visual cryptography and mixnets. Hisscheme allows a voter to take home a receipt. The election official publishes copies of allthe receipts on a web site, where voters can check that their receipt appears and is identicalto the physical receipt. This receipt does not reveal who the voter voted for. In fact, thereceipt is information-theoretically secure.The tabulation process then begins with these receipts, and proceeds through stages ofdecryption, each of which is auditable by the public to ensure that there is no foul play.Chaum’s scheme
View Full Document
Unlocking...