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):

• Voting for Three-Ballot involves filling out three ballot papers. Every party has to get one vote on one of the three papers.
• The party you want to vote for get’s an additional vote on a second paper.
• In the end all votes are counted and afterwards the number of voters are subtracted from the results of all parties, giving all parties their real results.
• (I am skipping parts like “how to ensure that everyone votes for one party only?”)

The attack now works like this:

• Eve want’s to coerce/pay/… Alice into voting for some party X.
• Eve tells Alice three random patterns such that they result in Eves prevered vote.
• If Alice votes for them, her ballot-papers will show up in the end-result.
• Given a sufficiently large number of parties, the likelihood for some other voter to select the exact same parties is negligable, allowing Eve to verify Alice’s vote.

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

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].)