Prêt à Voter
Encyclopedia
Prêt à Voter is an E2E voting system
devised by Peter Ryan of the University of Luxembourg
. It aims to provide guarantees of accuracy of the count and ballot privacy that are independent of software, hardware etc. Assurance of accuracy flows from maximal transparency of the process, consistent with maintaining ballot privacy. In particular, Prêt à Voter enables voters to confirm that their vote is accurately included in the count whilst avoiding dangers of coercion or vote buying.
The key idea behind the Prêt à Voter approach is to encode the vote using a randomized
candidate list. The randomisation of the candidate list on each ballot form ensures the secrecy of each vote. Incidentally, it also removes any bias towards the top candidate that can occur with a fixed ordering.
The value printed on the bottom of the receipt is the key to extraction of the vote. Buried cryptographically
in this value is the information needed to reconstruct the candidate order and so extract the vote encoded on the receipt. This information is encrypted with secret keys shared across a number of teller
s. Thus, only the set of tellers acting together are able to interpret the vote encoded on the receipt. No individual agent or machine involved in the election should ever be able to tie a particular voter to a particular decrypted vote.
After the election, voters (or perhaps proxies acting on their behalf) can visit the Web Bulletin Board (WBB) and confirm their receipts appear correctly. Once this is over, the tellers take over and perform anonymising mixes and decryption of the receipts. All the intermediate stages of this process are posted to the WBB and are audited later.
There are various auditing mechanisms to ensure that all the steps, the creation of the ballot forms, the mixing and decryption and so on were all performed correctly, but these are carefully designed so as not to impinge on ballot privacy.
In the booth, Anne extracts her ballot form from the envelope and makes her selection in the usual way by placing a cross in the right hand column against the candidate of choice (or, in the case of a Single Transferable Vote (STV) system for example, she marks her ranking against the candidates). For example, a vote for Asterix is given by:
Once her selection has been made, she separates the left and right hand strips along a perforation and discards the left hand strip. She is left with the right hand strip which now constitutes her privacy protected receipt, as shown in Figure 2.
Anne now exits the booth clutching her receipt, registers with an official and casts her receipt. Her receipt is placed over an optical reader or similar device that records the random value at the bottom of the strip and records in which cell her X is marked. Her original paper receipt is digitally signed and franked and returned to her to keep.
Note that because the candidate list is removed before scanning, the machine that reads the ballot paper never learns the content of the vote. This prevents (intentional or unintentional) violation of vote privacy by the scanning equipment.
. It replaces the visual cryptographic encoding the voter's choice in Chaum's scheme by the conceptually and technologically simpler candidate randomization. The Prêt à Voter idea of encoding the vote through permutations has subsequently been incorporated in Chaum's Punchscan
scheme. However Punchscan uses a permutation of indirection symbols instead of candidate names allowing it to comply with voting laws that require a specific ordering of candidates. The first implementation of Prêt à Voter, by a team led by the University of Surrey
, won Best Design, and overall second place at the 2007 University Voting Systems Competition
, after the winning team, Punchscan, uncovered a security flaw in the random number generator portion of the Prêt à Voter source code
.
, and Mark Ryan at the University of Birmingham
; it is a close collaboration with the FNR-funded SerTVS project run by Peter Ryan at the University of Luxembourg
.
End-to-end auditable voting systems
End-to-end auditable or end-to-end voter verifiable systems are voting systems with stringent integrity properties and strong tamper-resistance. E2E systems often employ cryptographic methods to craft receipts that allow voters to verify that their votes were not modified, without revealing which...
devised by Peter Ryan of the University of Luxembourg
University of Luxembourg
thumb|Campus LimpertsbergThe University of Luxembourg is the only university in Luxembourg, founded on 13 August 2003. Prior to that, there were several higher educational institutions such as the cour universitaire or the IST that offered one or two years of academic studies...
. It aims to provide guarantees of accuracy of the count and ballot privacy that are independent of software, hardware etc. Assurance of accuracy flows from maximal transparency of the process, consistent with maintaining ballot privacy. In particular, Prêt à Voter enables voters to confirm that their vote is accurately included in the count whilst avoiding dangers of coercion or vote buying.
The key idea behind the Prêt à Voter approach is to encode the vote using a randomized
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
candidate list. The randomisation of the candidate list on each ballot form ensures the secrecy of each vote. Incidentally, it also removes any bias towards the top candidate that can occur with a fixed ordering.
The value printed on the bottom of the receipt is the key to extraction of the vote. Buried cryptographically
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
in this value is the information needed to reconstruct the candidate order and so extract the vote encoded on the receipt. This information is encrypted with secret keys shared across a number of teller
Teller
Teller may refer to:* Teller * Teller , of Penn & Teller* Bank teller** Automated teller machine* Teller * Teller, Alaska* Teller County, Colorado* Teller Amendment* Teller mine...
s. Thus, only the set of tellers acting together are able to interpret the vote encoded on the receipt. No individual agent or machine involved in the election should ever be able to tie a particular voter to a particular decrypted vote.
After the election, voters (or perhaps proxies acting on their behalf) can visit the Web Bulletin Board (WBB) and confirm their receipts appear correctly. Once this is over, the tellers take over and perform anonymising mixes and decryption of the receipts. All the intermediate stages of this process are posted to the WBB and are audited later.
There are various auditing mechanisms to ensure that all the steps, the creation of the ballot forms, the mixing and decryption and so on were all performed correctly, but these are carefully designed so as not to impinge on ballot privacy.
Example
Suppose that our voter is called Anne. At the polling station, Anne chooses at random a ballot form sealed in an envelope. An example of such a form is shown below:| Candidates | Mark X |
|---|---|
| Idefix | |
| Asterix | |
| Panoramix | |
| Obelix | |
| 3994025096 |
In the booth, Anne extracts her ballot form from the envelope and makes her selection in the usual way by placing a cross in the right hand column against the candidate of choice (or, in the case of a Single Transferable Vote (STV) system for example, she marks her ranking against the candidates). For example, a vote for Asterix is given by:
| Candidates | Mark X |
|---|---|
| Idefix | |
| Asterix | X |
| Panoramix | |
| Obelix | |
| 3994025096 |
Once her selection has been made, she separates the left and right hand strips along a perforation and discards the left hand strip. She is left with the right hand strip which now constitutes her privacy protected receipt, as shown in Figure 2.
| Mark X |
|---|
| . |
| X |
| . |
| . |
| 3994025096 |
Anne now exits the booth clutching her receipt, registers with an official and casts her receipt. Her receipt is placed over an optical reader or similar device that records the random value at the bottom of the strip and records in which cell her X is marked. Her original paper receipt is digitally signed and franked and returned to her to keep.
Note that because the candidate list is removed before scanning, the machine that reads the ballot paper never learns the content of the vote. This prevents (intentional or unintentional) violation of vote privacy by the scanning equipment.
Origin
Prêt à Voter was inspired by the earlier, voter-verifiable scheme by David ChaumDavid Chaum
David Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
. It replaces the visual cryptographic encoding the voter's choice in Chaum's scheme by the conceptually and technologically simpler candidate randomization. The Prêt à Voter idea of encoding the vote through permutations has subsequently been incorporated in Chaum's Punchscan
Punchscan
Punchscan is an optical scan vote counting system invented by cryptographer David Chaum. Punchscan is designed to offer integrity, privacy, and transparency. The system is voter-verifiable, provides an end-to-end audit mechanism, and issues a ballot receipt to each voter...
scheme. However Punchscan uses a permutation of indirection symbols instead of candidate names allowing it to comply with voting laws that require a specific ordering of candidates. The first implementation of Prêt à Voter, by a team led by the University of Surrey
University of Surrey
The University of Surrey is a university located within the county town of Guildford, Surrey in the South East of England. It received its charter on 9 September 1966, and was previously situated near Battersea Park in south-west London. The institution was known as Battersea College of Technology...
, won Best Design, and overall second place at the 2007 University Voting Systems Competition
University Voting Systems Competition
The University Voting Systems Competition, or VoComp is an annual competition in which teams of students design, implement, and demonstrate open-source election systems. The systems are presented to a panel of security expert judges. The winners are awarded a cash prize provided by the sponsors...
, after the winning team, Punchscan, uncovered a security flaw in the random number generator portion of the Prêt à Voter source code
.
Current development
An EPSRC-funded project, Trustworthy Voting Systems, running from April 2009 to September 2013, aims to enhance the design of Prêt à Voter in various ways, to build a full prototype implementation, and to produce mathematical proofs of the claimed security properties of Prêt à Voter. The project is being run by James Heather and Steve Schneider at the University of SurreyUniversity of Surrey
The University of Surrey is a university located within the county town of Guildford, Surrey in the South East of England. It received its charter on 9 September 1966, and was previously situated near Battersea Park in south-west London. The institution was known as Battersea College of Technology...
, and Mark Ryan at the University of Birmingham
University of Birmingham
The University of Birmingham is a British Redbrick university located in the city of Birmingham, England. It received its royal charter in 1900 as a successor to Birmingham Medical School and Mason Science College . Birmingham was the first Redbrick university to gain a charter and thus...
; it is a close collaboration with the FNR-funded SerTVS project run by Peter Ryan at the University of Luxembourg
University of Luxembourg
thumb|Campus LimpertsbergThe University of Luxembourg is the only university in Luxembourg, founded on 13 August 2003. Prior to that, there were several higher educational institutions such as the cour universitaire or the IST that offered one or two years of academic studies...
.