End-to-end auditable voting systems
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 counted as cast, without revealing which candidates were voted for. As such, these systems are sometimes referred to as receipt-based systems.
Electronic voting systems arrive at their final vote totals by a series of steps:
- each voter has an original intent,
- voters express their intent on ballots (whether transient, as on the display of a DRE voting machine, or durable, as in systems with voter verifiable paper trails),
- the ballots are interpreted, to generate electronic cast vote records,
- cast vote records are tallied, generating totals
- where counting is conducted locally, for example, at the precinct or county level, the results from each local level are combined 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 measures that are designed to guard the integrity of the entire chain.
Comprehensive coverage of election integrity frequently involves multiple stages. Voters are expected 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 effectiveness of our defenses, they 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 undervoted 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:
- Individual verifiability, 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, some 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.
A researcher has argued that end-to-end auditability and receipt-freeness should be considered to be orthogonal properties. Other researchers have shown that these properties can co-exist, and these 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.
To address ballot stuffing, the following measure can be adopted:
- Eligibility verifiability, by which anyone may determine that all counted ballots were cast by registered voters.
Alternatively, assertions regarding ballot stuffing can be externally verified by comparing the number of votes cast with the number of registered voters who voted, and by auditing other aspects of the registration and ballot delivery system.
Use in elections
The STAR-Vote system was under development for Travis County, the fifth most populous county in Texas, where the state capital, Austin, is. Development ended in 2017, because no contractor was willing to bid an open-source system meeting criteria in the request for proposals.
Proposed E2E Systems
In 2004, David Chaum 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 allow the voter to confirm that the electronic ballot was 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's team subsequently 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 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 preceding 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 STAR-vote system under development for Travis County, Texas is another way to combine an E2E system with conventionally auditable paper ballots, produced in this case by a ballot marking device.
- Prêt à Voter
- Wombat Voting 
- Bingo Voting
- homomorphic secret sharing
- DRE-i (E2E verifiable e-voting without tallying authorities based on pre-computation)
- DRE-ip (E2E verifiable e-voting without tallying authorities based on real-time computation)
- J. H. Saltzer, D. P. Reed and D. D Clark, End-to-End Arguments in System Design, ACM Trans. on Computer Systems (TOCS), Vol 2, No. 4, Nov. 1984, pages 277-288
- Douglas W. Jones, End-to-End Standards for Accuracy in Paper-Based Systems, Workshop on Election Standards and Technology (alternate source), Jan 31, 2002, Washington DC.
- Douglas W. Jones, Perspectives on Electronic Voting, From Power Outages to Paper Trails (alternate source), IFES, Washington DC, 2007; pages 32-46, see particularly Figure 4, page 39.
- Douglas W. Jones, Some Problems with End-to-End Voting, position paper presented at the End-to-End Voting Systems Workshop, Oct. 13-14, 2009, Washington DC.
- B Smyth, S. Frink and M. R. Clarkson, Election Verifiability: Cryptographic Definitions and an Analysis of Helios and JCJ, Cornell's digital repository, Feb. 2017
- 2005 Voluntary Voting System Guidelines, Election Assistance Commission
- Jeremy Clark, Aleks Essex, and Carlisle Adams. On the Security of Ballot Receipts in E2E Voting Systems. IAVoSS Workshop on Trustworthy Elections 2007.
- Aleks Essex, Jeremy Clark, Richard T. Carback III, and Stefan Popoveniuc. Punchscan in Practice: An E2E Election Case Study. IAVoSS Workshop on Trustworthy Elections 2007.
- Olivier de Marneffe, Olivier Pereira and Jean-Jacques Quisquater. Simulation-Based Analysis of E2E Voting Systems. E-Voting and Identity 2007.
- Ka-Ping Yee. Building Reliable Voting Machine Software. Ph.D. Dissertation, UC Berkley, 2007.
- "The Future of Voting: End-to-End Verifiable Internet Voting - Specification and Feasibility Study - E2E-VIV Project". U.S. Vote Foundation. 2015. Retrieved 2016-09-01.
- "Pilot Study of the Scantegrity II Voting System Planned for the 2009 Takoma Park City Election" (PDF). Archived from the original (PDF) on 2011-07-19.
- Hardesty, Larry. "Cryptographic voting debuts". MIT news. Retrieved 2009-11-30.
- Bell, Susan; et al. (2013-08-01). "STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System" (PDF). usenix evtvote13. Retrieved 2018-04-24.
- "Travis County - STAR-VoteTM Request for Proposal Released". www.traviscountyclerk.org. 2016-10-10. Retrieved 2018-04-24.
- Pritchard, Caleb (2017-10-04). "STAR-Vote collapses - Austin Monitor". Austin Monitor. Retrieved 2018-08-04.
- Ballard, Ginny (2017-09-28). "Travis County - STAR-Vote - A Change of Plans". traviscountyclerk.org. Retrieved 2018-08-04.
- Chaum, David (2004). "Secret-Ballot Receipts: True Voter-Verifiable Elections". IEEE Security and Privacy. 2 (1): 38–47. doi:10.1109/MSECP.2004.1264852.
- Reusable anonymous return channels
- Chris Karlof, Naveen Sastry, and David Wagner. Cryptographic Voting Protocols: A Systems perspective. Proceedings of the Fourteenth USENIX Security Symposium (USENIX Security 2005), August 2005.
- Steven Cherry, Making every e-vote count, IEEE Spectrum, Jan 2007.
- Scratch & Vote: Self-Contained Paper-Based Cryptographic Voting (2006)
- Okun, Eli (2014-07-09). "Travis County Forges New Territory in Creating Voting Machine". The Texas Tribune. Retrieved 2016-09-02.
- ADDER voting system
- Helios Voting system
- Wombat Voting system
- Feng Hao, Matthew N. Kreeger, Brian Randell, Dylan Clarke, Siamak F. Shahandashti, and Peter Hyun-Jeen Lee. "Every Vote Counts: Ensuring Integrity in Large-Scale Electronic Voting". USENIX Journal of Election Technology and Systems (JETS) Volume 2, Number 3, July 2014
- Siamak F. Shahandashti and Feng Hao. "DRE-ip: A Verifiable E-Voting Scheme without Tallying Authorities". Proceedings of the 21st European Symposium on Research in Computer Security (ESORICS), LNCS, Vol. 9879, 2016
- 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
- Simple Auditable & Anonymous Voting Scheme
- Study on Poll-Site Voting and Verification Systems — A review of existing electronic voting systems and its verification systems in supervised environments.