Pattern-voting-attacks on the German general elections

For the first time, I went to the vote-counting of todays/yesterdays general election. Doing so does not imply that I don’t trust the people doing that, but that I believe it is important to do so in principle which is why I recommend that everyone does it.

Wittnessing the approach and recalling some of the discussions that we had in the cryptographic-elections-lecture that I visited last term, I recognized that an attack that was presented there, could be applied with just minor changes to this election. The attack in question is called “pattern-voting”.

Pattern-voting is an attack that (to the best of my knowledge) was first described in the context of a paper-based-scheme named “Three-Ballot”, where it is described in section 4.4 “The ‘Three-Pattern’-Attack”. To provide a short version for those who don’t want to read the paper (though I recommend to do so):

The attack now works like this:

This attack obviously does not apply to the German general-election, where you only have one vote, as otherwise the vote will be invalid. (This still allows abstention-attacks, but those are allways possible for votes that require you to go to some specific place.)

For the application of the attack to the German elections, it is important to note that every voter has two votes. One for their prefered party (second vote) and one for the representative of the voting-district (first vote), the later of which has no real effect on the power-distribution in the parliament.1

When I was at the counting today, I learned that an invalid vote on one side of the ballot does not invalidate the other side. The effect of this is, that the entire election is again open for pattern-voting: Eve demands a random selection of candidates for the first vote which is invalidated by this. If Alice complies this random selection will almost certainly result in a unique vote, allowing the second vote to be connected to her. This attack is in fact made worse by the fact that there are only very few invalid votes like that: In this election in my polling-station there were six votes where only half was valid (because the other halve was empty), I believe four of them with just a second-vote.

As a result, it would have even been sufficient to demand just two votes for the first vote with a correct second-vote to verify it in this case. With about 10 candidates for the first vote on the other hand, there are 1013 patterns that allow to identify voters. (Interessting side-note: An obscure enough combination of the vote might also allow this attack.)

The obvious conclusion to this would be to make invalid votes completely invalid (except for abstentions), which would close this attack vector. To support this, I would like to add on a personal note, that people who are to stupid to fill in a ballot paper correctly are in my opinion also too stupid to vote, so nothing of value would be lost by such a rule.

To counter everything I just wrote, it should however be enough to point out, that postal voting is allowed in Germany (which has all of the listed problems in worse and then some). The Federal Constitutional Court ruled that the generallity of the election is more important than the secrecy and verifiablity. You may think about this however you want, but practically speaking, there is nothing to suggest that the German elections are anything but a shining example for how elections should work, when you compare them to almost any other country. (Though I still stand by what I wrote here [German].)

  1. Except that winning the first vote in at least three districts disables the 5%-threshold that all parties must otherwise pass in order for their votes to be counted. This could in fact motivate the reverse attack to coerce voters in three districts to use only their first vote, so that the other votes to the party result in actual seats.