ThreeBallot

Last updated
A sample ThreeBallot multi-ballot, with a first race for President with candidates Jones, Smith, and Wu and a second race for Senator with candidates Yip and Zinn. Threeballot.png
A sample ThreeBallot multi-ballot, with a first race for President with candidates Jones, Smith, and Wu and a second race for Senator with candidates Yip and Zinn.

ThreeBallot is a voting protocol invented by Ron Rivest in 2006. ThreeBallot is an end-to-end (E2E) auditable voting system that can in principle be implemented on paper. The goal in its design was to provide some of the benefits of a cryptographic voting system without using cryptographic keys.

Ron Rivest American cryptographer

Ronald Linn Rivest is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). He was a member of the Election Assistance Commission's Technical Guidelines Development Committee, tasked with assisting the EAC in drafting the Voluntary Voting System Guidelines.

End-to-end auditable or (E2E) systems are voting systems with stringent integrity properties and strong tamper resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were counted as cast, without revealing which candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.

Contents

It may be difficult for a vote to be both verifiable and anonymous. ThreeBallot attempts to solve this problem by giving each voter three ballots: one verifiable, and two anonymous. The voter chooses which ballot is verifiable and keeps this secret; since the vote-counter does not know, there is a 1/3 chance of being discovered destroying or altering any single ballot. The voter is forced to make two of their three ballots cancel each other out, so that they can only vote once.

Goals

The crucial advantages that the ThreeBallot system offers over comparable, ciphered ballots are:

  1. Its implementation is familiar looking and simple for voters to understand, compared to other encryption systems (arguably, the most important advantage of all).
  2. The ballots can be counted directly, without decryption. This is because they have the property that the sum of the marks is the sum of the votes for the candidate, even though any individual ballot section cannot reveal the candidate preference of the voter.
  3. There is no key that requires protection or secrecy in order to maintain security (the "Achilles' heel" of many proposed systems).
  4. While it requires a machine to validate the ballots before depositing them, afterwards the ballot record is entirely on paper, and requires no additional security process beyond that afforded traditional ballots.

Additional theoretical system goals include:

  1. Each voter's vote is secret, preventing vote-selling and coercion.
  2. Each voter can verify that his vote was not discarded, and was correctly used and not altered, in the computation of the election result. (And if not, the voter is in a position to prove the vote counters cheated.)
  3. Everybody can verify the election result was computed correctly.
  4. The method is designed for use with paper ballots and requires primarily low-tech devices, but is compatible with more advanced technologies.

Method

In the ThreeBallot Voting System, voters are given three blank ballots, identical except for a unique identifier that is distinct for each ballot. To vote for a candidate the voter must select that candidate on two of the three ballots. To vote against a candidate (the equivalent of leaving a ballot blank in other systems) the voter must select that candidate on exactly one ballot.

Thus every candidate gets at least one ballot with a mark, and one ballot without a mark; as a result seeing any one ballot does not tell if the voter voted for the candidate or not. While this also means that every candidate gets at least one vote when the three ballots are summed, this constant offset for all the candidates (equal to the number of voters) can be subtracted off the final total of all the ballots.

 John Foo    [ X ]    [   ]    [ X ]         //  Any two columns marked indicates a 'for' vote Barb Bar    [   ]    [   ]    [ X ]         //  Any single column marked is not a 'for' vote. Bill Too    [   ]    [ X ]    [   ] 

However, it is imperative to verify that the voter did not mismark their ballot: no candidate can be left blank on all 3 ballots, and no candidate can be selected on all three ballots.

 Andy Oops    [ X ]    [ X  ]   [ X ]        //  Not allowed.   Elle Error   [   ]    [    ]   [   ]        //  Not allowed. 

This requirement means all three ballots must be inserted into a machine to validate this before the 3 ballot vote is cast. Failure to do so would enable a voter to both cast an extra vote for and an extra vote against, allowing voter fraud; by design a for vote cannot be distinguished from an against vote once cast, so this multiple-vote fraud could not be detected until the final tally-verification (and maybe not even then), and it cannot be corrected at that point or even traced to a specific voter.

Typically, the ballots might be co-joined to simplify the marking by the voter, but before they are cast it is imperative that the ballots be separated. Once separated, and combined with other ballots in scrambled order, the true vote is encrypted. For example, consider just the third column ballot for John and Barb above. Each of them has an 'X' but the voter is actually voting for John and not Barb. Likewise if you saw just the second column ballot, it only shows a mark for Bill, but again the overall vote by the three ballots together is actually for John. When all 3 ballots are summed, the totals will show 2 marks for John and 1 mark each for Barb and Bill. Subtracting the number of voters, in this case 1, produces 1 vote for John and none for the others.

At the polling station, the voter makes a copy of any one of his three ballots including its ID number. In practice the machine verifying the ballots would perform this task automatically based on the voter's free choice of one of the ballots. Then, all three original ballots are dropped into the ballot box. The voter keeps the one copy as a receipt.

At the end of the election, all ballots are published. Since each ballot has a unique identifier, each voter may verify that his votes were counted by searching for the identifier on his receipt amongst the published ballots. However, because the voter selects which of his ballots he receives as a receipt, he can arrange for his receipt to bear any combination of markings. Thus voters cannot prove to another party who they voted for, eliminating vote-selling, coercion, etc. using this receipt.

With reference to a given set of objects, a unique identifier (UID) is any identifier which is guaranteed to be unique among all identifiers used for those objects and for a specific purpose. The concept have been formalized early in Computer science and Information systems, in general associating it to an atomic data type.

There is no indication on the ballots themselves which one was copied to make a receipt. Thus if at some point a ballot were 'lost' or maliciously discarded, there is a 1/3 chance that this would be the receipt ballot. A vigilant voter could detect this loss.

Rivest discusses other benefits and flaws in his paper. [1] In particular it is not suited for ranked preference voting. A field test has found ThreeBallot to have significant privacy, security, and usability problems, as well as implementation pitfalls. [2] [3] [4] [5]

Broken Encryption

The encryption system used in the ThreeBallot was broken by a correlation attack devised by Charlie Strauss [4] who also showed how it could be used to prove how you voted. [3] While the ThreeBallot is secure if there is only one yes/no question on the ballot, Strauss observed that it is not secure when there are multiple questions, including the case of a single race with many candidates from which to choose. His attack exploited the fact that not every combination of 3 ballots form a valid triple: proposed triples with 3 or 0 votes cast in any row on the ballot (not just one race of interest) can be rejected since those ballots could not be from the same voter. Likewise proposed trines resulting in a vote for more than one candidate in any race can be rejected. Since there are exponentially more possible vote patterns than there are ballots cast in a typical precinct (or even people in the world), statistically most of the ballots cast can be trined uniquely for sufficiently long ballots. [4] Typically, 90% of ballots can be reconstructed on ballots with just 11 to 17 questions. [5] This likely allows a voter's votes to be known by anyone with the receipt. Moreover, even without a receipt it leaks information that could discredit a voter's claimed candidate selections. [3] Consequently, a voter conspiring to prove their vote (for money, coercion, or posterity) could mark all the ballots in a previously agreed unusual pattern that could later prove to a third party if the agreement was kept (even without seeing the receipt). [3] In either case the veil of the secret ballot is pierced and traceable to the ID number on the receipt.

Revised ThreeBallot

Rivest later acknowledged this logic error in the original concept, [1] and revised the RFC schema in his final publication to require tearing off each row (each yes/no) individually (destroying the correlation of the questions) and also having unique tracking numbers on each mark on each ballot (not just one ID for each column ballot). While this did restore the unbreakable aspect of the scheme, the proliferation of receipts (one per row) and chopped ballots rendered the mechanics of processing the votes or for a voter reviewing a receipt, significantly complex, thus undermining its intended simplicity. [1] An electronic version addressing the paper-ballot implementation and usability problems was proposed by Costa, et al. [6]

Request for Comments (RFC), in information and communications technology, is a type of text document from the technology community. An RFC document may come from many bodies including from the Internet Engineering Task Force (IETF), the Internet Research Task Force (IRTF), the Internet Architecture Board (IAB), or from independent authors. The RFC system is supported by the Internet Society (ISOC).

See also

Related Research Articles

Single transferable vote Proportional representation voting system

The single transferable vote (STV) is a voting system designed to achieve proportional representation through ranked voting in multi-seat organizations or constituencies. Under STV, an elector (voter) has a single vote that is initially allocated to their most preferred candidate. Votes are totalled, and a quota derived. If their candidate achieves the quota, they are elected and in some STV systems any surplus vote is transferred to other candidates in proportion to the voters' stated preferences. If more candidates than seats remain, the bottom candidate is eliminated with their votes being transferred to other candidates as determined by the voters' stated preferences. These elections and eliminations, and vote transfers if applicable, continue until there are only as many candidates as there are unfilled seats. The specific method of transferring votes varies in different systems.

Voting method for a group such as a meeting or an electorate to make a decision or express an opinion

Voting is a method for a group, such as a meeting or an electorate, in order to make a collective decision or express an opinion usually following discussions, debates or election campaigns. Democracies elect holders of high office by voting. Residents of a place represented by an elected official are called "constituents", and those constituents who cast a ballot for their chosen candidate are called "voters". There are different systems for collecting votes.

A ballot is a device used to cast votes in an election, and may be a piece of paper or a small ball used in secret voting. It was originally a small ball used to record decisions made by voters.

A voting machine is a machine used to register and tabulate votes. The first voting machines were mechanical but it is increasingly more common to use electronic voting machines. Traditionally, a voting machine has been defined by the mechanism the system uses to cast votes and further categorized by the location where the system tabulates the votes.

Electronic voting is voting that uses electronic means to either aid or take care of casting and counting votes.

Electronic voting in India component of Indian electoral system

Electronic Voting is the standard means of conducting elections using Electronic Voting Machines, sometimes called "EVMs" in India. The use of EVMs and electronic voting was developed and tested by the state-owned Electronics Corporation of India and Bharat Electronics in the 1990s. They were introduced in Indian elections between 1998 and 2001, in a phased manner. The electronic voting machines have been used in all general and state assembly elections of India since 2004.

Voter verifiable paper audit trail (VVPAT) or verifiable paper record (VPR) is a method of providing feedback to voters using a ballotless voting system. A VVPAT is intended as an independent verification system for voting machines designed to allow voters to verify that their vote was cast correctly, to detect possible election fraud or malfunction, and to provide a means to audit the stored electronic results. It contains the name of the candidate and symbol of the party/individual candidate.

Postal voting voting, election, ballot papers, distributed to electors or returned by post, mail

Postal voting is voting in an election whereby ballot papers are distributed to electors or returned by post, in contrast to electors voting in person at a polling station or electronically via an electronic voting system. Historically, postal votes must be distributed and placed in return mail before the scheduled election day, it is sometimes referred to as a form of early voting. It can also be used as an absentee ballot. However, in recent times the model in the US has morphed, in municipalities that use postal voting exclusively, to be one of ballots being mailed out to voters, but the return method taking on alternatives of return by mail or dropping off the ballot in person via secure drop boxes and/or voting centers.

India is a federation with a parliamentary system governed under the Constitution of India, which defines the power distribution among the central government and the states.

Donkey vote vote in a ranked preferential voting system in which consecutive numbers are listed in the ballot order

A donkey vote is a ballot cast in an election that uses a preference voting system, where a voter is permitted or required to rank candidates on the ballot paper, and ranks them based on the order they appear on the ballot paper. The voter that votes in this manner is referred to as a donkey voter.

The idea of having electronic voting in Estonia gained popularity in 2001 with the "e-minded" coalition government. Estonia became the first nation to hold legally binding general elections over the Internet with their pilot project for the municipal elections in 2005. The electronic voting system withstood the test of reality and was declared a success by Estonian election officials. The Estonian parliamentary election in 2007 also used internet voting, another world first.

Punchscan is an optical scan vote counting system invented by cryptographer David Chaum. Punchscan is designed to offer integrity, privacy, and transparency. The system is voter-verifiable, provides an end-to-end (E2E) audit mechanism, and issues a ballot receipt to each voter. The system won grand prize at the 2007 University Voting Systems Competition.

An optical scan voting system is an electronic voting system and uses an optical scanner to read marked paper ballots and tally the results.

The term "software independence" (SI) was coined by Dr. Ron Rivest and NIST researcher John Wack. A software independent voting machine is one whose tabulation record does not rely solely on software. The goal of an SI system is to definitively determine whether all votes were recorded legitimately or in error.

Prêt à Voter is an E2E voting system devised by Peter Ryan of the University of Luxembourg. It aims to provide guarantees of accuracy of the count and ballot privacy that are independent of software, hardware etc. Assurance of accuracy flows from maximal transparency of the process, consistent with maintaining ballot privacy. In particular, Prêt à Voter enables voters to confirm that their vote is accurately included in the count whilst avoiding dangers of coercion or vote buying.

An election recount is a repeat tabulation of votes cast in an election that is used to determine the correctness of an initial count. Recounts will often take place in the event that the initial vote tally during an election is extremely close. Election recounts will often result in changes in contest tallies. Errors can be found or introduced from human factors, such as transcription errors, or machine errors, such as misreads of paper ballots. Alternately, tallies may change because of a reinterpretation of voter intent.

Scantegrity is a security enhancement for optical scan voting systems, providing such systems with end-to-end (E2E) verifiability of election results. It uses confirmation codes to allow a voter to prove to themselves that their ballot is included unmodified in the final tally. The codes are privacy-preserving and offer no proof of which candidate a voter voted for. Receipts can be safely shown without compromising ballot secrecy.

Bingo voting is an electronic voting scheme for transparent, secure, end-to-end auditable elections. It was introduced in 2007 by Jens-Matthias Bohli, Jörn Müller-Quade, and Stefan Röhrich at the Institute of Cryptography and Security (IKS) of the Karlsruhe Institute of Technology (KIT).

Verified Voting Foundation U.S. advocacy organization that catalogs voting equipment used in each state

The Verified Voting Foundation is an non-governmental, nonpartisan organization founded in 2003 by David L. Dill, a computer scientist from Stanford University, designed to preserve the democratic process with modern day voting advancements. Dill’s educational nonprofit 501(c)(3) organization has grown quickly since its founding and seeks to represent concerned citizens who are hesitant about electronic paperless voting. The Verified Voting Foundation volunteers act as lobbyists, educators, and leaders who promote a secure voting environment by the means of paper voting with a tangible receipt for each vote. They do this by influencing election officials and civilians at every level of government to closely monitor elections in the United States. As well, the Verified Voting Foundation is in charge of a database that contains "voting system information" and "best practices"; this information about the electoral process and voting equipment is available to the public online. The role of the Verified Voting Foundation has expanded as various ballot mechanisms have emerged in the United States. The 2000 and 2016 Presidential elections have contributed to this foundation's role because citizens and officials were questioning voter security and ballot counts after both elections.

References

  1. 1 2 3 Ronald L. Rivest (2006). "The ThreeBallot Voting System" (PDF). Retrieved 2007-01-16.Cite journal requires |journal= (help)
  2. Jones, Harvey; Jason Juang, and Greg Belote (2006). "Three Ballot in the Field" 6.857 class project, MIT. Reported in "ThreeBallot" tested by MIT students, December 2006.
  3. 1 2 3 4 Charlie E. M. Strauss (2006). "The Trouble with Triples Part 1" (PDF). Retrieved 2015-04-16.Cite journal requires |journal= (help)
  4. 1 2 3 Charlie E. M. Strauss (2006). "The Trouble with Triples Part 2" (PDF). Retrieved 2015-04-16.Cite journal requires |journal= (help)
  5. 1 2 Henry, K.; Stinson, D.R.; Sui, J. (2009). "The effectiveness of receipt-based attacks on threeballot". IEEE Transactions on Information Forensics and Security. 4 (4): 699–707. doi:10.1109/TIFS.2009.2031914.
  6. Costa, R.G.; Santin, A.O.; Maziero, C.A. (2008). "A Three Ballot Based Secure Electronic Voting System". IEEE Security & Privacy Magazine. 6 (3): 14–21. CiteSeerX   10.1.1.180.4126 . doi:10.1109/msp.2008.56.