A recently presented the very interesting electronic voting protocol of Frédéric Connes. This protocol has some issues, most notably that is does not work for the first voter and an attack is possible, knowing the paper receipt of previous voters. https://bentobako.org/david/blog/admin/post.php?id=75&upd=1# I would like to present a modification proposal on Connes' protocol. The main idea of this proposal is to let memorize by the voting machine a pool of random numbers, use them for the first voter so that they will be correctly associated to the choice of future voters. That way, the main property of the protocol is kept, even for the first voter:

  • All vote choices on a receipt are associated to a valid vote;
  • All votes are available on the web site and can be checked.

Moreover, one should notice that if this approach is applied not only for the first voter but for latter voters, this approach could be a counter-measure against the attack that try to guess votes, knowing the paper receipt of voters.

Of course, this proposal is just an idea and a detailed analysis would be necessary to see if it really brings additional security. The probably most difficult point is that the initial pool should be empty at the end of the vote, i.e. all random numbers printed on a paper receipt should be used as a choice by other voters. Otherwise it might be possible to guess some votes. And pre-generating and storing some random numbers add some security issues that must taken into account.

Proposal details

Here is an hopefully more detailed presentation of the proposal. We assume an election amongst three people, A, B and C.

During the vote initialisation phase, three series of 10 random numbers are generated, IA1..IA10, IB1..IB10, IC1..IC10. Each one of these random number is associated to a state. Three states are possible:

  • Unused;
  • Assigned-to-vote-choice;
  • Assigned-to-other-choice.

Initially, all random numbers have state Unused.

When a new voter votes, supposing that he/her wants to vote for option A:

  • For option A, a number is chosen:
    • Either a new random number (which is stored to be reused by further voters);
    • Or either a previously generated number in IA1..IA10 in the state Assigned-to-other-choice. This number is put into the state Assigned-to-vote-choice;
  • For each option B and C, a number is chosen:
    • Either a previously used and stored number for votes B and C;
    • Or either a previously generated number in IB1..IB10 and IC1..IC10 and with the state Assigned-to-vote-choice;
    • Or either a previously generated number in IB1..IB10 and IC1..IC10 and with the state Unused. The state is put to state Assigned-to-other-choice.

Then the receipt is given to the voter as usual and the chosen option and associated number is stored for final counting.

For an initial voter, it is always possible to have random number, either a new one for his/her option A and a previously generated one for options B and C. As those two numbers are associated to state Assigned-to-other-choice, at one point in the future another voter is going to select those numbers and use it as his/her vote option, thus publishing it on the final web site and making the receipt of the initial voter perfectly valid.

In the above algorithm, the probability of selection between the different options might be not equal. The size 10 of the initial pool is chosen so that the probability of having the pool empty at the end of the vote is high. This remains to be verified.

It now remains to make a detailed presentation and analysis of the protocol and to implement it.