I recently stumbled on this presentation at SSTIC 2010 on the Security of voting systems. Beyond the usual presentation on the lack of security in current electronic voting systems, Frédéric Connes presents an interesting new electronic voting protocol.

This protocol has been firstly draft in a first paper in 2008 and then in an updated second French paper for SSTIC 2010. The French slides of the SSTIC 2010 presentation are also available.

Very roughly, the main idea of this protocol is to associate a randomly generated number to each new vote. For example, if in a election amongst three people A, B, and C I vote for A, a random number 23482 is generated and associated to my vote A. Just after leaving the voting both, I also receive a paper receipt where my choice is displayed ("A 23482"). To keep the anonymity of my vote, for other options B and C a number is also printed, number chosen so that it corresponds to the choice of a previous voter. At the end of the vote, the results are published on a web site. Everybody can verify that his/her vote is correctly taken into account by checking that the random number is correctly displayed with the correct choice. One can also verify other options on the receipt. And one can also recount the tally the displayed votes and verify the election result.

This protocol ensures the good properties of a voting protocol:

  • My vote is anonymous because there is no way to associate my identity to the random number;
  • I have no way to prove that I vote for a given person because all the votes on the receipt are valid and displayed on the web site;
  • The whole vote can be audited because everybody can check that the content of his receipt is correctly displayed on the web site and recount the whole vote.

This protocol is relatively simple to understand, with no complex cryptography and with simple procedures. Of course, this protocol is far from being perfect and its author present some weak points and counter-measures:

  • the random number should be really chosen at random. The author presents two procedures to ensure this randomness. One of them is to let both the voter and the voting machine participate in the generation of the random number, but this seems very complicated to me;
  • For the first voters, there is no or few previous random numbers for the choices different that his/her choice. The author propose to generate false votes for the first voter. This has strong implication, most notably that the vote of the first voter is not really taken into account;
  • It is possible to guess the vote by knowing the receipt of one or more voters before a given voter. The author proposes the ability to generate a "completely anonymous" receipt, where the random number generated for the vote is not displayed on the receipt. This breaks the nice property to check the receipt content on the final web site;
  • The receipt should signed to ensure its integrity, so one can go into a Court to defend ones vote in case an error is detected. This signing procedure complicates a lot the voting procedure.

Another issue that the author does not mention:

  • What happens if all voters vote for the same option? Are their vote still guaranteed to be anonymous?

Overall, this voting protocol is currently not perfect but it offers very interesting ideas and properties. Probably the most interesting of it is that the protocol is "Software independent" as defined by Ronald Rivest, meaning that the correct working of the vote procedure does not need a correct software, any (or most) errors in the software can be detected.

A lot of work would be needed on this protocol:

  • An attack tree to find the possible attacks and way to counter them;
  • A probability analysis of the protocol, especially in the attack scenario where an attacker knows one or more paper receipt;
  • A detailed description of the voting procedure, giving the rationale of each step and giving actions to take in case of errors (one or more receipt is not valid, the voter does not like the random number, etc.);
  • A formal description of all the properties and invariants of the protocol.

I would like to thank Frédéric Connes for his very stimulating paper. :-)