Trusting voting machines

Before New Year I attended day one of the 26th Chaos Communication Congress (link currently down), the yearly hacker convention organised by the Chaos Computer Club. One of the big topics were voting machines especially after this and this and there being a strong lobby to introduce voting machines in Germany.

Most attendants agreed that most problems could be avoided by just not using voting machines but old school paper ballots. But there were also arguments in favour especially for elections with complicated voting systems: In some local elections in Germany, the voter can cast as many votes (70 IIRC) as there are seats in the parliament she is voting for with up to three votes per candidate. Obviously this is a night mare for a manual count. The idea behind these systems is to give voters rather than parties more influence on the composition of the parliament (while maintaining proportional vote) than in list voting system used most of the time: There, the parties set up sorted lists and the voters just vote for parties determining the number of seats for each party. Then these seats are filled with the candidates from the list from the top. This effectively means that the first list positions of the big parties are not really voted for in the general election as these people will go into parliament with nearly 100% probability and only the candidates further down the list are effectively decided about by the constituency.

The obvious problem with more complicated voting systems which might have the advantage of being fairer is that they are harder to understand and consequently they have the risk of being less democratic because too many voters fail to understand them. But voting systems should be a topic of a different post and have already been a topic in the past.

I would like to discuss what you can do to increase trust in voting machines if you decided to use them.

Note that nobody claims you cannot cheat in paper elections. You can. But typically, you can only influence a few votes with reasonable effort and it is unlikely that these will have big influences, say for order N voters you only influence O(1) votes. However with voting machines there are many imaginable attacks with influence possibly O(N) votes threatening the whole election.

The problem arises from the fact that there are three goals for an election mechanism which are hard to achieve all at the same time: a) the result should be check able b) the vote should be anonymous and c) the voter should not get a receipt of his vote (to prevent vote selling). If you drop either of these criteria the whole thing becomes much easier.

The current problems with voting machines mostly come from a): The machine just claims that the result is x and there is no way of challenging or verifying it. And in addition you have no real possibility to work out what software the machine is actually running, it could just have deleted the evil subroutines or it could be more involved.

A first solution would be that the voting machine prints out the vote on an internal printer and presents it to the voter so she could check it is what she really voted but the printout remains inside the voting machine and is a checkable proof of the vote. However now, you have to make sure you do not run into conflict with anonymity as it should not be possible to later find out what was for example the 10th vote.

Here comes my small contribution to this problem: Why not have the machine prove that what it claims is the result is correct? I would propose the following procedure:

For each voting possibility (party/candidate) there is one separate machine that cannot communicate with the other machines plus there is one further separate, open machine per polling station. Before the election, in some verifiable open and random procedure a hyperplane in an M dimensional projective space is determined (M has to be larger than the total number of voters), maybe with different people contributing different shares of information that go into the selection of that hyperplane. The idea behind this procedure is that any three points determine a plane in 3-space and it does not matter which 3 points you give (as long as they are not collinear).


Then each voter is presented a random point on that hyper surface (on some electric device or printout) and she votes by inputting that point into the machine that represents her vote.

After the election, each of the machines holds the information about as many points as votes have been cast for that party/candidate. Then it announces its result (the number of votes), N_i say. The new thing is it has to prove that it has really been given this N_i votes but it can do so demonstrating that it holds the information about N_i points. For example it does it by requesting further M-1-N_i points. After obtaining these it should know the hyper surface and can show this when given one further point with one coordinate missing: From the knowledge of the hyper surface it can compute the remaining coordinate and thus showing it really holds the information from the N_i votes it claimed it received. The nice thing about this procedure is that it does not matter which N_i points it received it is only the number that matters.

Of course, this is only the bare procedure and you can wrap it with further encryption for example to make the transition of the points from the polling to the counting computers safer. Furthermore, the dimensions sould really be larger so no points are accidentally linear dependant.

And of course, this procedure only prevents the machines from claiming more votes than they actually received. There is nothing which stops them from forgetting votes. Therefore, in this system, the individual machines should be maintained by the parties whose votes they count: These would have a natural interest in not losing any votes.

But at least, this procedure makes sure no votes from one candidate are illegally transferred to another candidate by evil code in a voting machine.