Rick Carback’s Blog

This article is cross-posted from the punchscan blog. Leave your comments over there.

As explained in part 1, there are numerous ways for a voter to violate the principle of a secret ballot. In this post we discuss identifying marks (IMs). Such marks occupy a middle ground because the voter may or may not knowingly be giving away his identity.

Many states make IMs on ballots illegal but they rarely give a clear definition. In some cases it means serial numbers. In others it means writing outside of acceptable spaces. For our purposes, the definition of an IM is anything on the ballot that could potentially identify a voter after her ballot has been cast. As far as I know, only a small subset of such IMs could be considered illegal under most laws.

Simple Identifying Marks

Simple IMs are obvious and generally require voter complicity. These include marks that would generally be considered illegal under an IM law, such as arbitrarily signing your name or writing your address on the ballot.

Because they are legal, write-in candidate slots are the worst kind of simple IM. Voter’s can easily identify their ballots by voting for an agreed upon candidate. It might also be possible to identify voters through a handwriting recognition program (unlikely at this point, but possible in the future).

Serial numbers can also be an IM. If the voter knows the serial number, she can write it down and tell people what it is. This is easy to fix, however, by making the serial number unreadable to the voter, or adding said serial numbers after the voter casts her vote. Some places have serial numbers on ballots that are removed when casting a ballot.

Covert Identifying Marks With Voter Cooperation

There are endless possibilities for IMs when the voter cooperates. A voter could mark her ballot in a specific way. In an optical scan system the voter could make little flags on the circled choices. Since some people will do this accidentally (but not in a specific pattern), it is hard to detect. Some optical scan systems make voters draw an arrow, and a voter could do the same thing by drawing predictably crooked arrows.

Marking patterns are not the only way to make identifying marks. Voters could make creases in the paper. The coercer could give the voter a particular marking device (and it could be invisible except under blacklight). The other end of the pen used for marking could make a barely visible indentation in the paper. A particular colored grease could be put on the voter’s hands as they are using the ballot. The voter could write something on the other side of the ballot that is not checked by the scanner.

IMs without Voter Cooperation

As in the write-ins example, it is possible to identify voter’s choices without their knowledge. The attack I am most familiar with can be done with lever machines and grease. Levers for the candidates are marked with various colors of grease or ink. Voter’s who vote for those candidates must pull on the levers, and they will unwittingly get the grease on their hands. As the voter leaves the polling place, the attacker shakes her hand, and he can check the transfer to see how the voter voted.

The opposite of the grease attack is also possible. A voter could shake hands with the attacker before she votes, and the attacker could identify the ballot after the election by checking for grease. There’s also genetic material and finger prints on the ballot. A sophisticated attacker could scan all the ballots and identify voters if he knew their DNA or fingerprints (again, this is something that is probably not possible now, but might be in the future).

On absentee ballots, voters are required to sign the envelope that contains the ballot. Pressure on the envelope could transfer the signature to the ballot. Of course, if an attacker controls the receipt of the absentee ballots, he can get the identity anyway. Likewise, if an attacker has a poll worker on his side, the poll worker could put identifying marks on the ballot during casting time by helping the voter put the ballot into the ballot box.

Defeating IM Attacks

Unfortunately, there are no easy answers here for traditional paper systems, and as technology gets more powerful the situation gets worse. You can’t detect all IMs before casting without violating voter privacy, but you might be able to get a machine to do it in a limited way.

One way to prevent IM would be to create a machine that makes a pristine copy of the ballot and destroys the other copy. Only the valid marks would be transferred to the new copy, and any identifying marks would not. The problem here, though, is that voters might not always check the copy very carefully before casting their ballots.

As with PV, DREs mostly avoid this problem, because the voter doesn’t have the opportunity to make IMs. However, the logging might still make it possible, particularly if it records interaction with the machine (e.g. how the voter moves through the ballot, or when the voter marks and unmarks candidates). Even simply storing the choices in order could identify voter choices if you correlated it with poll book data, and I remember a story of this being done successfully in Ohio. You might also be able to do the grease attack, if you could make the grease undetectable. As we’ll see in part 3, surveillance is much easier on DREs, too.

E2E systems, again, do a great job solving these problems. That’s because the ballot you submit, the receipt, is public knowledge. That you put identifying information on it matters a lot less, because a copy is made without those marks and posted online then you walk out with what you used to vote.

Stay tuned for part 3, surveillance, next week.

Special thanks to Taral for proofing this week.

This article is cross-posted from the punchscan blog. Leave your comments over there.

We rely on the secret ballot to prevent vote selling and voter intimidation, but the “secret” ballot isn’t always very secret. In this post I will discuss a problem that very few people know about or understand—one that allows us to give ourselves away using the very choices we make!

The problem is called pattern voting (PV), and it occurs when there are enough choices on a ballot to allow voters to identify themselves using a predetermined voting pattern. Whether or not this is possible is a function of the the number of unique choices on the ballot, the number of voters, and how ballots are counted.

The simplest PV example is an election with one voter. That voter identifies her choices simply by voting, but more realistic scenarios are simple to construct. Consider an election with 10 voters and 3 races with 2 candidates each. Assuming a two-party system, let us say the choices for each race are the democrat (D), republican(R), or no vote (N). If voters follow the rules, this situation leads to the following 27 possible voting patterns:

DDD, DDR, DDN, DRD, DRR, DRN, DND, DNR, DNN, RDD, RDR, RDN, RRD, RRR, RRN, RND, RNR, RNN, NDD, NDR, NDN, NRD, NRR, NRN, NND, NNR, NNN

This is simply a permutation with repetition (3^3). To identify a voter, all that is necessary is to agree before the election on an unlikely voting combination. Up to 9 voters could vote for the same candidate in a select race using unique patterns between them.

As a coercer or vote buyer, all I need to do is give the voter a unique combination (e.g. DNR), and look for that pattern in the ballots during counting or whenever they become publicly available. The voter can either vote the way I told her, guaranteeing that unique pattern in the output, or vote the way she wants hoping the pattern will appear anyway.

The chance of the latter happening is pretty low given the number of voters. Assuming each voter votes randomly, there is less than a 30% ((1-(26/27)^9), see the birthday paradox) chance that a random voter will share the same vote as the coerced voter.

The worst part about this situation is that what I gave above is a best case scenario. Chances decrease if the other voters do not vote randomly, are also being coerced, or do not follow the rules. Unless there’s a particularly bad or good candidate, the likely patterns are straight party (DDD or RRR).

Pattern Voting on a Real Ballot

To make this seem more real, I decided to take Maryland’s 2006 sample ballot I got and calculate the number of unique patterns you could make on it. Note that Maryland used DREs w/out VVPAT, so this is not directly applicable, but it does point out a potential problem when we switch back to optical scan.

There are 30 contests on this ballot. 16 of them have 2 options or 3 choices (yes/no/none), yielding 3^16 patterns. 3 of the races are “choose x” elections, for which the logic is explained in the next section. The rest of the races are detailed below (assuming voters follow the rules):

• Governor: 6 patterns
• Comptroller: 4
• AG: 4
• US Senator: 5
• District 3 Congressional Rep: 5
• State Senator: 4
• House of Delegates (vote for 2 of 6): C(6, 2)+C(6,1)+C(6,0) = 15+6+1 = 22
• County Executive: 4
• County Council District 1: 4
• Circuit Court Judge (vote for 4 of 8): C(8, 4)+C(8,3)+C(8,2)+C(8,1)+C(8,0) = 70 + 56 + 28 + 8 + 1 = 163
• States Attorney: 4
• Circuit Court Clerk: 4
• Judge of the Orphans Court (vote for 3 of 9): C(9,3)+C(9,2)+C(9,1)+C(9,0) = 84 + 36 + 9 + 1 = 130
• Sheriff: 4

To get the total number of patterns, we multiply it all together:

3^16*6*4*4*5*5*4*22*4*4*163*4*4*130*4 = 1.97271752×10^20 = 197,271,752,498,675,712,000

There are only 5,615,727 people in Maryland, and fewer in the county. Not all of these people are registered to vote. If you counted at each polling place, the numbers would be noticeably worse. Also remember that this is a conservative number. You could easily sell over half the ballot and have plenty of patterns left over!

Calculating Your Ballot’s Secrecy

It’s not too hard. Each race has a certain number of choices, and all you have to do is calculate these numbers and multiply them together. If you want to see the number of unique choices after targeting a specific race, for 1 choice election methods you remove that race from the multiplication. For rank choices, n out of m, or range/approval voting you simply remove the candidate you want to win from the calculation.

Below is a guide to help you figure out how many unique patterns appear on your ballot. n is the number of candidates in the election, r is the range or number of choices you can make.

• Choose 1: n+1
• Choose r: sum(C(n,r), 0, r) — this can express choose 1, too.
• Approval: 2^n
• Range: (r+1)^n — this can also express approval
• Ranked Choice: P(n,r) ==> n!/(n-r)!

Of course, this is assuming the voters follow the rules. Otherwise, the answer is 2^(number of dots) (because each dot can either be chosen or not). You can see wikipedia’s combinatorics page for more.

Fighting the Pattern Vote

The bad news is that few people pay attention to this problem, but the good news is that it can be mitigated. To defeat pattern voting, you have to reduce the number of choices that are associated with each other. Except for Ranked Choice, which is special, the key is treating each race separately, and in some election methods you need to treat each candidate separately. This is (sometimes) easier said than done.

In paper ballot systems you have a few choices. You could keep the ballots secret, and use only trusted counters (machines or people). You could have one ballot per race. You could also have a machine that cuts ballots after they are used. DREs w/ VVPAT would need a different mechanism than a paper rolltape to work. Because DREs w/out VVPAT can report results in aggregate, they avoid the PV problem.

As far as I know, every E2E system can handle PV, and some can handle PV with ranked choice. My colleague Stefan Popoveniuc wrote a paper about how this is accomplished in Punchscan and Scantegrity.

The problem with ranked choice is that you can’t hide the relationship between rankings. You need to know it to do the counting. In this scenario, the only choice for traditional systems is secret counting. Digital systems have the possibility of zero knowledge proofs to prove that the counting was correct, however.

That’s it for part 1 of this series. Part 2 will be on the effect of identifying marks (including write-ins and serial numbers), Part 3 will be on surveillance.

Special thanks to my proof readers: Taral, Emily, Jeremy, Scott, and Ben.