End-to-end auditable voting
{{Short description|Voting system}}
{{Electiontech}}
{{voting|expanded=Electoral fraud}}
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 use cryptographic techniques to provide voters with receipts that allow them to verify their votes were counted as cast, without revealing which candidates a voter supported to an external party. As such, these systems are sometimes called receipt-based systems.{{Cite web|url=https://www.eac.gov/sites/default/files/eac_assets/1/28/VVSG.1.0_Volume_1.PDF|title=Voluntary Voting System Guidelines version 1.0|date=2005|website=Election Assistance Commission|access-date=2020-04-07}}
Overview
Electronic voting systems arrive at their final vote totals by a series of steps:
- voters cast ballots either electronically or manually,
- cast vote records are tallied to generate totals,
- where elections are conducted locally, such as at the precinct or county level, the results from each level are combined to produce the final tally.
Classical approaches to election integrity focus on ensuring the security of each step individually, going from voter intent to the final total. Such approaches have generally fallen out of favor with distributed system designers, as these local local focus may miss some vulnerabilities while over-protecting others. The alternative is to use end-to-end measures that are designed to demonstrate the integrity of the entire chain.{{Cite journal |author-link1=Jerry Saltzer |author-link2=David P. Reed |author-link3=David D. Clark |author1=J. H. Saltzer |author2=D. P. Reed |author3=D. D. Clark |doi=10.1145/357401.357402 |doi-access=free |issn=0734-2071 |volume=2 |issue=4 |journal=ACM Transactions on Computer Systems |language=en |pages=277–288 |date=1 November 1984 |s2cid=215746877 |title=End-to-end arguments in system design|citeseerx=10.1.1.39.1747 }}
Comprehensive coverage of election integrity frequently involves multiple stages. Voters are expected to verify that they have marked their ballots as intended, recounts or audits are used to protect the step from marked ballots to ballot-box totals, and publication of all subtotals allows public verification that the overall totals correctly sum the ballot-box totals.Douglas W. Jones, Perspectives on Electronic Voting, [http://www.ifes.org/publication/6535478b9b3c7bda289626a871bb821a/IFES%20From%20Power%20Outages_GEO%20Conf%20Paper_cv.pdf From Power Outages to Paper Trails] {{Webarchive|url=https://web.archive.org/web/20081128110716/http://www.ifes.org/publication/6535478b9b3c7bda289626a871bb821a/IFES%20From%20Power%20Outages_GEO%20Conf%20Paper_cv.pdf |date=2008-11-28 }} ([http://www.cs.uiowa.edu/~jones/voting/IFES2007.pdf alternate source]), IFES, Washington DC, 2007; pages 32-46, see particularly Figure 4, page 39. Conventional voting schemes do not meet this standard, and as a result cannot conclusively prove that no votes have been tampered with at any point; voters and auditors must instead verify each individual step is fully secure, which may be difficult and introduces many points of failure.Douglas W. Jones, End-to-End Standards for Accuracy in Paper-Based Systems, [https://web.archive.org/web/20020606233416/http://www.vote.caltech.edu/west02/presentations.html Workshop on Election Standards and Technology] ([http://www.cs.uiowa.edu/~jones/voting/west02/ alternate source]), Jan 31, 2002, Washington DC.
While measures such as voter verified paper audit trails and manual recounts measure the effectiveness of some steps, they offer only weak measurement of the integrity of the physical or electronic ballot boxes. Ballots could be removed, replaced, or could have marks added to them without detection (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 their 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, most E2E voting schemes also attempt to meet a third requirement called receipt-freeness:
- No voter can prove how he or she voted to any third party.
It was originally believed that combining both properties would be impossible.Douglas W. Jones, [http://www.cs.uiowa.edu/~jones/voting/E2E2009.pdf Some Problems with End-to-End Voting], position paper presented at the [http://csrc.nist.gov/groups/ST/e2evoting/program_E2E.html End-to-End Voting Systems Workshop], Oct. 13-14, 2009, Washington DC. However, further research has since shown these properties can co-exist.B Smyth, S. Frink and M. R. Clarkson, Election Verifiability: Cryptographic Definitions and an Analysis of Helios and JCJ, [https://hdl.handle.net/1813/40575 Cornell's digital repository], Feb. 2017 Both are combined in the 2005 Voluntary Voting System Guidelines promulgated by the Election Assistance Commission.[http://www.eac.gov/voting%20systems/docs/vvsgvolumei.pdf/attachment_download/file/ 2005 Voluntary Voting System Guidelines] {{Webarchive|url=https://web.archive.org/web/20080613012027/http://www.eac.gov/voting%20systems/docs/vvsgvolumei.pdf/attachment_download/file |date=2008-06-13 }}, Election Assistance Commission This definition is also predominant in the academic literature.Jeremy Clark, Aleks Essex, and Carlisle Adams. [http://people.scs.carleton.ca/~clark/papers/2007_wote_receipts.pdf On the Security of Ballot Receipts in E2E Voting Systems] {{Webarchive|url=https://web.archive.org/web/20120722023603/http://people.scs.carleton.ca/~clark/papers/2007_wote_receipts.pdf |date=2012-07-22 }}. IAVoSS Workshop on Trustworthy Elections 2007.Aleks Essex, Jeremy Clark, Richard T. Carback III, and Stefan Popoveniuc. [http://www.punchscan.org/papers/pip_essex.pdf Punchscan in Practice: An E2E Election Case Study]. IAVoSS Workshop on Trustworthy Elections 2007.Olivier de Marneffe, Olivier Pereira and Jean-Jacques Quisquater. [https://doi.org/10.1007%2F978-3-540-77493-8_12 Simulation-Based Analysis of E2E Voting Systems]. E-Voting and Identity 2007.Ka-Ping Yee. [http://zesty.ca/pubs/yee-phd.pdf Building Reliable Voting Machine Software]. Ph.D. Dissertation, UC Berkeley, 2007.
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.{{Cn|date=September 2024}}
Alternatively, assertions regarding ballot stuffing can be externally verified by comparing the number of ballots on hand with the number of registered voters recorded as having voted, and by auditing other aspects of the registration and ballot delivery system.
Support for E2E auditability, based on prior experience using it with in-person elections, is also seen as a requirement for remote voting over the Internet by many experts.{{cite news | url=https://www.usvotefoundation.org/E2E-VIV | title=The Future of Voting: End-to-End Verifiable Internet Voting - Specification and Feasibility Study - E2E-VIV Project | work=U.S. Vote Foundation | date=2015 | access-date=2016-09-01 }}
Proposed E2E Systems
In 2004, David Chaum proposed a solution that allows each voter to verify that their votes are cast appropriately and that the votes are accurately tallied using visual cryptography.{{cite journal|last=Chaum|first=David|author-link=David Chaum|year=2004|title=Secret-Ballot Receipts: True Voter-Verifiable Elections|journal=IEEE Security and Privacy|volume=2|issue=1|pages=38–47|doi=10.1109/MSECP.2004.1264852|s2cid=1015904}} After the voter selects their candidates, a voting 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 voting machine 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 detects changes to the voter's ballot and uses a mix-net decryption{{Cite book|chapter-url=https://doi.org/10.1145/1005140.1005155|chapter=Reusable anonymous return channels|first1=Philippe|last1=Golle|first2=Markus|last2=Jakobsson|title=Proceedings of the 2003 ACM workshop on Privacy in the electronic society |date=October 30, 2003|publisher=Association for Computing Machinery|pages=94–100|via=ACM Digital Library|doi=10.1145/1005140.1005155|isbn=1-58113-776-1 |s2cid=3040325 }} procedure to check if each vote is accurately counted. Sastry, Karloff and Wagner pointed out that there are issues with both of the Chaum and VoteHere cryptographic solutions.Chris Karlof, Naveen Sastry, and David Wagner. [http://www.cs.berkeley.edu/~nks/papers/cryptovoting-usenix05.pdf Cryptographic Voting Protocols: A Systems perspective]. Proceedings of the Fourteenth USENIX Security Symposium (USENIX Security 2005), August 2005.
Chaum's team subsequently developed Punchscan, which has stronger security properties and uses simpler paper ballots.Steven Cherry, [https://archive.today/20130113103752/http://www.spectrum.ieee.org/print/4817 Making every e-vote count], IEEE Spectrum, Jan 2007. 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.{{Cite web|url=https://ben.adida.net/research/|title=Ben Adida|website=ben.adida.net}}
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. Rather than replacing 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, producing conventional voter-verifiable paper ballots suitable for risk-limiting audits. Scantegrity II employs invisible ink and was developed by a team that included Chaum, Rivest, and Ryan.
The STAR-Vote system{{Cite web|last=Bell|first=Susan|display-authors=etal|date=2013-08-01|title=STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System|url=https://www.usenix.org/system/files/conference/evtwote13/jets-0101-bell.pdf|access-date=2018-04-24|website=usenix evtvote13}} was defined for Travis County, the fifth most populous county in Texas, and home of the state capital, Austin.{{Cite web|date=2016-10-10|title=Travis County - STAR-VoteTM Request for Proposal Released|url=http://www.traviscountyclerk.org/eclerk/Content.do?code=News.StarVote|access-date=2018-04-24|website=www.traviscountyclerk.org|archive-date=2018-04-25|archive-url=https://web.archive.org/web/20180425031824/http://www.traviscountyclerk.org/eclerk/Content.do?code=News.StarVote|url-status=dead}} It illustrated another way to combine an E2E system with conventionally auditable paper ballots, produced in this case by a ballot marking device.{{Cite web|last=Okun|first=Eli|date=2014-07-09|title=Travis County Forges New Territory in Creating Voting Machine|url=https://www.texastribune.org/2014/07/09/travis-county-forges-new-territory-voting-machines/|access-date=2016-09-02|website=The Texas Tribune}} The project produced a detailed spec and request for proposals in 2016, and bids were received for all the components, but no existing contractor with an EAC certified voting was willing to adapt their system to work with the novel cryptographic open-source components, as required by the RFP.{{Cite news|last=Pritchard|first=Caleb|date=2017-10-04|title=STAR-Vote collapses - Austin Monitor|language=en-US|work=Austin Monitor|url=https://www.austinmonitor.com/stories/2017/10/star-vote-collapses/|access-date=2018-08-04}}{{Cite web|last=Ballard|first=Ginny|date=2017-09-28|title=Travis County - STAR-Vote - A Change of Plans|url=https://countyclerk.traviscountytx.gov/star-vote-a-change-of-plans.html|access-date=2018-08-04|website=traviscountyclerk.org}}
{{anchor|ElectionGuard}}Building on the STAR-Vote experience, Josh Benaloh at Microsoft led the design and development of ElectionGuard, a software development kit that can be combined with existing voting systems to add E2E support. The voting system interprets the voter's choices, stores them for further processing, then calls ElectionGuard which encrypts these interpretations and prints a receipt for the voter. The receipt has a number which corresponds to the encrypted interpretation. The voter can then disavow the ballot (spoil it), and vote again. Later, independent sources, such as political parties, can obtain the file of numbered encrypted ballots and sum the different contests on the encrypted file to see if they match the election totals. The voter can ask those independent sources if the number(s) on the voter's receipt(s) appear in the file. If enough voters check that their numbers are in the file, they will find if ballots are omitted. Voters can get the decrypted contents of their spoiled ballots, to determine if they accurately match what the voter remembers was on those ballots. The voter cannot get decrypted copies of voted ballots, to prevent selling votes. If enough voters check spoiled ballots, they will show mistakes in encryptions. ElectionGuard does not detect ballot stuffing, which must be detected by traditional records. It does not detect people who falsify receipts, claiming their ballot is missing or was interpreted in error. Election officials will need to decide how to track claimed errors, how many are needed to start an investigation, how to investigate and how to recover from errors, State law may give staff no authority to take action. ElectionGuard does not tally write-ins, except as an undifferentiated total. It is incompatible with overvotes.{{Cite magazine |last=Halpern |first=Sue |date=2020-07-07 |title=Can Our Ballots Be Both Secret and Secure? |url=https://www.newyorker.com/news/the-future-of-democracy/can-our-ballots-be-both-secret-and-secure |magazine=New Yorker |language=en-US |access-date=2021-10-14}}{{Cite web |last=McKim |first=Karen |date=2021-03-16 |title=The Election Guard we need isn't one that Microsoft can provide. It's human. |url=https://wisconsinelectionintegrity.org/author/kmk/ |access-date=2021-10-15 |website=Wisconsin Election Integrity |language=en-US}}{{Cite web |title=ElectionGuard - Structures and Processes |url=https://www.electionguard.vote/concepts/Structure_and_Processes |access-date=2021-10-17 |website=www.electionguard.vote |language=en}}
Use in elections
The city of Takoma Park, Maryland used Scantegrity II for its 2009 and 2011 city elections.{{Cite web
|title=Pilot Study of the Scantegrity II Voting System Planned for the 2009 Takoma Park City Election
|url=http://www.takomaparkmd.gov/committees/boe/documents/flyer_workshop_I_(02-19-09).pdf
|archive-url=https://web.archive.org/web/20110719064407/http://www.takomaparkmd.gov/committees/boe/documents/flyer_workshop_I_(02-19-09).pdf
|archive-date=2011-07-19
| last = Hardesty
| first = Larry
| title = Cryptographic voting debuts
| work = MIT news
| date = 13 November 2009
| access-date = 2009-11-30
| url = http://web.mit.edu/newsoffice/2009/rivest-voting.html
}}
Helios has been used since 2009 by several organizations and universities for general elections, board elections, and student council elections.{{Cite web|url=https://iacr.org/elections/eVoting/heliosDemo.pdf|title=The Helios e-Voting Demo for the IACR|last=Haber|first=Stuart|date=May 24, 2010}}{{Cite web|url=https://www.usenix.org/legacy/event/evtwote09/tech/full_papers/adida-helios.pdf|title=Electing a University President using Open-Audit Voting: Analysis of real-world use of Helios|last=Adida|first=Ben|date=June 25, 2009}}
Wombat Voting was used in student council elections at the private research college Interdisciplinary Center Herzliya in 2011 and 2012,{{Cite web|url=https://courses.csail.mit.edu/6.857/2018/files/L20-Auditability-and-Verifiability-of-Elections-slides.ppt|title=Auditability and Verifiability of Elections|last=Rivest|first=Ron L.|date=March 16, 2016}}{{Cite conference |last1=Ben-Nun |first1=Jonathan |last2=Farhi |first2=Niko |last3=Llewellyn |first3=Morgan |last4=Riva |first4=Ben |last5=Rosen |first5=Alon |last6=Ta-Shma |first6=Amnon |last7=Wikstrom |first7=Douglas |date=2012 |title=A New Implementation of a Dual (Paper and Cryptographic) Voting System |editor=Manuel J. Kripp |editor2=Melanie Volkamer |editor3=Rüdiger Grimm |book-title=5th International conference on electronic voting 2012 (EVOTE2012) |location=Bonn |publisher=Gesellschaft für Informatik |isbn=978-3-88579-299-4 |s2cid=2015880}} as well as in the primary elections for the Israeli political party Meretz in 2012.{{Cite news|url=https://www.jpost.com/Diplomacy-and-Politics/Meretz-aims-to-revolutionize-electronic-voting|title=Meretz aims to revolutionize electronic voting|newspaper=The Jerusalem Post|access-date=2020-01-14}}
A modified version of Prêt à Voter was used as part of the vVote poll-site electronic voting system at the 2014 Victorian State Election in Australia.{{Cite arXiv|title=A Trustworthy Electronic Voting System for Australian Federal Elections|last=Eldridge|first=Mark|date=May 6, 2018|class=cs.CR|eprint=1805.02202}}
ElectionGuard was combined with a voting system from VotingWorks and used for the Fulton, Wisconsin spring primary election on February 18, 2020.{{Cite magazine|title=A Texas County Clerk's Bold Crusade to Transform How We Vote|language=en-us|magazine=Wired|url=https://www.wired.com/story/dana-debeauvoir-texas-county-clerk-voting-tech-revolution/|access-date=2021-04-10|issn=1059-1028}}
A touch-screen based DRE-ip implementation was trialed in a polling station in Gateshead on 2 May 2019 as part of the 2019 United Kingdom local elections.{{cite web |last1=Wakefield |first1=Jane |title=E-voting trialled in local elections |url=https://www.bbc.co.uk/news/technology-48132591 |website=BBC News |date=2 May 2019}}{{cite journal |last1=Hao |first1=Feng |last2=Wang |first2=Shen |last3=Bag |first3=Samiran |last4=Procter |first4=Rob |last5=Shahandashti |first5=Siamak F |last6=Mehrnezhad |first6=Maryam |last7=Toreini |first7=Ehsan |last8=Metere |first8=Roberto |last9=Liu |first9=Lana |title=End-to-End Verifiable E-Voting Trial for Polling Station Voting |journal=IEEE Security & Privacy |date=2020 |volume=18 |issue=6 |pages=6–13 |doi=10.1109/MSEC.2020.3002728 |s2cid=219616040 |url=https://eprint.iacr.org/2020/650.pdf}} A browser-based DRE-ip implementation was used in an online voting trial in October 2022 among the residents of New Town, Kolkata, India during the 2022 Durga Puja festival celebration.{{cite journal |last1=Druliac |first1=Horia |last2=Bardsley |first2=Matthew |last3=Riches |first3=Chris |last4=Dunn |first4=Christian |last5=Harrison |first5=Luke |last6=Roy |first6=Bimal |last7=Hao |first7=Feng |title=On the feasibility of E2E verifiable online voting – A case study from Durga Puja trial |journal=Journal of Information Security and Applications |date=1 March 2024 |volume=81 |pages=103719 |doi=10.1016/j.jisa.2024.103719|doi-access=free }}
Examples
- ADDER{{Cite web |url=http://mkorman.org/acsac.pdf |title=ADDER voting system |access-date=2012-07-12 |archive-date=2010-03-27 |archive-url=https://web.archive.org/web/20100327045753/http://www.mkorman.org/acsac.pdf |url-status=dead }}
- Helios{{Cite web|url=https://vote.heliosvoting.org/|title=Helios Voting|website=vote.heliosvoting.org}}
- Prêt à Voter
- Punchscan
- Scantegrity
- Wombat Voting {{Cite web|url=https://wombat.factcenter.org/|title=Wombat Voting System}}
- ThreeBallot
- Bingo Voting
- homomorphic secret sharing
- DRE-iFeng Hao, Matthew N. Kreeger, Brian Randell, Dylan Clarke, Siamak F. Shahandashti, and Peter Hyun-Jeen Lee. [https://www.usenix.org/system/files/jets/issues/0203/overview/jets-0203-hao.pdf "Every Vote Counts: Ensuring Integrity in Large-Scale Electronic Voting"]. USENIX Journal of Election Technology and Systems (JETS)
Volume 2, Number 3, July 2014 (E2E verifiable e-voting without tallying authorities based on pre-computation)
- DRE-ipSiamak F. Shahandashti and Feng Hao. [https://eprint.iacr.org/2016/670.pdf "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 (E2E verifiable e-voting without tallying authorities based on real-time computation)
- Assembly Voting X{{cite web |last1=Patachi |first1=Stefan |title=Assembly Voting X |url=https://assemblyvoting.com/wp-content/uploads/AVX_technical_documentation.pdf |website=assemblyvoting.com |publisher=Assembly Voting |access-date=27 April 2023 |archive-url=https://web.archive.org/web/20230302090612/https://assemblyvoting.com/wp-content/uploads/AVX_technical_documentation.pdf |archive-date=2 March 2023 |language=en |date=September 2019 |url-status=live}}{{cite web | url=https://assemblyvoting.com/technology/core-technologies/ | title=Core Technologies – Assembly Voting | date=24 April 2021 }}{{cite web | url=https://assemblyvoting.com/blog/black-box-voting-vs-e-2-e-verifiable-voting/ | title=Black Box Voting Vs. End-to-End Verifiable Voting – Assembly Voting | date=19 April 2022 }}
References
{{reflist}}
External links
- [https://www.youtube.com/watch?v=ZDnShu5V99s Verifying Elections with Cryptography] — Video of Ben Adida's 90-minute tech talk
- [http://www.usenix.org/events/sec08/tech/full_papers/adida/adida.pdf Helios: Web-based Open-Audit Voting] — PDF describing Ben Adida's Helios web-site
- [https://heliosvoting.org/ Helios Voting System web-site]
- [http://quaxio.com/simple_auditable_anonymous_voting_scheme/ Simple Auditable & Anonymous Voting Scheme]
- [https://dx.doi.org/10.1016/j.cose.2012.08.001 Study on Poll-Site Voting and Verification Systems] — A review of existing electronic voting systems and its verification systems in supervised environments.
- [https://www.media.mit.edu/posts/crypto-voting-us-elections-reality/ a 2020 MIT Media Lab article about end to end verifiable voting systems, includes discussion of blockchains]
- [https://www.economist.com/technology-quarterly/2008/12/06/a-really-secret-ballot A Really Secret Ballot] — Article by The Economist