Evidence Based Elections and Software Independence

Evidence Based Elections and Software Independence

Speakers: Ron Rivest, Professor Emeritus, MIT

Conference: Voting Village

YouTube: https://www.youtube.com/watch?v=8rIM5aTApKo

Overview

In this compelling talk at the Voting Village, renowned computer scientist and MIT Professor Emeritus Ron Rivest, widely recognized as the 'R' in the RSA algorithm, delivered a critical examination of election security, advocating for evidence-based elections and software independence. Rivest's presentation underscored the fundamental importance of trustworthy elections to democracy and challenged the prevailing reliance on unverified electronic systems. He argued that despite technological advancements, the most robust security for electoral processes lies in tangible, voter-verified evidence, primarily paper ballots, coupled with rigorous post-election audits.

Rivest, a Turing Award laureate, brought his extensive expertise in cryptography and computer science to bear on one of the most complex challenges in the field: securing democratic elections. His insights highlight that unlike other digital transactions such as online banking, voting demands absolute anonymity and an environment where no single party, including software or election officials, can be fully trusted. The talk served as a powerful call to action for election integrity, urging a shift towards systems that inherently provide convincing evidence of correct outcomes, rather than simply relying on computer tallies.

The core message of the presentation revolved around minimizing the trust placed in software, which is inherently vulnerable to undetected errors and malicious manipulation. Instead, Rivest champions a system where the voter-verified cast ballot forms the immutable "ground truth" evidence, subject to statistical audits that can detect and correct any discrepancies. This approach offers a pragmatic and resilient pathway to ensuring that election results accurately reflect the will of the people, fostering public confidence in an increasingly scrutinized democratic process.

Background

▶ Watch: Introduction of Ron Rivest: RSA co-inventor and Turing award winner. (0:00)

The landscape of voting in the United States has undergone significant transformations, moving from historical methods to predominantly paper ballots today, a trend Rivest supports. The Australian paper ballot, introduced in 1893, marked a pivotal shift by standardizing ballots printed by election officials, ensuring voter privacy and eliminating partisan colors. While paper ballots are now widely used, the integration of technology, particularly scanners for efficient tabulation and Ballot Marking Devices (BMDs), introduces complexities and potential vulnerabilities. These systems, while streamlining the process, can introduce errors due to differing interpretations of voter intent, stray marks, configuration issues, or even malicious programming.

Rivest emphasized that voting is "one of the hardest problems in computer science," fundamentally different from online banking. Unlike banking, where transactions are auditable and traceable to specific individuals, votes must remain anonymous, and no single entity, whether a vendor, election official, or even a nation-state, can be fully trusted. Key security requirements include ensuring only eligible voters cast ballots, each voter votes at most once, and crucially, each cast vote remains secret, even from the voter themselves (preventing vote selling through receipts). The final outcome must be verifiably correct, with evidence accessible to all stakeholders. This intricate web of requirements, coupled with variations across jurisdictions and the need to accommodate diverse voter needs (e.g., disabled voters, ranked-choice voting), makes election system design exceptionally challenging.

The inherent untrustworthiness of software forms a critical backdrop to Rivest's arguments. As he highlighted, software can be self-modifying, erasing, or even designed to appear clean when inspected, only to behave maliciously during an election. Furthermore, verifying that the correct and uncompromised software is running on a voting machine is an almost insurmountable task, a conclusion reached by the Technical Guidelines Development Committee (TGDC) during his tenure. This fundamental lack of trust in software necessitates a system where the election outcome does not solely depend on the flawless operation of code.

Key Findings

▶ Watch: Ron Rivest introduces talk focus: evidence-based elections and software indep... (3:15)

Rivest's talk centered on two paramount themes: evidence-based elections and software independence, which he posits are crucial for achieving trustworthy outcomes.

First, evidence-based elections mandate that an election system must not only accurately determine the winner but also "provide convincing evidence that the winner really won." This concept, most clearly articulated by Philip Stark and David Wagner in their 2012 paper, elevates the importance of post-election residue—the verifiable proof of the outcome—above mere system certification. For Rivest, the collection of voter-verified cast ballots constitutes the "best evidence" or "ground truth." This means the evidence must be something the voter has directly confirmed as accurate, ruling out electronic systems where verification is, at best, indirect. The authenticity of this collection must also be assured through a verifiable chain of custody.

Second, software independence addresses the inherent unreliability of software in critical systems. Rivest, drawing from his work with the TGDC, defined a voting system as software independent "if an undetected error in the software cannot cause an undetectable change in the election outcome." This means that even if malicious software manipulates tallies, there must be a way to detect this manipulation through independent means. A stronger form, strongly software independent, further requires that any such detected error can be corrected, closing the loop on election integrity. The primary example of a software-independent system is paper ballots combined with a hand recount or a Risk-Limiting Audit (RLA). Rivest also provocatively argued for open source voting systems, suggesting that making software public would aid examination, but crucially, he stressed that "the software is not the evidence; the evidence is the paper trail." The core concern is the integrity of the ballots, not the software itself, which could even be written by an adversary and still produce a legitimate outcome if subject to robust, independent verification.

These principles align with the recommendations of the National Academies of Sciences, Engineering, and Medicine (NASA) 2018 report, "Securing the Vote." This report, in which Rivest was a committee member, called for the universal use of voter-verifiable paper ballots by 2020 and mandatory auditing of election outcomes. Rivest echoed the sentiment, quoting Philip Stark: "Pervyor elects to say, you know, eat your breakfast, you know, floss your teeth, audit your elections." These findings collectively advocate for a fundamental reorientation of election security around tangible evidence and human oversight, rather than blind trust in technology.

Technical Deep Dive

▶ Watch: Historical context and current prevalence of paper ballots. (4:40)

The cornerstone of Rivest's proposed secure election system is the Risk-Limiting Audit (RLA). An RLA is a statistical audit that uses manual interpretation of cast paper ballots to verify, with a high probability, that the reported election outcome is correct. More precisely, it quantifies the probability that if the reported winner is incorrect, the audit would still accept that outcome. The audit continues to sample ballots until this "risk" falls below a predetermined limit, typically 5%. Unlike traditional recounts that often only confirm machine tallies, RLAs are designed to detect if the reported outcome is wrong.

RLAs are remarkably efficient. They inspect only a small, randomly selected fraction of ballots. If an election is not close, a very small sample size is sufficient to confirm the outcome. In close elections, the sample size might increase, potentially escalating to a full hand count if discrepancies persist. Rivest noted that RLAs can offer a "200% speed up" compared to full hand recounts, making them practical for widespread adoption. The randomness of the sample selection is critical to prevent adversaries from predicting which ballots will be audited.

Rivest outlined three main paradigms for RLAs:

1. Ballot comparison audit: The most efficient, comparing each selected paper ballot to its corresponding electronic record generated by the scanner.
2. Ballot polling audit: Used when a direct one-to-one electronic record for each ballot isn't available; it samples ballots and manually tallies them, comparing the sample's outcome to the reported totals.
3. Batch comparison audit: The least efficient, focusing on batches of ballots rather than individual ones.

He strongly critiqued image-based audits, where people review digital images of ballots instead of the physical paper. Rivest argued that this approach is flawed because the images themselves are created by scanners and machines, which are precisely the untrusted components the audit aims to bypass. Relying on images does not provide true software independence or access to the primary evidence.

The scope of RLAs extends beyond simple plurality elections. Rivest discussed methods for auditing more complex outcome rules, such as Ranked-Choice Voting (RCV), also known as Instant Runoff Voting (IRV), where voters rank candidates by preference. He mentioned Bayesian methods for auditing, which he explored in a paper filed in arXiv, and noted recent advancements in frequentist means by Philip Stark, Vanessa Teague, and Michelle Blom for handling IRV. This indicates a growing sphere of auditable election methods.

While emphasizing paper-based systems, Rivest also delved into cryptographic voting systems, specifically End-to-End Verifiable (E2V) voting systems. He acknowledged their "heavy duty cryptographically" nature and the skepticism surrounding their complexity, citing Germany's ban on such systems. E2V systems typically involve a public bulletin board where encrypted votes are posted, allowing different parties to verify various stages of the election. The core challenge for E2V is ensuring voter verification that their vote was "cast as intended" (even though encrypted and no receipt is given), "collected as cast," and "counted as collected." This often involves sophisticated techniques like homomorphic encryption (where computations can be performed on encrypted data) to sum votes without decrypting them. Despite their complexity, Rivest noted that E2V systems have been used in test elections and represent a viable, though long-term, research area.

Rivest concluded this section by highlighting hybrid voting systems, which combine voter-filled paper documents with E2V verifiability. These systems allow for auditing through either the paper trail or the cryptographic proofs, offering redundancy and potentially enhanced confidence.

Demo / Proof of Concept

▶ Watch: Explaining preference for simple paper ballots despite MIT background. (6:00)

While Ron Rivest's talk did not feature a live, interactive demonstration of a specific voting system or audit process, he provided crucial examples of where these principles have been applied or are currently being explored as proofs of concept. His discussion served to illustrate the practical feasibility and ongoing development of evidence-based election methods.

One notable example he cited was the Tacoma Park election, where officials allowed a hybrid system combining traditional paper ballots with cryptographic verifiability. The key takeaway from Tacoma Park was the election officials' insistence on the existence of a robust paper evidence trail that could be physically examined. This demonstrated the prevailing trust in tangible evidence, even when advanced cryptographic methods were also employed. The officials, in essence, were willing to "forget all the cryptography" as long as the paper ballots provided an independent, auditable record.

Rivest also mentioned ongoing efforts in the realm of End-to-End Verifiable (E2V) systems. He specifically referenced ElectionGuard, software being pushed by Josh Benaloh, and Free and Fair, which Joe Canary is implementing. These technologies are not merely theoretical; they have been deployed in "some test elections" across various U.S. states, including Wisconsin, California, Idaho, Utah, and Maryland. These real-world applications demonstrate a gradual movement towards incorporating cryptographic verifiability into electoral processes, even if their widespread adoption is still considered a "ways off" by Rivest due to their inherent complexity.

Crucially, Rivest addressed the contentious issue of internet voting and mobile phone voting. He firmly stated that the NASA report recommended against internet voting, and he personally is "not a fan." He cited the conclusion of a Berkeley study group, which, despite seeking to establish standards for internet voting, ultimately found that "the current cybersecurity environment and state of technology make it infeasible for the working group to draft responsible standards to support the use of internet-based ballot return in US public elections at this time." This strong stance, reinforced by his personal anecdote of buying a burner phone for Defcon, underscores the current lack of a secure and verifiable proof-of-concept for online voting, deeming it too dangerous given the current threat landscape.

In summary, while a direct "demo" was absent, Rivest's talk highlighted existing and developing practical applications of his core principles, emphasizing the tangible (paper ballots and audits) over the purely digital (unverified electronic systems and internet voting) in the current environment.

Defensive Implications

▶ Watch: Declaring voting as one of the hardest problems in computer science. (8:00)

The defensive implications stemming from Ron Rivest's talk are clear and actionable, guiding election officials, policymakers, and cybersecurity professionals toward more robust and trustworthy election systems.

1. Universal Adoption of Voter-Verified Paper Ballots: The foremost defensive measure is to ensure every vote is cast on a voter-verified paper ballot. This means actively moving away from purely electronic voting machines that lack a paper trail. Voters must have the opportunity to physically inspect and confirm their choices on paper before their ballot is cast. This paper trail serves as the ultimate "ground truth" evidence, resilient against software manipulation.
2. Mandatory and Robust Risk-Limiting Audits (RLAs): Implementing statistically sound Risk-Limiting Audits across all jurisdictions is paramount. These audits must be conducted before election outcomes are certified and must involve random sampling of paper ballots. RLAs should be designed to detect whether the reported outcome is incorrect and escalate to a full hand count if necessary. Current audit practices, often criticized for being ineffective or merely confirming machine tallies, need to be upgraded to meet the rigorous standards of RLAs. Election officials must also understand that the goal is to audit the outcome, not just the tally.
3. Strict Chain of Custody for Paper Ballots: The integrity of the paper ballot evidence hinges on a secure and verifiable chain of custody. This includes secure storage, transportation, and handling protocols for all cast ballots from the moment they are dropped into the ballot box until the election is certified and all audit processes are complete. Any break in this chain compromises the evidence.
4. Scrutiny of Ballot Marking Devices (BMDs): While BMDs produce paper, defenders must be vigilant about their implementation. If a BMD prints a QR code or barcode that is subsequently read by a scanner, and the human-readable text is not the primary source for the tally, then the system reverts to being software-dependent. Voters must be able to verify the human-readable text, and this text, not a barcode, should be the auditable evidence.
5. Resist Internet and Mobile Voting: Given the current cybersecurity environment, election officials must heed the NASA report's recommendation against internet and mobile voting. The internet is simply too dangerous and complex to secure for anonymous, high-stakes elections. Defensive strategies should focus on securing in-person and mail-in voting processes, not attempting to port them to inherently insecure online platforms.
6. Transparency in Software (Open Source): While not the primary evidence, Rivest advocates for making all voting system software publicly disclosed or open source. This allows for broader scrutiny by the security community, potentially identifying vulnerabilities or malicious code before deployment. Even if the software is untrusted, transparency can aid in understanding potential attack vectors and designing better audit procedures.
7. Public Education and Confidence Building: Defenders should actively engage in educating the public about the mechanisms that secure elections, particularly the role of paper ballots and RLAs. Fostering public understanding of these evidence-based processes can help combat misinformation and build confidence in election results.
8. Distinguish Voting from Related Issues: While important, issues like voter suppression or campaign advertising should be formally distinguished from the technical process of securing the vote. Defensive efforts should focus on ensuring the integrity of the voting and tabulation process itself, while acknowledging these broader societal challenges.

By prioritizing voter-verified paper ballots and robust, statistically sound audits, election defenders can build systems that are resilient to both accidental errors and malicious attacks, providing convincing evidence that election outcomes are correct.

Key Takeaways

• Voter-verified paper ballots are the indispensable foundation of secure elections. They provide the "ground truth" evidence, directly confirmed by the voter, which is crucial for establishing the legitimacy of any election outcome.
• Software independence is a critical design principle. Election outcomes should not depend solely on the flawless or trusted operation of software, which is inherently vulnerable to undetected errors, malicious code, and difficult-to-verify states.
• Risk-Limiting Audits (RLAs) are the gold standard for post-election verification. These statistically rigorous audits efficiently verify election outcomes by manually examining a random sample of paper ballots, ensuring that any incorrect outcome would be detected with high probability.
• The evidence for an election outcome resides in the voter-verified cast ballots, not in the software itself. While open-source software can aid transparency, the focus for integrity must remain on the physical evidence and the processes that verify it.
• Internet and mobile voting are currently too insecure and complex for responsible implementation. The inherent dangers of the internet environment make it infeasible to meet the rigorous security and verifiability requirements of public elections at this time.
• Hybrid voting systems, combining paper ballots with End-to-End Verifiable (E2V) cryptographic methods, show promise for the long term. These systems offer redundancy and multiple layers of verifiability, but their complexity means widespread adoption is still years away.

About the Speaker(s)

Ron Rivest is a distinguished Professor Emeritus at the Massachusetts Institute of Technology (MIT), where his contributions have profoundly shaped the field of computer science. He is most famously recognized as the "R" in the RSA algorithm, the groundbreaking public-key cryptosystem that revolutionized secure communications and computing. This fundamental work earned him, along with Adi Shamir and Leonard Adleman, the Turing Award, often regarded as the Nobel Prize of computer science.

Beyond his seminal work in cryptography, Rivest has made extensive contributions across various domains of computer science, including managing trust, secure naming environments, and, notably, election security. His deep understanding of technical complexities and his commitment to practical, robust solutions have positioned him as a leading authority in the ongoing effort to secure democratic processes. His perspective often challenges conventional wisdom, pushing for simpler, more technically comprehensible solutions that prioritize verifiability and minimize reliance on untrustworthy components. His involvement in the National Academies of Sciences, Engineering, and Medicine (NASA) 2018 report, "Securing the Vote," further underscores his influence and expertise in this critical area.