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 and Warren D. Smith 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.

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 familiarly 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 that the vote counters cheated.)
  3. Everybody can verify that 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.835126

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:

CandidateBallotNotes
123
John FooXXAny two columns marked indicates a "for" vote.
Barb BarXAny single column marked is not a "for" vote.
Bill TooX

As a result, seeing any one ballot does not tell whether 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 from the final total of all the ballots.

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:

CandidateBallotNotes
123
Andy OopsXXXNot allowed.
Elle ErrorNot 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.

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 article. [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 forms 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 whether 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]

See also

Related Research Articles

<span class="mw-page-title-main">Plurality voting</span> Type of electoral system

Plurality voting refers to electoral systems in which the candidates in an electoral district who poll more than any other are elected.

<span class="mw-page-title-main">Single transferable vote</span> Multi-winner electoral system

The single transferable vote (STV) or proportional-ranked choice voting (P-RCV), is a multi-winner electoral system in which each voter casts a single vote in the form of a ranked ballot. Voters have the option to rank candidates, and their vote may be transferred according to alternative preferences if their preferred candidate is eliminated or elected with surplus votes, so that their vote is used to elect someone they prefer over others in the running. STV aims to approach proportional representation based on votes cast in the district where it is used, so that each vote is worth about the same as another.

A voting machine is a machine used to record votes in an election without paper. 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 its mechanism, and whether the system tallies votes at each voting location, or centrally. Voting machines should not be confused with tabulating machines, which count votes done by paper ballot.

Electronic voting is voting that uses electronic means to either aid or take care of casting and counting ballots including voting country

Electoral fraud, sometimes referred to as election manipulation, voter fraud, or vote rigging, involves illegal interference with the process of an election, either by increasing the vote share of a favored candidate, depressing the vote share of rival candidates, or both. It differs from but often goes hand-in-hand with voter suppression. What exactly constitutes electoral fraud varies from country to country, though the goal is often election subversion.

Voter verifiable paper audit trail (VVPAT) or verified paper record (VPR) is a method of providing feedback to voters who use an electronic voting system. A VVPAT allows 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 and party affiliation of candidates for whom the vote has been cast. While VVPAT has gained in use in the United States compared with ballotless voting systems without it, hand-marked ballots are used by a greater proportion of jurisdictions.

<span class="mw-page-title-main">Positional voting</span> Class of ranked-choice electoral systems

Positional voting is a ranked voting electoral system in which the options or candidates receive points based on their rank position on each ballot and the one with the most points overall wins. The lower-ranked preference in any adjacent pair is generally of less value than the higher-ranked one. Although it may sometimes be weighted the same, it is never worth more. A valid progression of points or weightings may be chosen at will or it may form a mathematical sequence such as an arithmetic progression, a geometric one or a harmonic one. The set of weightings employed in an election heavily influences the rank ordering of the candidates. The steeper the initial decline in preference values with descending rank, the more polarised and less consensual the positional voting system becomes.

Electronic voting in Estonia gained popularity in 2001 with the "e-minded" coalition government. In 2005, it became the first nation to hold legally binding general elections over the Internet with their pilot project for municipal elections. Estonian election officials declared the electronic voting system a success and found that it withstood the test of real-world use.

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.

End-to-end auditable or end-to-end voter verifiable (E2E) systems are voting systems with stringent integrity properties and strong tamper resistance. E2E systems use cryptographic techniques to provide voters with receipts that allow them to verify their votes were counted as cast, without revealing which candidates a voter supported to an external party. As such, these systems are sometimes called receipt-based systems.

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.

In cryptography, homomorphic secret sharing is a type of secret sharing algorithm in which the secret is encrypted via homomorphic encryption. A homomorphism is a transformation from one algebraic structure into another of the same type so that the structure is preserved. Importantly, this means that for every kind of manipulation of the original data, there is a corresponding manipulation of the transformed data.

<span class="mw-page-title-main">Summability criterion</span>

In election science, a voting method satisfies the summability criterion if it is possible to tally election results locally by precinct, then calculate the results by adding up all the votes. More formally, the compilation or summation complexity of a voting system measures the difficulty of vote counting for individual precincts, and is equal to the smallest number of bits needed to summarize all the votes. A voting method is called summable if the number of bits grows as a polynomial function of the number of candidates.

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).

<span class="mw-page-title-main">Risk-limiting audit</span> A procedure in which post-election tabulation is audited for risk limits.

A risk-limiting audit (RLA) is a post-election tabulation auditing procedure which can limit the risk that the reported outcome in an election contest is incorrect. It generally involves (1) storing voter-verified paper ballots securely until they can be checked, and (2) manually examining a statistical sample of the paper ballots until enough evidence is gathered to meet the risk limit.

<span class="mw-page-title-main">Helios Voting</span>

Helios Voting is an open-source, web-based electronic voting system. Users can vote in elections and users can create elections. Anyone can cast a ballot; however, for the final vote to be counted, the voter's identification must be verified. Helios uses homomorphic encryption to ensure ballot secrecy.

<span class="mw-page-title-main">Postal voting in the United States</span> Overview of topic

Postal voting in the United States, also referred to as mail-in voting or vote by mail, is a form of absentee ballot in the United States. A ballot is mailed to the home of a registered voter, who fills it out and returns it by postal mail or drops it off in-person at a secure drop box or voting center. Postal voting reduces staff requirements at polling centers during an election. All-mail elections can save money, while a mix of voting options can cost more. In some states, ballots may be sent by the Postal Service without prepayment of postage.

Direct Recording Electronic with Integrity and Enforced Privacy (DRE-ip) is an End-to-End (E2E) verifiable e-voting system without involving any tallying authorities, proposed by Siamak Shahandashti and Feng Hao in 2016. It improves a previous DRE-i system by using a real-time computation strategy and providing enhanced privacy. A touch-screen based prototype of the system was trialed in the Gateshead Civic Centre polling station on 2 May 2019 during the 2019 United Kingdom local elections with positive voter feedback. A proposal that includes DRE-ip as a solution for large-scale elections was ranked 3rd place in the 2016 Economist Cybersecurity Challenge jointly organized by The Economist and Kaspersky Lab.

References

  1. 1 2 3 Ronald L. Rivest (2006). "The ThreeBallot Voting System" (PDF). Retrieved 2007-01-16.{{cite journal}}: 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}}: 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}}: 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. S2CID   10717380.
  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. S2CID   5959774.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.