ThreeBallot

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

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 his three ballots cancel each other out, so that he can only vote once.

Goals

The crucial advantages that the ThreeBallot system over comparable ciphered ballots is that 1) 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 (x2), even though any individual ballot section cannot reveal the candidate preference of the voter.) 2) There is no key that requires protection to maintain security (an achilles heal of many proposed systems) 3) While it requires a machine to validate the ballots before depositing them, after that the ballot record is entirely on paper and requires no additional security process beyond that afforded traditional ballots. Arguably, the most important advantage is that it's implementation is familiar looking and simple for voters to understand compared to other encryption systems.

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. Everybody can verify that extra fake "voters" were not added, and the full list of voters is publicly known.
5. 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 is a constant offset equal to the number of ballots for all the candidates which can be subtracted off the final total of all the ballots.

However, it is imperative that 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. Thus 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.

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 voters 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. 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. Rivest discusses other benefits and flaws in his paper. In particular it is not suited for ranked preference voting.

A field test has found ThreeBallot to have significant privacy, security, implementation pitfalls, and usability problems.

Broken Encryption

The encryption system used in the ThreeBallot was broken by a correlation attack devised by Charlie Strauss who also showed how it could be used to prove how you voted. 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 to choose amongst. 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. Typically, 90% of ballots can be reconstructed on ballots with just 11 to 17 questions. 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. 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). In either case the veil of the secret ballot is pierced and traceable to the ID number on the receipt.

Revised ThreeBallot

Rivest et al later acknowledged this logic error in their original concept, and revised the RFC schema in their 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. While this did restore the unbreakable aspect of the scheme, arguably 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. An electronic version addressing the paper-ballot implementation and usability problems was proposed by Costa, et al.

See also

• Electoral fraud