The Prêt à Voter electronic voting system has been defined and refined in a series of academic papers. We have spent a number of months building one of the first complete implementations of the system and have concluded that those papers treat many aspects of the system on a theoretic level that are not applicable to a real world system. It appears to us that in order to define the details of the application of cryptography, mix networks and so forth a number of assumptions are made that present obstacles on the way to an implementation.

University of Surrey Students' Union Sabbatical Elections 2007

The system that we implemented was built to run the University of Surrey Students' Union (USSU) Sabbatical Elections 2007.

Special requirements

To complicate matters there were three important special requirements posed by USSU:

1. Single Transferable Vote (STV) --- The USSU elections use STV which means that each voter ranks one or more candidates on the ballot form in the order they would prefer them. In a number of rounds during the tally the weakest candidate is eliminated and the votes distributed to the next choice in the list until a candidate has gained a majority of the votes.
2. Paper trail --- USSU asked us to allow the original ballot forms to be placed in a sealed ballot box so that they may be counted by hand after the election. This was a requirement from the National Union of Students (NUS) to allow the electronic voting trial to go ahead at the University of Surrey.
3. Remote voting via web interface --- USSU was keen on using the electronic elections to encourage greater participation in the democratic process among the electorate. After initially wishing for all voting to be done through a web interface they settled on a requirement that those students on placement or otherwise unable to vote in polling stations would be allowed to apply to do so remotely.
   

Lessons

This section goes through a number of distinct lessons learnt from implementing Prêt à Voter.

Single Transferable Vote

Prêt à Voter has so far only used First Past The Post (FPTP), i.e. the simple marking of a single candidate on the form. Practically, FPTP is much easier to scan in and interpret than STV. We looked at a number of different methods of constructing the ballot form so that it could be reliably scanned in and translated into the correct electronic representation.

We initially looked at a grid where the candidates are named in permuted order on the y axis and each position, i.e. first, second, third and so on, were listed on the x axis. The voter would tick one candidate in each of the positions and this would be scanned in. We concluded that this would be too confusing for the voter.

Then we looked in depth at different ways of accepting the voter's choices through a computer based interface. This would include the ballot form being aligned onto a screen within the voting booth. On the ballot form would be printed the candidate list and a machine readable onion or serial number --- simply a bar code. The voter would then be able to on the computer drag and drop the words "first (1st)", "second (2nd)" and so forth next to each candidate on the paper candidate list. The computer in the booth would then submit to the web bulletin board the ballot form serial number together with the choices made, print a receipt and the voter could shred the candidate list.

This method seemed very promising as it would assist the voter, be accessible and in essence could be the same in the voting booth as it would be online for those voting remotely. However, in this implementation each polling station would require a number of booths, each equipped with a computer, a barcode scanner and a printer. As the USSU elections were to take place in four polling stations around campus this would require quite a lot of equipment at a fairly high cost.

We finally made experiments with a paper based ballot form where the ranking was made using a seven segment display, quite similar to that of digital clocks.  This method made it possible to have only one computer, one scanner and one printer in each polling station as the voters were able to fill out their forms in secret in booths before scanning them in. The seven segment display would aid Optical Character Recognition (OCR) of the contents of the vote. The experiments went well and we went with this choice.

As a result of this method of accepting the voter's choices into an electronic form the OCR had to be done at the time of scanning, a receipt must printed with those choices and the voter given the opportunity to check this receipt and reject it if was not the same as the intended vote. This check could be done in public as the candidate list had been removed and it was a matter of checking that the system had correctly interpreted the vote. In our implementation the voter checked the receipt and if it did not match the intended vote, the ballot form was cancelled and the voter issued another form.

Four concurrent polling stations

In order to deal with a number of concurrent polling stations where all eligible voters were able to cast their vote in either one we built a registration module which would connect to the central database and assign a particular ballot form to a particular voter. If this form would be voided or cancelled for any reason it was possible for the poll station worked manning this module to cancel the first and assign another form. The operator used the voter's University Registration Number (URN) to search for the voter and then typed in a ballot form serial number to assign the form to that voter. The result of this is that when a voter correctly identified herself at a polling station she would be able to cancel any previously cast vote and cast another, making it impossible to vote twice.

Full permutations rather than cyclic shifts

Original Prêt à Voter uses cyclic shifts and in Prêt à Voter 2006 \cite{ryan:2006} this cyclic shift makes it possible to inject the voter's choice into the onion before it is passed through the re-encryption network. As the choice is injected into the onion this means that the onions in a batch cannot be partitioned according to the attached choice. Sadly, it is not the case that the permutation that represents the voter's choice in STV can be injected into the onion. Instead this choice must pass through the mix network together with the associated onion and thus these may be partitioned according to the attached choices.

If the candidate list is only cyclicly shifted then it is possible to look at the popularity of the candidates in opinion polls and try to match this information to the choices in a receipt. If a match between the first three candidates for example is made with the voter's "1", "2" and "3" then it can be determined with high probability that the vote is for those candidates in that order.

To combat this we were not able to use cyclic shifts but had to use full permutations. This in turn meant that we could not use the re-encryption mix networks of Prêt à Voter 2006 but had to revert to the decryption mix network of original Prêt à Voter. The latter suffers both from the chain voting and the administrator knowledge problems.

Paper trail

In Prêt à Voter as defined by the papers the voter is allowed to leave with the right hand half of the ballot form as an encrypted receipt. When this half had to be left in a ballot box this meant we were required to print another receipt for the voter to take away.

The process thus became as follows:

1. The voter is assigned a ballot form
2. The voter fills out the ballot form in secret detaches the two halfs
3. The encrypted receipt is scanned
4. A receipt is printed
5. The voter checks that this receipt is correct
6. If it is correct then the voter staples the two halves back together and these are put in the ballot box

Allowing the vote to be spoilt

Something that appears to have been overlooked by many constructors of electronic voting systems is the democratic right to spoil a vote. In order not to comply when being subject to the chain voting attack for example, the voter's last resort is to void the ballot by making some mark on it or filling it out erroneously.

However, in our implementation we used OCR and had to make sure that what the machine interpreted is what the voter intended. This OCR thus had to take place immediately after the scanning of the ballot form and a receipt printed which the voter was able to check against her own ballot form half. Unfortunately this meant that the OCR software had to communicate to the voter that it had received something that did not make sense. Also, it would disregard marks outside the voting grid itself that might void the ballot form in other circumstances and only interpret the numbers within the grid.

In order to allow a voter to spoil the vote we discussed the possibility of inserting a STOP TRANSFERRING candidate in each race which whenever given the first rank by a voter would lead to the vote not being tallied. This would also be a solution to the partitioning of the votes according to the number of choices made by the voter, see another part of this report.

More than one race on a ballot paper

The USSU election for which the implementation would first be put in use had seven races: president, four vice-presidents and two referenda. Traditionally, and for the sake of simplicity, all current races have always been printed on the same ballot form. In Prêt à Voter the form consists of a candidate list to the left and a grid for the voter to insert the choice to the right. In the implementation we had to have seven such forms on a single piece of paper. Because of the small number of candidates in each race this was in fact possible.

In order to cope with this we had to add one level of abstraction: that, which popularly is a ballot form, became a ballot form paper, consisting of seven ballot forms. Each of these ballot forms would have its associated onion and so forth, but be referenced by a single serial number, that of the ballot form paper. When a voter was assigned a ballot form by a clerk this in fact meant assigning a ballot form paper. When the polling station software would submit the vote to the web bulletin board it would do so with one serial number (that of the paper) and seven permutations representing one vote in each race.

We devised the system such that when a vote was submitted in this fashion each permutation would be assigned to its ballot form in the database. In the decryption and tallying phases no reference would again be made to which paper a ballot form might have been printed on, which meant that the simplicity of original Prêt à Voter was regained in these phases.

Partition according to number of choices

Another way that the votes may be partitioned as they go through the decryption mix network is by the number of choices the voter has made. To comply with the rules of STV the voter must be able to rank any subset of all the candidates available. Some voters may prefer to give support to only one candidate while others may rank all. The batches of onion rank pairs can be partitioned according to the number of choices made. Any such information leaks have a negative impact on ballot secrecy and should be avoided.

The solution that we discussed but because of time constraints did not implement was to include a STOP TRANSFERRING candidate in the list. The voter would then make her choices and when she is finished continue ranking all the other candidates randomly, but starting with the STOP TRANSFERRING candidate. Alternatively this can be done automatically.

If the rest of the candidates are ranked randomly (but no votes are transferred to them because the STOP TRANSFERRING candidate appears before them) then the receipt will not be exactly the same as the voter filled it in. Although it is possible to explain why this is this certainly makes it less straightforward for the voter to see why the receipt encrypts her vote.