Previously in this blog, I have mentioned that cryptographers designed algorithms allowing us to conceal messages without the use of a computer, like Solitaire. Although message privacy is the first subject that comes into everyone’s mind when talking about cryptography, it has many other applications, one of them being the design of secure voting systems. In this post, I will talk about ThreeBallot voting system, a system designed by Ronald Rivest (the R in RSA) which aims at creating a secure voting protocol entirely based (almost entirely) on paper ballots.

End-to-end auditable voting systems

Before we start taking a look at ThreeBallot, we need to summarize the objectives of cryptographic voting systems. In general, cryptographic voting systems aims at being end-to-end auditable, which means two things:

• Anyone can proceed to a recount
• Every voter has a way to know if their vote was counted

This second property is usually achieved by giving a receipt of its vote to the voter. However, this receipt should not contain enough information to allow an attacker to breach the privacy of the vote, as each vote must remain secret to avoid vote-buying or coercion.

Introducing the multi-ballot

The ThreeBallot system aims at solving this problem with the use of a “multi-ballot”. The multi-ballot is a voting ballot that can be split into 3 parts (one per column), all containing the list of candidates (one per row) with optical-scan checkboxes as well as a unique identifier. To vote, simply check 2 boxes on the row of the candidate you want to vote for, and 1 box on the row of each candidate you want to vote against. A ballot will be considered spoilt if all three boxes for a candidate are checked, or none for another candidate.

The validity of the ballot will need to be checked (by machine) before being split into 3 separate ballots. The voter will then chose which parts of the ballot to be used as a receipt and receive a printed copy of it, before casting the 3 ballots.

When the election is complete, every ballot is displayed publicly. Anyone can proceed to a count, the results are inflated by the number of voters (one box as to be checked minimum) but the difference between candidates will remain the same. The voters can each check that their ballot appears with the correct vote and ballot ID, or contest the vote using their receipt. The voters cannot use their receipt as a proof of having voted for a candidate, as you need at least 2 of the 3 ballots to tell that, thus maintaining vote secrecy.

Limitations

Despite looking very good on paper, this voting system sadly has many practical vulnerabilities. First of all, despite being paper-based it still requires a machine to print ballots with unique identifiers, and another one to check the validity of the ballots before casting them. Both of these machines represent weak points of the system, as one of them failing would stop the election from taking place correctly. A single malfunction of the checker machine would also be enough to make the entire election null because the system doesn’t provide any way of spoiling a vote after it’s cast. Privacy breaches could also happen if these machines were to be compromised, as an attacker could record which identifiers are part of the same multi-ballot and use it to connect receipts to a full ballot.

In a follow up paper, Charlie Strauss points out that voter coercion can still happen with methods as simple as asking the voter to take a picture of their ballot using a smartphone. According to Strauss, it would also be trivial to double or triple vote by modifying the ballot after having validated it and before casting it. Voters might also give away their receipts or simply throw them in the nearest trash can, making their vote non-auditable and giving an attacker the opportunity of changing them.

In a second paper, Strauss also points out the cryptographic weakness of ThreeBallot. Since one part of the multi-ballot restricts choice on the two other parts (a candidate can’t be entirely blank or checked), the receipt is leaking information about the actual vote. Combining this information with voter bias (ie. party preference), and the publicly displayed ballots, it becomes statistically possible to link a receipt with its two other ballot parts. This is especially concerning in a situation where the attacker could coerce the voter into not only voting for a specific candidate but also checking a specific pattern on its ballot.

Legacy

Many improvements to the ThreeBallot voting system have been suggested, but as with many security protocols, improving security often comes with useability issues. This led to the slow abandonment of this protocol. However, the insights gained through ThreeBallot later allowed the creations of new secure voting systems, such as Scantegrity, which was used in actual elections by the city of Takoma Park, in 2009 and 2011.