The cryptography behind electronic voting (and why paper ballots are still essential)

As millions of Americans vote in today’s U.S. midterms, most will use paper ballots, which are protected by strict chain-of-custody protocols and, in some cases, statistical audits. You may wonder why we still use paper for our elections and voting systems when tasks like banking, tax filing, and document signing have moved away from paper-based legacy systems and become fully electronic. The short answer: security.

That may come as a surprise to some. After all, cryptography and other security advancements have enabled secure electronic systems for many applications. In fact, cryptography can be used to provide two essential safeguards in elections: keeping (1) individual votes secret while (2) making the final tally independently verifiable. This is exactly the approach of cryptographic protocols like Helios and ElectionGuard. However, Helios intentionally targets lower-risk and lower-coercion settings rather than high-stakes public elections. ElectionGuard, by contrast, is intended for public elections, but not as a replacement for a paper-based system; it is used as a cryptographic layer integrated with traditional voting infrastructure.

In this blog post, we’ll explain how cryptographic techniques can help protect ballot secrecy and prevent manipulation in electronic voting systems, and explore the limitations of these systems. Although cryptography can strengthen election verifiability and have other strong security properties, it cannot fully replace the security and trust of existing paper ballot systems in general elections.

The challenges of electronic voting

The National Academy of Sciences’ excellent 2018 report on election security concludes that electronic ballot return (also known as online voting or internet voting) should not be used in general elections, since “no known technology guarantees the secrecy, security, and verifiability of a marked ballot transmitted over the Internet.”

The difficulty of this problem makes sense when you consider the strong security guarantees any election system requires:

1. Voter privacy must be maintained, even if a voter has a financial incentive to disclose their vote to a third party.

2. Ballot integrity must be maintained. This becomes especially challenging in the electronic setting because, in general, the voter does not hold a cryptographic identity and cannot sign their ballot cryptographically. Oh, and the electronic voting client and server may be compromised anyway.

3. Voters shouldn’t be able to vote more than once, but this is hard to verify without associating votes with their voters. This becomes even more challenging electronically when, again, voters often lack a digital cryptographic identity.

4. Everyone should be able to trust (and ideally verify) that the election result correctly reflects the voters’ intent.

Paper-based voting systems must solve these problems, too. The first three requirements are typically met through standard physical security measures you see in paper ballot election locations: voters identify themselves to polling workers (preventing multiple votes from one person), are given a ballot without their name on it and a secure location to fill it in (protecting voter privacy), and personally hand their ballot to a polling worker and watch as their ballot is submitted for counting (ballot integrity). As with any security controls, there are threats that can compromise these protections; however, compromising them at a nationwide scale is extremely expensive, difficult, and noisy (i.e., detectable) to election observers, making these controls especially effective for large national elections. The final requirement is the most difficult to achieve for paper-based systems, and voters typically have to trust that election workers compute the final tallies honestly, and that chain-of-custody controls coupled with post-election audits would detect any attempt to compromise the election outcome. Cryptography can be used in conjunction with paper-based systems to help strengthen the trust in this final requirement, using what’s known as end-to-end verifiability, as we will explore later in the post.

Electronic systems introduce an existentially dangerous failure mode not present in modern, sensible paper-based systems: a supply-chain or 0-day vulnerability that can scale across many voting machines and jurisdictions could allow one person to single-handedly control and influence the outcome of an election (and, depending on the system and exact vulnerability, possibly while evading detection). In traditional paper-based systems, this risk is sharply constrained by independent physical records and physical security controls. It’s much more difficult for a single person to meaningfully change an election’s outcome while evading detection in this system.

Software security alone is not enough to secure electronic voting systems, though; the key design principle is not only to implement robust security controls but also to design your system so that all failures of those controls are detectable. This can’t be solved only using software whose correctness must be trusted. This property is known as software independence: changes in the election outcome caused by changes or errors (or vulnerabilities) in voting software must be detectable. In practice, this is typically achieved using evidence that can be verified independently of the voting software, such as a paper ballot audit trail.

Inside the design and cryptographic safeguards of electronic voting systems

Now that we’ve introduced the challenges of electronic voting, let’s explore how modern system designs aim to address them. We will focus our discussion on two electronic voting systems in particular: Helios and ElectionGuard. Helios is a complete voting protocol that targets low-stakes elections where coercion is not a concern. Famously, it is used by the International Association for Cryptologic Research to elect its board of directors. ElectionGuard aims to provide end-to-end verifiability on top of existing election infrastructure, and has been tested alongside systems based on paper ballots in College Park Maryland, Preston Idaho, and Fulton Wisconsin. Let’s look at how these systems use cryptography to provide voter privacy, ballot integrity, and end-to-end verifiability.

Protecting voter privacy

Encryption is a natural choice to preserve voter privacy and ensure that cast votes cannot be read by anyone else: by having the voting client encrypt ballots before they are returned, we protect them from being read in transit. But who controls the key we encrypt to? If we encrypt ballots to a public key controlled by the backend server, it could just decrypt each ballot when it is received, which would immediately reveal how users voted. (Even if the ballot is sent anonymously, the backend would still know how users at a particular voting station voted; it would just not be able to associate individual ballots with the corresponding voters.)

One way of solving this problem is to threshold-share the keypair used for encryption, and split the private key between $N$ trusted election officials. This means that a predetermined quorum $t+1\ \leq N$ of the trustees have to be involved in order to decrypt ciphertexts. Using a homomorphic encryption scheme offers further protection for individual encrypted ballots: it allows the backend to compute an encrypted tally from the encrypted votes and only decrypt the final result. As long as $N-t$ election officials are honest, this protects the confidentiality of cast votes from the voting client to the inclusion in the final tally¹.

${{E}_{K}({x}_{1}+\ \ldots \ +{x}_{N})\ ={E}_{K}({x}_{1})\ \oplus \ \ldots \ \oplus {E}_{K}({x}_{N})}_{}$

With homomorphic encryption, the server can compute the encryption of the sum of the individual votes ${x}_{i}$ as the sum of the encrypted votes ${E}_{K}({x}_{i})$.

Schemes like Helios and ElectionGuard use a version of exponential ElGamal to encrypt individual choices on the ballot². If the threshold-shared election key is $K\ =\ {g}^{k}$, the choice $x$ is encrypted as ${E}_{K}(x)\ =\ ({g}^{r},\ {K}^{r}{g}^{x})$, where $r$ is a random scalar. This scheme is additively homomorphic using pointwise multiplication of ciphertexts, as shown below.

${E}_{K}(x)\ \oplus {E}_{K}(y)\ {=}_{}({g}^{r}{\cdot g}^{s},{K}^{r}{g}^{x}\cdot {K}^{s}{g}^{y})\ =\ ({g}^{r+s},\ {K}^{r+s}{g}^{x+y})={E}_{K}(x+y)$

Exponential ElGamal is additively homomorphic if we define $\oplus$ as pointwise multiplication of ciphertexts.

Note that decryption yields ${g}^{x}$ rather than $x$, which is typically hard to invert. However, since $x$ is comparatively small in this case, we can use brute force (or tables) to recover the exponent.

As an example, if we use 0 to indicate No and 1 to indicate Yes, we can compute the number of Yes-votes by summing the individual encrypted votes as described above, and then decrypting the encrypted tally to reveal the result. However, if we don’t ensure that individual ciphertexts are well-formed, a compromised client could simply encrypt the value 1,000,000 to vote Yes a million times. To prevent this, clients must include a zero-knowledge proof ensuring that the encrypted ballot contains a permitted value (or a permitted combination of values).

Protecting against a compromised voting client

What if the voting client is hacked and alters the voters’ choices before they are encrypted, or drops the ballot completely? To protect against client compromise, the voter needs a way to ensure that the backend received their ballot, and that the choices recorded and encrypted by the software client correspond to how they actually voted.

This can be achieved in different ways. Helios and ElectionGuard use a mechanism known as Benaloh’s challenge method. The underlying idea is that when the ballot is encrypted, the voter obtains a commitment to the encrypted ballot and is then allowed to challenge and spoil their ballot. If they do, the ballot is opened and the voter can verify that their choices were recorded correctly and that the commitment corresponds to the encrypted ballot. The device has to reveal the commitment to the voter before learning whether or not the voter wants to challenge the encrypted ballot. Otherwise, it could present a correct commitment only when it is challenged. Moreover, it must be possible to obtain some external validation that the committed ciphertext actually encrypts the voter’s intended choices. Otherwise, the voting client can simply lie and present a plaintext that doesn’t match the commitment.

When the voter is satisfied that the voting client records their choices honestly, they record their choices one last time and cast their ballot, which is then published to a public bulletin board. The voter can use their commitment to check that their encrypted ballot is included in the published election record.

While this protocol provides a method to detect a compromised voting client that tampers with the voter’s choices or drops ballots, it still requires that a significant portion of voters exercise the mechanism in order to ensure that compromised clients are detected with high-enough probability³. Moreover, it does not protect against other types of compromise, like a voting client surreptitiously sending the voter’s plaintext ballot to a third-party server.

Additional issues must be solved in order for this method to be secure. One is the problem of voter authentication: how does the voting client ensure that the voter is eligible to vote, and how do we ensure that only one vote is cast? Additionally, there is the previously mentioned problem of coercion: how do we protect voters from being strong-armed into voting for a specific candidate or issue when voting stations may be spread out all over the world?

Authenticating voters is generally a difficult problem in countries (like the U.S.) that do not have a widely used national ID. However, there are options available for specific groups of voters. For example, some voting systems designed for overseas military voters use the Common Access Card to allow service members to identify themselves. Protecting voters against coercion typically requires that voters are able to vote without being supervised, which seems like a difficult problem to solve using cryptography.

Protecting against a compromised backend

What if the backend server is faulty or compromised by an attacker? With encryption, the backend aggregates the encrypted votes into an election record, computes the encrypted final tally over the encrypted votes, and then lets election officials decrypt the result. Encryption protects voter privacy, but it doesn’t stop the server from dropping, altering, or injecting votes into the election record. How could we allow voters to verify that this did not happen?

If the election record is public (and we can ensure that everyone shares a consistent view of it), voters can verify that their encrypted vote is included in the record using their commitment to their encrypted ballot, as described above. This provides a mechanism to detect a compromised server which attempts to drop or alter votes. Again, we need to rely on active participation from many voters to ensure that a compromise is detected, since a voter can only detect if their individual ballot has been dropped or tampered with.

ElectionGuard extends this idea to allow voters to detect a change in any of the ballots cast before theirs by chaining ballot commitments generated on the same device. Without chaining, the commitment is essentially computed as a hash of the voter’s encrypted ballot. With chaining, ballot commitments are chained as follows:

${c}_{1}=H({c}_{0}\ ,\ {B}_{1})$ ${c}_{2}=H({c}_{1}\ ,\ {B}_{2})$ ${c}_{3}=H({c}_{2\ },\ {B}_{3})$ $\vdots$

When ballot commitments are computed as a chain, the hash chain is published together with the election record. Here, ${B}_{i}$ is voter $i$’s encrypted ballot.

This means that any changes are propagated forward, allowing voters to detect tampering with earlier votes cast using the same voting client.

Detecting a compromised server that injects additional votes is more difficult and usually requires external data, like voter participation records, to solve. It is not enough to associate encrypted ballots with voter identities, since a malicious server could pad the election record with ballots corresponding to abstaining voters.

Once the election record is trusted, it is possible to use zero-knowledge proofs to verify that the final result is computed correctly from the published election record. Since anyone can compute the encrypted tally from the election record, we only need to prove that the final aggregate ciphertext was decrypted correctly.

What cryptography solves that paper ballots can’t do alone: end-to-end verifiability

Recall our fourth requirement for election systems, which we admitted was most difficult to achieve for paper-based systems: Everyone should be able to trust (and ideally verify) that the election result correctly reflects the voters’ intent.

This requirement is usually formalized in terms of end-to-end verifiability, which means that the following should be possible:

1. Each voter should be able to verify that their choices have been correctly recorded.
2. Anyone should be able to verify that the final tally is computed correctly from the election record.

Taken together, these two mechanisms allow voters to independently verify that their vote contributed to the election outcome, without relying on a particular piece of software or hardware (which may be hacked), or external observers (who may not be trustworthy). This property isn’t achievable in exclusively paper-based election systems without introducing some level of trust in humans/institutions overseeing the election. For example, without trusting anyone, how do you know what happens to your paper ballot after you and your vote both leave the voting location? The reason you won’t know this in an exclusively paper-based system is simple: in order to protect vote secrecy, when you submit your ballot to be counted with the other ballots, you intentionally break the link between your identity and your ballot.

Well, using cryptography, you can introduce a mechanism to verify that a cryptographic representation of your vote was included in the election record while still preserving voter privacy! This mechanism is exactly what was described above: encrypt the ballots and publish them to a public bulletin so that voters can privately check that their vote was both included and not tampered with. This allows you to enhance trust in existing paper-based election systems without compromising their security properties. This is the exact design choice behind ElectionGuard.

We won’t be replacing paper ballots any time soon

Helios and ElectionGuard both build on the ideas outlined above, but their use cases differ. Helios explicitly targets settings with low coercion risk and advises against use in high-stakes public elections. ElectionGuard, on the other hand, is built to provide end-to-end verifiability on top of an existing paper-based voting system. Neither protocol makes a general claim to solve the problem of electronic voting because neither achieves the security of status quo paper-based systems purely electronically.

There is widespread agreement among experts on election security that paper ballots are essential for protecting the security and integrity of general elections, and that likely will not change anytime soon. However, cryptographic techniques like the ones described in this post can still be used alongside paper ballots to improve trust in the election outcome by improving the result’s public verifiability and auditability.

If you’re using cryptography to build a new voting system, please reach out. We want to hear about it!