Source-linked AI summary
STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System
Josh Benaloh, Mike Byrne, Philip Kortum, Neal McBurnett, Olivier Pereira, Philip B. Stark, Dan S. Wallach
TL;DR
Existing election systems left Travis County needing a replacement that addressed aging DREs, paper-ballot ambiguities, and ballot-style management while preserving usability. The paper presents STAR-Vote, combining a DRE-style interface, machine-printed paper records, end-to-end cryptography, voter verification, and audits. Its architecture provides redundant evidence for election outcomes, while voter participation in challenge procedures and coercion resistance remain important limitations.
Problem
Travis County needed to replace aging DREs, but available systems were inadequate and hand-marked or pre-printed paper ballots introduced ambiguity and ballot-style management concerns.
Method
The paper architects STAR-Vote as a DRE-style voting system combining a voter-verifiable paper trail, end-to-end cryptography, usability-oriented interaction, and multiple audit mechanisms.
Results
STAR-Vote is designed so three evidence lines—homomorphic tallying, voter challenge and receipt checking, and paper-ballot auditing—support each election outcome and should remain consistent.
Takeaways & Limitations
The architecture combines paper and electronic records with cryptographic and statistical checks to support reliability, transparency, fraud resistance, and auditability.
Takeaways & Limitations
The end-to-end verification depends partly on voters challenging the system, but challengers may be few and unrepresentative, allowing some problems to go unnoticed.
Abstract
from arXiv · showhide
In her 2011 EVT/WOTE keynote, Travis County, Texas County Clerk Dana DeBeauvoir described the qualities she wanted in her ideal election system to replace their existing DREs. In response, in April of 2012, the authors, working with DeBeauvoir and her staff, jointly architected STAR-Vote, a voting system with a DRE-style human interface and a "belt and suspenders" approach to verifiability. It provides both a paper trail and end-to-end cryptography using COTS hardware. It is designed to support both ballot-level risk-limiting audits, and auditing by individual voters and observers. The human interface and process flow is based on modern usability research. This paper describes the STAR-Vote architecture, which could well be the next-generation voting system for Travis County and perhaps elsewhere.
1 Introduction
STAR-Vote was designed to replace aging and inadequate DRE and optical-scan systems while preserving a DRE-like interface and adding a voter-verifiable paper record. The architecture balances usability, auditing, security, and administrative constraints.
- Existing DRE systems promised usability, accessibility, accurate tallies, security, and reliability, but much of that promise was not realized.
- DRE machines adopted after the 2000 Florida punch-card failures were nearing the end of their service lifetimes.
- Travis County found available DRE replacements inadequate and rejected returning to hand-marked or pre-printed paper ballots because of ambiguity and ballot-style management problems.
- The design team combined cryptography, auditing, and usability expertise under constraints requiring a DRE-like experience and a machine-printed, voter-verifiable paper ballot.
- The project treated certification as out of scope while also seeking lower costs and reduced burdens for poll workers and voters.
2 Voter Flow
Voters authenticate with temporary tokens, make and review selections on an accessible terminal, and receive both a paper ballot summary and a cryptographic receipt. They may cast, spoil, challenge, or provisionally submit the ballot, with records tracked for later verification.
- Voters check in, receive a ballot-style token, select a machine, and enter a temporary code that identifies the ballot style without permanently binding the code to their identity.
- The voting interface supports visual and auditory selection, includes a review screen, and lets voters confirm selections before printing.
- Each completed vote produces a human-readable paper ballot summary and a take-home receipt containing terminal, time, and commitment information.
- After reviewing the printed record, voters may cast the ballot, spoil it to challenge the terminal, or submit it as a provisional ballot.
- Spoiled ballots are excluded from the tally and decrypted for verification, while monitors can use spoiled ballots for parallel testing during live elections.
- Voters can check posted encrypted records and spoiled-ballot decryptions against their receipts on a public bulletin board.
3 Design
STAR-Vote combines threshold cryptography, encrypted public records, paper ballots, voter checks, and risk-limiting audits into a redundant verification architecture. Commodity hardware and separated software components support operational resilience and replacement.
- Threshold key generation lets any k of n trustees complete the election while preventing fewer than k trustees from decrypting it.
- The system publishes encrypted ballots with signatures and well-formedness proofs, while spoiled records receive verifiable decryptions.
- A privacy-preserving risk-limiting audit randomly matches paper ballot summaries with encrypted ballots to provide software-independent evidence of the outcome.
- Three evidence lines support each outcome: homomorphic tallying, voter challenge and receipt checking, and an independent paper-ballot audit.
- The three checks should be perfectly consistent, with records sufficient to isolate discrepancies to individual ballots.
- The design favors commodity components because they reduce cost and simplify replacement, while hardware and software separation may ease certification.
4 Usability
STAR-Vote treats usability as a design objective alongside security and administrative practicality, using electronic interaction to reduce voter errors while retaining a paper review opportunity. Its interface also incorporates accessibility and review-screen requirements.
- Design Considerations: The design seeks effectiveness, efficiency, and satisfaction while maximizing usability within enhanced security and administrative constraints.
- Usability and security: Security mechanisms are mostly invisible, while optional challenge and post-voting verification tasks are left to voters who choose them.
- Error reduction: Computer-assisted selection eliminates overvotes, highlights undervotes, and provides electronic and paper review opportunities before casting.
- Accessibility: The interface uses a touchscreen DRE model with an auditory interface and support for voter-supplied controls for physical impairments.
- Review Screens: The design extends VVSG-based requirements with full contest and candidate names, undervote highlighting, navigable review screens, and distinctive race-state markings.
- Accessibility: Accessibility requirements include adjustable speech, replay and skipping controls, and a final ballot review that is available but not mandatory.
5 Audit
STAR-Vote combines a paper audit trail with cryptographic verification, linking individual cast vote records to paper ballots for efficient ballot-level comparison audits. Its audit procedures can detect outcome discrepancies, but voter challenges and ballot handling introduce important limitations.
- Limitations: Voter challenges can reveal dishonest encryption and missing votes, but challengers may be few and unrepresentative, allowing some problems to go unnoticed.Ballot marks made during handling can also create discrepancies between printed voter intent and audit interpretation.
- Paper audit trail: The paper audit trail independently checks tabulation, agreement between voter-visible selections and encryption, and whether reported winners match a full hand count.STAR-Vote uses SOBA as its risk-limiting audit method.
- Risk-limiting audit: A risk-limiting audit can trigger a full hand count when the reported outcome disagrees with the paper-ballot outcome, correcting the result before it becomes official.Risk-limiting audits are described as widely considered best practice for election audits.
- Ballot-level comparison: Individual cast vote records link to their corresponding paper ballots through encrypted vote data, simplifying ballot-level comparison audits and reducing ordering errors.This avoids work-arounds such as reordering ballots, rescanning images, and constructing cast vote records manually.
- SOBA protocol: SOBA combines public commitment to vote data, unbundled publication of contests, and simple computations to reduce pattern-voting risks while preserving transparency.The protocol publishes vote data in plain text but separates contests so patterns cannot be used to signal.
- Audit sampling: The encrypted ballot data provide unique identifiers, while public entropy and a published pseudorandom generator select audit ballots transparently.The ballot identifier removes the need to store ballots in rigid order.
6 The Cryptographic Workflow
The cryptographic workflow encrypts and proves each ballot, links electronic and paper records through hashes and serial numbers, and aggregates encrypted votes into a verifiable tally. Threshold trustees and published cryptographic data support privacy, integrity checks, and public verification.
- Cryptographic core: STAR-Vote uses threshold encryption with additive homomorphism so trustees can protect voter privacy while combining encrypted ballots into an aggregate tally.The paper identifies exponential Elgamal as satisfying these requirements.
- Key generation: Trustees hold distributed private-key shares, and any preset quorum can complete the election while fewer than the threshold cannot compromise voter privacy.The published public key corresponds to the distributed shares.
- Ballot protection: Each ballot is encrypted with randomized encryption, accompanied by a non-interactive zero-knowledge proof of validity, and incorporated into a hash chain.The proof ensures encrypted ballots correspond to well-formed votes; the chain links ballots to a published election commitment.
- Public verification: Publishing encrypted ballots and hashes lets voters verify recording and observers verify homomorphic aggregation, while a removed ballot invalidates the committed hash chain.Stored data are accepted when the hash chain and cryptographic proofs verify.
- End-to-end verification: The paper-and-cryptographic workflow is hardened so voters can inspect printed selections, challenge ballots, and connect the election outcome to the paper audit trail.These mechanisms verify different aspects of ballot preparation and casting.
- Ballot production: The terminal prints a human-readable ballot and a take-home receipt containing the terminal identifier, time, and ballot hash, while transmitting the encrypted record and proof to the judge’s station.The paper ballot includes a robustly machine-readable serial number.
- Tally computation: When a ballot is cast, its serial number marks the associated electronic record complete; at poll closing, flagged encrypted votes are aggregated and verifiably decrypted into the election result.A separate hash structure supports the SOBA audit.
7 Coercion
STAR-Vote addresses coercion selectively: it prevents wholesale pattern-voting attacks but accepts residual risks from receipts, chain voting, and links between paper and electronic records. Some mitigations are used, while stronger measures were rejected as impractical or harmful to usability.
- Receipt coercion: The design avoids elaborate receipt-hiding measures because ubiquitous cameras could leave coercion threats unaddressed despite those protections.The authors explicitly weigh protocol complexity and voter-experience costs against known coercion threats.
- Chain voting: Chain voting remains possible when voters carry completed ballots to coercers, although time-outs and efforts to prevent ballots leaving polling sites provide mitigation.The design does not require additional steps to make chain voting impossible.
- Pattern voting: SOBA is designed to prevent pattern-voting attacks without publishing the full set of raw ballots, preserving tally assurance while limiting coercive signaling.The paper distinguishes this protection against wholesale coercion from residual coercion risks.
- Paper–electronic linkage: Data linking paper ballots to encrypted electronic records create a potential vulnerability when audited ballot summaries become public.Take-home receipt data are therefore excluded from the corresponding public paper-ballot summary.
- External votes: External ballots are initially entered by officials as proxies, so remote voters cannot audit their own ballots even though the privacy-preserving audit can still detect problems.The initial design avoids the complexity of capturing provisional and remote ballots electronically.
8 Conclusions and Future Work
STAR-Vote combines commercial voting-system foundations with cryptography, usability, software engineering, and auditing techniques, while supporting future remote-voting applications. Its cryptographic design preserves voter anonymity for remote votes but does not make Internet voting suitable.
- STAR-Vote evolves commercial voting systems by integrating cryptography, software engineering, usability, and auditing techniques to improve election reliability, accuracy, fraud-resistance, and transparency.
- STAR-Vote could support remote voting by transmitting ballot definitions to suitable voting locations and returning results to the county.
- Cryptographic mechanisms make a remote vote equivalent to a local provisional vote for resolution while preserving voter anonymity.
- STAR-Vote is not intended for Internet voting because unknown computers, malware, and the absence of systematic protections against bribery or coercion make ballot casting foolhardy.
- The architecture anticipates commodity computers running custom software, although meeting long-term storage and full-day battery requirements remains unclear.