Close elections lead to vociferous accusations. History shows that the accusations enjoy a long life. It's widely believe for example that dead people from Chicago helped elect Kennedy in 1960. Roll forward to 2004 and you will hear about the possibility of rigged paperless voting machines. Whether these stories are true or not, designing a computer-based tallying program to favor one candidate over another or to allow a secret trapdoor for tampering is all too easy. Worse, very few people need be involved.

The most basic safeguard consists of paper receipts of some kind that can be put into a ballot box and counted if there is a dispute about the machine count. While a definite improvement, this is only a first step. Ballot boxes have been tampered with in the past (see Further Reading below) and may be in the future.

At the very high end of verification, David Chaum has suggested a cryptographically based solution (again, see the Further Reading below) using randomized laminated receipts, anonymizing networks and public key encryption. This puzzle explores whether a simple cryptography-free solution may provide all the basic guarantees while remaining understandable.

Let's look at the goals:

1. Every vote is counted as cast. No ballot can be replaced by a different one, whether by fraud or accident.

2. Only people who vote have their votes counted. It should not be possible to stuff ballot boxes with ghost votes.

3. Each voter can choose to preserve his or her anonymity.

4. If a voter charges fraud, he or she should be able to document that charge convincingly.

5. A voter should not normally be able to demonstrate how he or she voted (to prevent vote selling).

Now, let's look at the assumptions, some of which are based on the difficulty of organizing a conspiracy involving many people:

1. A person can vote in only one polling place. This basic assumption holds because violating it involves a large-scale conspiracy and risks prison time if people are caught.

2. People sign in as they enter the polling place, so the total number of ballots can't exceed the number of signatures.

3. Handwriting (e.g., a signature) can't be forged, at least not on a massive scale. Photocopying may reproduce colors but handwriting also changes the three-dimensional features of the writing surface.

4. If a recount ever occurs, the recounters (say, the League of Women Voters) can be trusted. There are technical workarounds to this assumption, but this is a good social assumption in practice.

As we discuss possible solutions, we will imagine that you are designing a protocol and your adversary is someone who wants to cheat.

Warm-up: Consider the following solution. Number the ballots and reprint the number on a tab separated by a perforation. The voter takes the tab upon leaving. If there is a recount, each voter can check that his or her numbered ballot is there. Does this work?

Solution to warm-up: No. Your adversary could have two sets of ballots printed having the same numbers. Actual voters' ballots could then be discarded in favor of the adversary's. The recount would have no way to detect this skullduggery.

Problem:

Suppose that ballots can be constructed with backing paper, reminiscent of carbon copies, so that if a person writes something on the ballot, his or her writing be traced onto the backing paper. The backing paper may lie behind the whole ballot or only a portion of it. It should not be possible to write directly onto the backing paper.

How might you design a ballot and what might you ask each voter to do to guarantee the five goals above in spite of an aggressive adversary. Your solution should not involve cryptography and should be easily understandable.

Further reading:

1. In Lyndon Johnson's election campaign against W. Lee Pappy O'Neil, Johnson lost partly because of ballot stuffing, according to biographer Robert Caro in his book The Path to Power (Knopf, 1982; Vintage, reissued 1990). According to Caro, Johnson won the next Senate election in 1948 by using the same tactic.

2. "Secret-Ballot Receipts: true voter-verifiable elections" by David Chaum (http://www.voterverifiable.com/article.pdf) in the January/February issue of the journal IEEE Security & Privacy, pp. 38-47.