End-to-end auditable voting systems
Encyclopedia
End-to-end auditable or end-to-end voter verifiable (E2E) 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 candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.
systems arrive at their final vote totals by a series of steps:
Classical approaches to election integrity tended to focus on mechanisms that operated at each step on the chain from voter intent to final total. Voting is an example of a distributed system, and in general, distributed system designers have long known that such local focus may miss some vulnerabilities while over-protecting others. The alternative is to use end-to-end
measures that are designed to guard the integrity of the entire chain.
The failure of current optical scan voting systems to meet
reasonable end-to-end standards was pointed out in 2002. End-to-end coverage of election integrity frequently involves multiple stages. We expect voters to verify that they have marked their ballots as intended, we use recounts or audits to protect the step from marked ballots to ballot-box totals, and we use publication of all subtotals to allow public verification that the overall totals correctly sum the local totals.
While measures such as voter verified paper audit trails
and manual recounts increase the end-to-end coverage of our defenses, the offer only weak protection of the integrity of the physical or electronic ballot boxes. Ballots could be removed, replaced, or could have marks added to them (i.e.,to fill in undervote
d contests with votes for a desired candidate or to overvote
and spoil
votes for undesired candidates). This shortcoming motivated the development of the end-to-end auditable voting systems discussed here, sometimes referred to as E2E voting systems. These attempt to cover the entire path from voter attempt to election totals with just two measures:
Because of the importance of the right to a secret ballot
, all of the interesting E2E voting schemes also attempt to meet a third requirement, usually referred to as receipt freeness.
Some researchers argue that end-to-end auditability and receipt-freeness should be considered to be orthogonal properties. These two properties are combined in the 2005 Voluntary Voting System Guidelines
promulgated by the Election Assistance Commission
. This definition is also predominant in the academic literature.
Note that assertions regarding ballot stuffing
are not inherently addressed by the definition of E2E, although they can be externally verified by comparing the number of votes cast with the number of registered voters who voted.
proposed a solution that allows a voter to verify that the vote is cast appropriately and that the vote is accurately counted using visual cryptography
. After the voter selects their candidates, a DRE machine prints out a specially formatted version of the ballot on two transparencies. When the layers are stacked, they show the human-readable vote. However, each transparency is encrypted with a form of visual cryptography
so that it alone does not reveal any information unless it is decrypted. The voter selects one layer to destroy at the poll. The DRE retains an electronic copy of the other layer and gives the physical copy as a receipt to ensure the ballot is not later changed. The system guards against changes to the voter's ballot and uses a mix-net decryption procedure to ensure that each vote is accurately counted. Sastry, Karloff and Wagner pointed out that there are issues with both of the Chaum and VoteHere cryptographic solutions.
Chaum has since developed Punchscan
, which has stronger security properties and uses simpler paper ballots. The paper ballots are voted on and then a privacy-preserving portion of the ballot is scanned by an optical scanner.
The Prêt à Voter
system, invented by Peter Ryan, uses a shuffled candidate order and a traditional mix network. As in Punchscan, the votes are made on paper ballots and a portion of the ballot is scanned.
The Scratch and Vote system, invented by Ben Adida, uses a scratch-off surface to hide cryptographic information that can be used to verify the correct printing of the ballot.
The ThreeBallot
voting protocol, invented by Ron Rivest
, was designed to provide some of the benefits of a cryptographic voting system without using cryptography. It can in principle be implemented on paper although the presented version requires an electronic verifier.
The Scantegrity
and Scantegrity II systems provide E2E properties, however instead of being a replacement of the entire voting system, as is the case in all the proceeding examples, it works as an add-on for existing optical scan voting systems. Scantegrity II employs invisible ink
and was developed by a team that included Chaum, Rivest, and Ryan. The city of Takoma Park, Maryland
used Scantegrity II for its November, 2009 election.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
to craft receipts that allow voters to verify that their votes were not modified, without revealing which candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.
Overview
Electronic votingElectronic voting
Electronic voting is a term encompassing several different types of voting, embracing both electronic means of casting a vote and electronic means of counting votes....
systems arrive at their final vote totals by a series of steps:
- each voter has an original intent,
- voters express their intent on physical ballots (whether transient, as on the display of a DRE voting machineDRE voting machineA direct-recording electronic voting machine records votes by means of a ballot display provided with mechanical or electro-optical components that can be activated by the voter ; that processes data by means of a computer program; and that records voting data and ballot images in memory components...
, or durable, as in systems with voter verifiable paper trailsVoter Verified Paper Audit TrailVoter Verified Paper Audit Trail or Verified Paper Record is intended as an independent verification system for voting machines designed to allow voters to verify that their vote was cast correctly, to detect possible election fraud or malfunction, and to provide a means to audit the stored...
), - physical ballots are represented electronically,
- electronic ballot images are collected into a ballot box,
- vote totals are computed from the electronic images, and
- where counting is conducted locally, for example, at the precinct or county level, the tallies from each local count are aggregated to produce the final tally.
Classical approaches to election integrity tended to focus on mechanisms that operated at each step on the chain from voter intent to final total. Voting is an example of a distributed system, and in general, distributed system designers have long known that such local focus may miss some vulnerabilities while over-protecting others. The alternative is to use end-to-end
End-to-end principle
The end-to-end principle is a classic design principle of computer networking which states that application specific functions ought to reside in the end hosts of a network rather than in intermediary nodes, provided they can be implemented "completely and correctly" in the end hosts...
measures that are designed to guard the integrity of the entire chain.
The failure of current optical scan voting systems to meet
reasonable end-to-end standards was pointed out in 2002. End-to-end coverage of election integrity frequently involves multiple stages. We expect voters to verify that they have marked their ballots as intended, we use recounts or audits to protect the step from marked ballots to ballot-box totals, and we use publication of all subtotals to allow public verification that the overall totals correctly sum the local totals.
While measures such as voter verified paper audit trails
Voter Verified Paper Audit Trail
Voter Verified Paper Audit Trail or Verified Paper Record is intended as an independent verification system for voting machines designed to allow voters to verify that their vote was cast correctly, to detect possible election fraud or malfunction, and to provide a means to audit the stored...
and manual recounts increase the end-to-end coverage of our defenses, the offer only weak protection of the integrity of the physical or electronic ballot boxes. Ballots could be removed, replaced, or could have marks added to them (i.e.,to fill in undervote
Undervote
An undervote occurs when the number of choices selected by a voter in a contest is less thanthe maximum number allowed for that contest or when no selection is made for a singlechoice contest....
d contests with votes for a desired candidate or to overvote
Overvote
An overvote occurs when one votes for more than the maximum number of selections allowed in a contest. The result is a spoilt vote which is not included in the final tally....
and spoil
Spoilt vote
'Bold text'In voting, a ballot is considered to be spoilt, spoiled, void, null, informal or stray if it is regarded by the election authorities to be invalid and thus not included in the tally during vote counting. This may be done accidentally or deliberately...
votes for undesired candidates). This shortcoming motivated the development of the end-to-end auditable voting systems discussed here, sometimes referred to as E2E voting systems. These attempt to cover the entire path from voter attempt to election totals with just two measures:
- Voter auditing, by which any voter may check that his or her ballot is correctly included in the electronic ballot box, and
- Universal verifiability, by which anyone may determine that all of the ballots in the box have been correctly counted.
Because of the importance of the right to a secret ballot
Secret ballot
The secret ballot is a voting method in which a voter's choices in an election or a referendum are anonymous. The key aim is to ensure the voter records a sincere choice by forestalling attempts to influence the voter by intimidation or bribery. The system is one means of achieving the goal of...
, all of the interesting E2E voting schemes also attempt to meet a third requirement, usually referred to as receipt freeness.
- No voter can demonstrate how he or she voted to any third party.
Some researchers argue that end-to-end auditability and receipt-freeness should be considered to be orthogonal properties. These two properties are combined in the 2005 Voluntary Voting System Guidelines
Voluntary Voting System Guidelines
The Voluntary Voting System Guidelines are guidelines adopted by the United States Election Assistance Commission for the certification of voting systems...
promulgated by the Election Assistance Commission
Election Assistance Commission
The Election Assistance Commission is an independent agency of the United States government created by the Help America Vote Act of 2002 . The Commission serves as a national clearinghouse and resource of information regarding election administration...
. This definition is also predominant in the academic literature.
Note that assertions regarding ballot stuffing
Ballot stuffing
Ballot stuffing is the illegal act of one person submitting multiple ballots during a vote in which only one ballot per person is permitted. The name originates from the earliest days of this practice in which people literally did stuff more than one ballot in a ballot box at the same time...
are not inherently addressed by the definition of E2E, although they can be externally verified by comparing the number of votes cast with the number of registered voters who voted.
E2E Systems
In 2004, 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...
proposed a solution that allows a voter to verify that the vote is cast appropriately and that the vote is accurately counted using visual cryptography
Visual cryptography
Visual cryptography is a cryptographic technique which allows visual information to be encrypted in such a way that the decryption can be performed by the human visual system, without the aid of computers....
. After the voter selects their candidates, a DRE machine prints out a specially formatted version of the ballot on two transparencies. When the layers are stacked, they show the human-readable vote. However, each transparency is encrypted with a form of visual cryptography
Visual cryptography
Visual cryptography is a cryptographic technique which allows visual information to be encrypted in such a way that the decryption can be performed by the human visual system, without the aid of computers....
so that it alone does not reveal any information unless it is decrypted. The voter selects one layer to destroy at the poll. The DRE retains an electronic copy of the other layer and gives the physical copy as a receipt to ensure the ballot is not later changed. The system guards against changes to the voter's ballot and uses a mix-net decryption procedure to ensure that each vote is accurately counted. Sastry, Karloff and Wagner pointed out that there are issues with both of the Chaum and VoteHere cryptographic solutions.
Chaum has since developed 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...
, which has stronger security properties and uses simpler paper ballots. The paper ballots are voted on and then a privacy-preserving portion of the ballot is scanned by an optical scanner.
The Prêt à Voter
Prêt à Voter
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...
system, invented by Peter Ryan, uses a shuffled candidate order and a traditional mix network. As in Punchscan, the votes are made on paper ballots and a portion of the ballot is scanned.
The Scratch and Vote system, invented by Ben Adida, uses a scratch-off surface to hide cryptographic information that can be used to verify the correct printing of the ballot.
The ThreeBallot
ThreeBallot
ThreeBallot is a voting protocol invented by Ron Rivest.ThreeBallot is an end-to-end auditable voting system that can in principle be implemented on paper. The goal in its design was to provide some of the benefits of a cryptographic voting system without using cryptography.A vote cannot be both...
voting protocol, invented by Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
, was designed to provide some of the benefits of a cryptographic voting system without using cryptography. It can in principle be implemented on paper although the presented version requires an electronic verifier.
The Scantegrity
Scantegrity
Scantegrity is a security enhancement for optical scan voting systems, providing such systems with end-to-end verifiability of election results. It uses confirmation codes to allow a voter to prove to themselves that their ballot is included unmodified in the final tally. The codes are...
and Scantegrity II systems provide E2E properties, however instead of being a replacement of the entire voting system, as is the case in all the proceeding examples, it works as an add-on for existing optical scan voting systems. Scantegrity II employs invisible ink
Invisible ink
Invisible ink, also known as security ink, is a substance used for writing, which is invisible either on application or soon thereafter, and which later on can be made visible by some means. Invisible ink is one form of steganography, and it has been used in espionage...
and was developed by a team that included Chaum, Rivest, and Ryan. The city of Takoma Park, Maryland
Takoma Park, Maryland
Takoma Park is a city in Montgomery County, Maryland, United States. It is a suburb of Washington, D.C., and part of the Washington Metropolitan Area. Founded in 1883 and incorporated in 1890, Takoma Park, informally called "Azalea City," is a Tree City USA and a nuclear-free zone...
used Scantegrity II for its November, 2009 election.
Examples
- Helios
- Prêt à VoterPrêt à VoterPrê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...
- PunchscanPunchscanPunchscan 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...
- ScantegrityScantegrityScantegrity is a security enhancement for optical scan voting systems, providing such systems with end-to-end verifiability of election results. It uses confirmation codes to allow a voter to prove to themselves that their ballot is included unmodified in the final tally. The codes are...
- ThreeBallotThreeBallotThreeBallot is a voting protocol invented by Ron Rivest.ThreeBallot is an end-to-end auditable voting system that can in principle be implemented on paper. The goal in its design was to provide some of the benefits of a cryptographic voting system without using cryptography.A vote cannot be both...
- Bingo VotingBingo votingBingo voting is a cryptographic protocol for transparent, secure end-to-end auditable electronic voting. It was introduced in 2008 by German researchers.The following is a simplified description of the process....
External links
- Verifying Elections with Cryptography — Video of Ben Adida's 90-minute tech talk
- Helios: Web-based Open-Audit Voting — PDF describing Ben Adida's Helios web-site
- Helios Voting System web-site