This is a two-part project. This part is about reality. The other part is science fiction. Both are about mobile, blockchain, and cryptographically secure voting systems in the context of US elections. (Science Fiction: link)

With anticipation for the US 2020 presidential election following concerns over foreign intervention in the 2016 presidential contest, there is an important focus on securing our voting systems while increasing voter participation.

Fortunately, cryptographers and technology experts have developed a variety of methods to make voting systems secure, transparent, and openly auditable.

This piece will describe them. Unfortunately, instead of implementing these methods, presidential candidates¹ and election officials have been fooled into promoting and piloting problematic blockchain-based mobile voting systems, which experts have warned against.

They have been told that mobile apps will make voting easier and more accessible, and that blockchains make these systems more secure. However, there are better ways to make voting easier, and these mobile voting technologies only introduce additional security threats.

Blockchains can be useful for building trust in networks of distrusting participants, but they are not pertinent to ensuring the type of trust necessary for the US election system.

Trustworthy election systems are critical to the stability of our democracy and are a matter of national security. Yet many of the machines currently used to tally votes across the US work as “black boxes,” lacking the transparency needed for trust, and have been successfully hacked. Better voting systems are available.

This piece will present how those superior voting systems work with illustrated examples. It will start by describing their common concepts and components to provide a foundation for understanding the more technical systems described later.

For the cryptographically curious readers, a large section will then cover the cryptography behind them in greater technical depth. Those uninterested in cryptography can skip the cryptography section.

This piece will then cover how internet, mobile, and blockchain-based systems fit in, and discuss how any of these systems can, or cannot, contribute towards the goals of securing democracy and elections in the US In particular, increasing access to voting is important, and mobile and internet-voting systems can seem like a way to make voting more convenient and accessible.

Yet the results for whether internet-voting systems that have been deployed actually increase voter participation have been mixed, and each of these systems are deployed at the cost of making elections less secure. The benefits of increasing access to voting are lost if voting systems are then hacked, votes are tampered with, or if voters do not trust election outcomes. The accessibility and security of election systems must be balanced, and claims that blockchains can add security to these systems have been misleading.

What Our Voting Systems Should Provide

First, to evaluate these voting systems, we must assess what properties they should provide:

Integrity. Voting systems must ensure that only eligible voters cast votes, that they vote at most once, and that all votes are counted as cast. In the US this is often handled by registered voters authenticating their identities in person before casting their ballot, and then simply trusting people and machines to properly count their votes. (Read on for how we can do better.)

Secrecy. Voting systems must keep votes secret. In the US this is achieved with private polling booths, where voters fill out their ballots. This privacy feature is crucial to keeping voters safe from coercion and votes safe from purchase.

Auditability. If a voting system or its tally is questioned, it must provide a means for a recount. This is often achieved by keeping paper ballots, even when votes are cast electronically.

Usability. Voting systems must be simple to use. A highly secure system that is too difficult to use may not be adopted, and its security features will then be irrelevant. Or worse, if a confusing system is adopted then voters will misuse it².

We can have more than just these necessary features. Voting systems have been developed that enhance the transparency, verifiability, and security of elections.

They enable any voter to check that their ballot is properly recorded, and anyone to check that ballots are properly tallied, all the while maintaining the secrecy of voters’ ballots.

Developing a system that can provide all of these features may seem untenable, especially given that secrecy and transparency are often at odds. Yet cryptographers, computer scientists, and voting systems experts have developed a suite of techniques to enable “end-to-end verifiability” and make this possible.

End-to-End Verifiable Voting

End-to-end verifiability can be summarized by its two main components:

1. Cast As Intended: Voters can verify that their ballots, whether cast electronically or on paper, are properly recorded.

2. Tallied As Cast: Anyone can verify that all recorded ballots are correctly tallied.

A variety of end-to-end verifiable voting systems have been developed. Some are clever paper-based innovations, invented by creative cryptographers. Others rely on cryptographic tools that have developed over decades.

While these systems vary in the level of technology they use, there are common concepts used throughout them, such as “ballot receipts” which are posted to public “bulletin boards.” These receipts are meaningful enough to the voter who cast the ballot to allow them to verify with the “bulletin board” that their ballot was “cast as intended.”

However, these receipts are either encrypted or contain only partial information about the voter’s ballot, making them meaningless to anyone else. This level of obfuscation is important. The ballot receipts provide no way for voters to prove to anyone else how they voted, which protects votes from being coerced or purchased.

Even if a voter is willing to sell their vote, they have no way of proving to potential buyers how they voted.

Once votes are cast, end-to-end verifiable voting systems employ various strategies to tally the votes in a transparent way, allowing any outside observer to verify that every recorded ballot is correctly “tallied as cast,” while maintaining ballot secrecy.

These systems allow anyone to verify their integrity, yet not everyone has to. Voters who want to continue about their day without the burden of thinking about whether their vote was properly recorded can do so. It only takes a few concerned voters or outside auditors to detect with a high statistical likelihood whether votes were tampered with.

This piece will describe how these mechanisms work in various voting systems. It will start with the simpler paper-based systems in order to make the common concepts of end-to-end verifiable voting systems easier to understand. These paper-based systems presented may have strange looking ballots; they are presented in this way to show how end-to-end verifiable voting can work. The electronic-based end-to-end systems that are built upon similar ideas can have interfaces as simple as the electronic voting systems already in use.

End-to-End Verifiable Voting: Paper-Based Examples

Consider the ‘ThreeBallot Voting System,” published by cryptographer Ron Rivest in 2006. It may look strange or inefficient, but it was not designed for real use. End-to-end verifiable voting had already been developed at this point and his ThreeBallot system was meant to introduce end-to-end verifiable voting, and show how it is possible, to a non-technical audience without using any cryptography. That’s just how we will use it.

In this system, each voter casts three ballots. Each of these ballots has a unique and random ID, and the voter can take home a copy of just one of these ballots as a “receipt.”

These ballots could be on separate pieces of paper, or all on the same piece of paper with perforations between them to allow later separation (as shown in the figure), or they could be filled out via an electronic device.

Figure: An exampleThreeBallot before it is filled out by a voter. Each single ballot on the ThreeBallot has a unique random ID on the bottom. (Image source)

For each candidate, there are then three empty bubbles that a voter could mark. A voter casts a vote for a candidate by marking a bubble on two of these three ballots. They mark a vote on just one ballot for any candidate they are not voting for.

Figure: A filled-out ThreeBallot where the voter cast votes for Bob Smith and Ed Zinn. Note: All three ballots must be read to determine the actual votes cast.

Which bubbles on which of the three ballots are filled in can be chosen arbitrarily. A ThreeBallot is valid as long as for each race, there are two votes for one candidate, and one vote for all of the other candidates.

The result is that all candidates receive one additional vote from each voter than they would have otherwise received. By subtracting the number of voters from the total number of votes for each candidate, the final tally can then be recovered.

When a voter casts their three ballots, they can choose any one of the ballots to copy as their receipt. All of the cast ballots are uploaded with their marked votes and their unique IDs to an online “bulletin board” that anyone can view.

Individual voters can then verify that their votes were properly recorded (“cast as intended”) by checking their receipt against the bulletin board. And anyone can check that the votes from all of the recorded ballots are properly tallied to produce the final result (“tallied as cast”).

Figure: When a voter casts their votes, the individual ballots of a ThreeBallot are separated. All three are posted to the public web bulletin board. The voter can choose one of the three ballots to keep a copy of as a “receipt” and later check for it on the bulletin board to audit whether their votes were properly recorded. If someone were to tamper with even just one of their ballots, the voter would have a ⅓ chance of catching them.

One ballot by itself proves nothing about who was voted for because of the way the votes are distributed across three ballots. This way ballot receipts keep votes secret.

Yet at the same time ballot receipts can be used to detect and prove if anyone tampers with the election. Any ballot that is modified or removed from the bulletin board has a ⅓ chance of being a copy of a voter’s receipt.

The number of voters who need to check their receipts to catch this kind of election tampering is then relative to the number of modified ballots, but only a few voters need to check to catch significant tampering with a high statistical likelihood.

The ThreeBallot system has been criticized for having security and usability issues, but many of these issues can be circumvented with technology that helps voters fill out their ballots (see appendix⁴). With the right user interface, a system like ThreeBallot can provide the average voter with a simple way to vote, such as on just one ballot, with no need to collect a ballot receipt.

It can then expose its complexity to the few concerned voters and auditors who want to verify the system’s integrity and use the receipts and bulletin board. However, the ThreeBallot system was not invented for use. It was meant as a pedagogical tool to introduce end-to-end verifiability with concepts such as “ballot receipts” and public “bulletin boards.”

Other end-to-end verifiable paper-based systems, such as Prêt à Voter, Punchscan, and Scantegrity, were designed for practical deployment and were even used in elections.

Figure: Simple example of a Prêt à Voter ballot. The ballot is shown unmarked, then marked, then as a receipt, which is posted on a public web bulletin board. The ordering of the candidates varies by ballot. On another ballot, candidate Asterix may appear at the top, or appear at the bottom.

A Prêt à Voter ballot has two sides. On one side is a list of candidates in a random order that varies by ballot⁵. On the other side are corresponding bubbles for each candidate that can be marked with a vote. After the voter fills out the ballot, the two sides are separated. Like the previous system, ballots have unique IDs and cast ballots are scanned and uploaded to a public web bulletin board which voters can later check. Only the side of the ballot with the marked bubbles is cast and put on the bulletin board, and the voter can keep a copy of it as a receipt.

Figure: Example Prêt à Voter ballot for the Victorian State elections (Australia). On the right-hand side is the randomly ordered list of candidates. On the left-hand side a voter can mark their choices. The two sides are separated before the ballot is cast. The side with just the marked choices and without the corresponding candidates can serve as a ballot receipt, and can be publicly posted while keeping the voter’s choices secret. (Image source)

With this receipt they can then check that their ballot ID and the order in which their ballot bubbles are filled in are properly recorded on the bulletin board. Since the candidate ordering is removed from cast ballots, the order in which ballot bubbles were filled in keeps votes secret⁶, while still providing voters with a meaningful receipt.

Prêt à Voter was further developed for the 2014 parliamentary elections in the Australian state of Victoria⁷. Since there were so many candidates involved, and their listed order varied by ballot, a digital device was developed for voters to use within the polling booth to cast their Prêt à Voter ballot with simplicity.

The Punchscan system uses a similar concept of a ballot that separates into two pieces. Punchscan was then later developed by its lead inventor into Scantegrity⁷ for easier use.

Figure: A simple example of a Punchscan ballot. Left: The two sheets (separated) of a Punchscan ballot before it is filled. Center: The same Punchscan ballot after it is filled out. Right: The same Punchscan ballot after it is filled out and its sheets are separated. (Source)

A Punchscan ballot is made of two sheets of paper. Each sheet is printed with the same ballot ID on it. On the top sheet are the candidate names and a corresponding symbol by their name. In this simple example, candidate ‘Obama’ corresponds to the symbol ‘A’, and ‘Clinton’ to ‘B.’ This correspondence between candidate and symbol is random across the ballots.

The symbols are printed on the bottom sheet of the ballot and are shown through holes in the top sheet. The order in which the symbols appear within the holes is also random. To vote for a candidate, voters mark the corresponding symbol through a hole with a bingo-style marker. The marker is intentionally oversized to leave a mark on both the bottom and top sheets of paper.

The voter chooses one sheet of paper as a receipt, and the other sheet is shredded. The receipt is scanned for tabulation and uploaded to an online bulletin board which the voter can later check to ensure that their ballot was properly recorded. However, a receipt cannot be used to prove to someone else how they voted. If the top sheet is kept as the receipt then which candidate symbols appeared within which holes is unknown. If the bottom sheet is kept as the receipt then how the symbols correspond to the candidates is unknown. The correspondence between candidates and symbols for each ballot ID is of course securely stored by authorities for later tabulation (see infographic or paper).

Scantegrity works with existing optical scan voting systems used in US elections, and keeps the voting experience unchanged for voters who do not care about end-to-end verifiability features.

Figure: The Scantegrity voting experience. 1. Upon marking a bubble on a Scantegrity ballot, a confirmation code that was printed in invisible ink within the bubble is exposed. 2. Voters who want to verify that their ballot was properly recorded can copy down the exposed confirmation codes along with their ballot ID. 3. Ballots are cast and scanned by an optical scanning system as they normally would be. 4. A voter can later check on the election website that their ballot ID was properly recorded with the exposed confirmation codes. (Image source)

Scantegrity ballots are printed with a unique set of random confirmation codes in invisible ink within the bubbles of each ballot. The codes within bubbles are exposed to a voter when the bubbles are filled in, and can serve as ballot receipts. Voters can copy down their exposed confirmation codes, along with their ballot ID. They can later verify on the election website (the bulletin board) that their ballot was properly recorded by checking that their ballot ID was recorded with the correct confirmation codes.

Scantegrity was extended to a remote voting system, called Remotegrity, to accommodate absentee voters, and these systems were successfully piloted in city-wide elections in Takoma Park, Maryland twice, in 2009 and then again in 2011.

Figure: The Scantegrity voting experience. (Image source)

At this point, you may be wondering what happened to these successful end-to-end verifiable voting systems. For example, after successful pilots, why wasn’t Scantegrity further implemented? Ron Rivest has collaborated with Scantegrity’s lead inventor, David Chaum, on a variety of voting projects, and when I pressed him about this, he gave me a defeated shrug and told me that the market would not pick these systems up⁸. There is a voting technology market, and this market is fragmented.

Different municipalities, each with their own funding constraints, invest in voting equipment to last many years. This piece will later discuss a problematic mobile voting app that has signed pilot contracts with multiple municipalities across the United States, where these pilots are funded by venture capital money. In contrast, the Scantegrity pilots in Maryland were made possible largely due to academic efforts. We need our government to invest in technologies that can enable end-to-end verifiable elections.

Where End-to-End Verifiability Meets Cryptography

Each of these above described voting systems are end-to-end verifiable. They allow any voter to verify that their cast ballot was properly recorded, and anyone can verify that recorded ballots are correctly tallied because the tallying is done in a way that is openly auditable. Exactly how this works for systems like Prêt à Voter and Scantegrity has been glossed over, and requires some cryptography.

Both Prêt à Voter and Scantegrity require a way to securely match ballot IDs to ballot contents. For example, the random ordering of the candidates on each Prêt à Voter ballot must be saved somewhere so that the votes can be tallied.

And similarly, how the codes in the Scantegrity bubbles correspond to ballot IDs must also be handled. Common principles from cryptography are used for this purpose, such as randomness, commitment schemes, and (threshold) encryption.

Ballots must be generated with randomness so that the order of the candidates on a Prêt à Voter ballot, or which codes are printed within which bubbles on a Scantegrity ballot, is sufficiently random, so that no one can use a ballot receipt to determine how someone voted.

Cryptographic commitment schemes are used to ensure that information about the ballots contents, such as Prêt à Voter ballot candidate list orders, or Scantegrity ballot confirmation codes, does not change from before the election to after ballots are cast. This is important to prevent election tampering.

Private data, such as databases that connect ballot IDs to ballot contents, are encrypted and can only be decrypted by trusted election authorities. Trust in the security and decryption of this data does not need to rest on one sole authority. Many encryption systems support what is called “threshold encryption.”

Encrypted data often requires a secret key to decrypt it. With threshold encryption, no single entity holds this secret key. Instead, the information necessary to construct and use this secret key is split across multiple parties, and decryption can only happen when enough of them agree to combine their information.

How many parties are involved, and how many are needed for decryption (the threshold) can vary to meet the needs of the election. For example, different election authorities, and even competing candidate parties, could hold part of the key. More about how threshold encryption and decryption works is in the appendix⁹.

There are other end-to-end verifiable voting systems that use the common concepts of ballot receipts, public bulletin boards, and a transparent tallying process, but with more reliance on cryptography. The following Cryptography section will attempt to describe their common concepts with simplicity, with the mathematical details behind these concepts in the appendix. If at any point the cryptography is not of interest, you can jump below to [cryptography ends here].

When these systems that leverage cryptography are deployed, it is not necessary for the general voting public to know how they work. What is important is that these systems work transparently, so that anyone who does understand them can then verify their integrity. (Note: This is not at all the case for the “black box” voting systems that are commonly used in the US today.)

It is also worth noting that when these end-to-end verifiable voting systems use encryption, it is only to make cast ballots private. Encryption is not used to ensure the accuracy of vote tallies, which can instead be done with statistical means. So if an encryption system fails for some reason, the secrecy of votes may be lost, but the integrity of the election can still be ensured.

Cryptography

Many end-to-end verifiable voting systems share and build upon some common ideas and cryptographic components, such as public key encryption protocols, particularly those that support re-encryption, partially homomorphic encryption, mix-nets, and zero-knowledge proofs. Before covering those, let’s start with the basics.

In public key cryptographic systems, there is a public key, pk, and a corresponding secret key, sk.

Data is encrypted with the public key using an encryption function, and the encrypted data is later decrypted with the corresponding secret key and decryption function to recover the original data. For example, a secret message m (e.g., a ballot) is encrypted to create the ciphertext c.

Enc( pk, m ) = c

This ciphertext c can be openly transmitted and shared without exposing the message m, and can then be decrypted with the secret key.

Dec( sk, c ) = Dec( sk, Enc( pk, m ) ) = m

The public key is public so that anyone can encrypt messages. The corresponding secret key is kept secret so that only authorized entities can decrypt the data.

There are many such public key encryption schemes that allow for threshold encryption so that data can only be decrypted when a threshold number of authorized entities cooperate to produce the secret key⁹.

These same encryption schemes can also support re-encryption and operate as homomorphic functions, which provide helpful features for voting systems, which will be explained. Upon these features we can build end-to-end verifiable voting systems that often fall within two main paradigms:

Those that use homomorphic encryption for tallying, versus those that rely on mix networks (or “mix-nets” for short). Other paradigms have been used as well, such as secure multi-party computation (MPC), but this piece will only focus on the use of homomorphic encryption and mix-nets.

Voting systems that are built with either mix-nets or homomorphic functions, or any other tallying mechanism, are multi-step processes. They can be designed for the same voter experience, and have the same beginning process and the same end results of trustworthy, verifiable, and transparently computed vote tallies.

The process begins with an individual voter who fills out their ballot. This can be done at a polling station in the privacy of a polling booth, or done remotely with an internet or mobile application. In the case of a polling booth, the process can be as simple as using electronic voting devices as those that are commonly used in voting booths today.

Filled out ballots are encrypted and their encrypted ciphertexts can be publicly posted on a web bulletin board. Modifying a cast ballot would modify its ciphertext, so a ciphertext can serve as a secret ballot receipt for the voter, so that they can check that their ballot was properly recorded.

For convenience, the voter might take away a receipt that was derived from this ciphertext and links back to it, such as a QR code or a short hash. Anyone else can then track how cast ballots are tallied throughout the following (mix-net or homomorphic) tallying process, and since posted ballots are encrypted, voters’ choices are kept secret.

Ballots are encrypted with a public key as well as random bits. Commonly used encryption schemes, such as ElGamal encryption, use the same public key to encrypt messages with a different set of random bits each time, where these random bits do not affect decryption. The appendix describes how this works for ElGamal encryption¹⁰.

Consider a filled-out ballot as a message, m, and random bits, r. m is encrypted with r to produce a ciphertext, c.

Enc( pk, m, r ) = c

And can then be later decrypted with the secret key that corresponds to the public key.

Dec( sk, c ) = Dec( sk, Enc(pk, m, r) ) = m

The point of the random bits is that the same message can be encrypted in many different ways to produce different ciphertexts, yet still be decrypted to retrieve the original message. For example, r1 and r2 could be used to encrypt m, producing different ciphertexts, c1 and c2.

Enc( pk, m, r1 ) = c1

Enc( pk, m, r2 ) = c2

Which can be decrypted to yield the same original message m.

Dec( sk, c1 ) = Dec( sk, Enc( pk, m, r1 ) ) = m

Dec( sk, c2 ) = Dec( sk, Enc( pk, m, r2 ) ) = m

To be clear, c1 and c2 will look like random strings of bits or numbers. With the use of proper encryption systems and randomness, they look substantially different from one another, with no indication that they were produced from the same message, m, versus any other message.

This encryption feature is important for keeping votes private. Even if two ballots are filled out identically, the encrypted ballots will look different because they will be encrypted with different random bits.

This flexibility also allows concerned voters or auditors to validate whether their ballots are properly encrypted before being cast. Some voting systems refer to this as “cast or audit,” others as a “challenge.” The idea is that upon filling out a ballot and receiving its encryption, a voter can choose to either cast the ballot or audit the ballot.

If they choose to audit, they receive the random bits used to encrypt the ballot, and since the encryption protocol and public key are public, they can use this information to validate that the expected encryption of their ballot matches the encryption they received. For security reasons, a voting system might then consider the audited ballot “spoiled.”

The voter then fills out a new ballot, which they might fill out differently if the last ballot was revealed, and the new ballot is encrypted with a new set of random bits. The voter can repeat this process again and again until they are satisfied that the encryption process is trustworthy. Or they may choose to not bother with the audit at all.

For the case of in-person voting, devices that handle the processes of filling, encrypting, and casting ballots, need not know anything about the identities of voters (and these processes can even be handled by separate devices). Voters’ identities should be authorized separately beforehand, such as when entering a polling station.

When vote creation devices are oblivious to voters’ identities, they have no way of distinguishing between the average voter who will not care to verify their vote, or a potential inspector who will audit the device. This hampers the ability of malicious vote creation devices to “cheat” when audits are conducted randomly.

Internet voting applications, such as Helios, have similar means for an audit by providing transparent client-side application code, allowing the voter to audit encrypted ballots before casting their final ballot with their credentials.

Homomorphic Encryption

Homomorphic encryption allows for computations on ciphertexts so that the decrypted result of the computations is the same as if the computations had been on the unencrypted values.

With homomorphic encryption, votes from encrypted ballots can be combined while the ballots are encrypted. The combined result can then be decrypted to show the final vote tally without ever exposing the votes of the individual ballots. In other words, cast ballots remain encrypted to keep votes secret while their combined tally can be mathematically guaranteed.

In general, a homomorphic function is a function where applying the function to individual inputs and then combining the individual outputs has the same result as first combining the inputs and then applying the function to their combination.

i.e. for function f and inputs m₁, m₂, …, mɴ

f( m₁ ) • f( m₂ ) • … • f( mɴ ) = f( m₁ • m₂ • … • mɴ )

For (partially) homomorphic cryptosystems, the function is encryption, and the composition (i.e. the way to combine elements) is either addition or multiplication¹¹.

Partially homomorphic cryptosystems that support addition, such as the Paillier cryptosystem, can be used to tally votes by simply summing the ciphertexts that represent their encrypted values, and then decrypting the sum.

For example, consider ballots (messages) m₁, m₂, …, mɴ with ciphertexts c₁, c₂, …, cɴ.

c₁+c₂+…+cɴ = f( m₁ )+f( m₂ )+…+f( mɴ ) = f( m₁+m₂+…+mɴ )

Decrypting the sum of c₁+c₂+…+cɴ produces the same resulting vote tally as would simply summing the unencrypted values m₁+m₂+…+mɴ.

Votes can also be tallied with partially homomorphic cryptosystems that are multiplicative instead of additive, such as with ElGamal encryption. This use of ElGamal is sometimes referred to as “exponential ElGamal” and it essentially uses the multiplicative properties of ElGamal encryption to perform addition over votes encoded in exponents.

Since additive cryptosystems like Pallier can be cumbersome, this is what is more commonly used. How this can be done is shown in the appendix¹³.

For either additive or multiplicative homomorphic encryption, it must be shown that encrypted ballots are valid. For example, a voter should not be able to submit more than one vote for a US presidential candidate. This is handled with (non-interactive) zero-knowledge proofs.

Zero-knowledge proofs provide a computational mechanism to prove something is true without revealing the information that makes it true. For example, they can be used to show that a ballot is valid without revealing the votes on the ballot. The devices that cast encrypted ballots can then also submit accompanying zero-knowledge proofs to show that each encrypted ballot is valid.

Mix Networks

In 1981, Chaum proposed an “untraceable electronic mail” system built upon public-key cryptography. His paper noted how it could be used in an election to allow voters to remain anonymous while verifying that their ballots were properly counted.

While this particular system was not used for elections, an important concept that was further developed and reused again and again came out of it: Mix networks.

A mix is a server to which a batch of encrypted messages (e.g., encrypted ballots) are sent as input. The mix re-encrypts the encrypted messages, shuffles them, and outputs them in a new order¹³.

Since only the mix server has access to the information that re-encrypts the messages, the mix obscures which input messages correspond to which output messages. A (zero-knowledge) proof provided with the output messages can show that the set of messages that enters the mix is the same set of messages that exits it, just with new encryptions.

Figure: A mix-net illustration from the Wombat end-to-end verifiable voting system, which uses mix-nets in its tallying process. Each gray block represents a mix server that takes in a batch of encrypted messages as input (A, B, C, D), and re-encrypts and shuffles them before outputting them. The next mix-net in the sequence takes that output and repeats this process. At each mix server in the mix-net, the messages are re-encrypted and shuffled. The final output can be safely decrypted because no observer will know which decrypted output message corresponds to which encrypted input message.

This process of re-encrypting and shuffling a set of encrypted messages is done again and again, sequentially in a sequence of mix servers that make up the mix network (or “mix-net” for short). The output set of encrypted messages from one mix is the input for the next mix in the sequence.

When the re-encrypted messages exit the final mix, they are considered sufficiently shuffled. They can then be safely decrypted (e.g., with threshold encryption) because no one can trace back which decrypted message corresponds to which encrypted message that originally entered the mix-net.

For voting applications, the encrypted messages that enter a mix-net are the encrypted ballots posted to a public bulletin board. When they exit the mix-net, the ballots can they be safely decrypted and tallied in the open. Anyone can follow the ballots throughout this transparent process, from bulletin board, through each step in the mix-net, to tallying, to verify that votes are properly handled.

The mix-nets originally proposed by Chaum operate like onion routers. Mix-nets used for more modern end-to-end voting applications are slightly different and are more flexible, allowing potentially arbitrary sequences of mix servers.

They work by leveraging a feature of re-encryption where encryption can be composed. The ElGamal encryption system is used as an example cryptosystem with this feature (with the mathematical details of how this works in the appendix¹⁰), but this feature is not dependent upon any one cryptosystem.

As an example to show how mix-nets can use this re-encryption feature, consider a message m (e.g., a ballot), encrypted with public key, pk, and random bits, r₁, to produce a ciphertext, c1.

Enc( pk, m, r₁) = c₁

This ciphertext, c1, can be used as a message for another round of encryption that uses the same public key as the first round, but with new random bits, r₂, to produce a new ciphertext, c₂.

Enc( pk, c₁, r₂ ) = Enc( pk, Enc( pk, m, r₁ ), r₂ ) = c₂

This is mathematically the same as composing the random bits to make r₁+r₂ and just encrypting the original message, m, with r₁+r₂ to produce c₂ instead.

Enc(pk, m, r₁+r₂) = Enc(pk, c₁, r₂) = Enc(pk, Enc(pk, m, r₁), r₂) = c₂

(The appendix shows the math of how this works with ElGamal¹⁰.)

The sum of r₁+r₂ is just another set of random bits that could have been randomly chosen to encrypt m in the first place. The resulting ciphertext c₂ is therefore another valid encryption of message m. In the same way that the secret key, sk, corresponding to the public key, pk, can be used to decrypt c₁, it can then be used to decrypt c₂.

Composing encryptions in this way can be done again and again. Ciphertext c₂ can then be used as a message and re-encrypted with a new set of random bits r₃, to produce ciphertext c₃, and this re-encryption result will be the same as if message m was originally encrypted with r₁+r₂+r₃.

Each mix in a mix-net can re-encrypt a set of encrypted ballots in this way, each using different random bits, but the same public key. Each mix must then prove that the set of ciphertexts that enter it and the re-encrypted set of ciphertexts that exit it contain the same underlying set of messages. That is, the mix must prove its integrity, that no messages were tampered with, removed, or inserted. This can be done with the Fiat-Shamir heuristic to produce a type of non-interactive zero-knowledge proof (see appendix for more details¹⁴).

[Cryptography Ends Here]

Voting Systems in Practice

These cryptographic tools have been developed over decades and used in a variety of end-to-end verifiable voting systems. In 2006 Josh Benaloh, who is a Senior Cryptographer at Microsoft Research, published a proposal for Simple Verifiable Elections showing how to put together necessary cryptographic components in a simple way. He described how a system could be implemented for both in-person voting as well as remote voting.

These ideas have since been developed into numerous working end-to-end verifiable voting systems and used in elections around the world. To name a few, these systems include the open source project Helios, Wombat, and STAR-Vote.

They may differ in exactly which cryptographic tools they use, but as end-to-end verifiable systems, they are secure and transparent in how they work. What these systems do not do is distribute the collection or storage of votes with a blockchain. They have no reason to. As Benaloh has stated, “Blockchains are a very interesting and useful technology for distributed consensus where there is no central authority. But elections just don’t fit that model.”

We already cast our votes with centralized US election authorities; end-to-end verifiable systems then allow us to verify that votes are “cast as intended” and “tallied as cast.” In elections where there is less trust in a single governing authority, these systems can use threshold encryption in order to decentralize the information necessary for decrypting votes. This too is of course done in an openly verifiable way. And this too does not require a blockchain.

Despite this, attention has been given to blockchains as a means to secure elections. Blockchain-based mobile voting apps, such as Voatz, have recently attracted support and funding from venture capitalists, and seem to use “blockchain” to attract attention and to claim that they enhance election security.

These mobile apps are also popular because they enable remote voting over the internet. Voting online, whether with mobile apps or with computers, may seem intuitive and appealing as we conduct so many other transactions online, such as with online banking and online shopping. Promoters of mobile voting see it as a way to make voting easier, more accessible, and to increase voter participation.

They can look to examples in countries such as Australia, Norway, Switzerland, and Canada where internet based voting systems have been piloted in binding elections. Or the country of Estonia, which has used internet-based voting (i-voting) for general elections since 2005.

Yet there is still no evidence that putting elections online actually increases participation. Studies on whether these internet-voting systems have led to increased voter turnout have shown mixed results. And putting elections online in this way opens up security risks.

Online voting must be treated with different security concerns than online banking and online shopping. These online systems do get compromised — credit card fraud and identity theft do happen. Such failures are tolerated, as credit card companies or online merchants absorb the costs because the net gains from these online systems still benefit their economic interests.

Our democracy does not have the same means to recover from these kinds of online security breaches or failures. When elections are put online, a trade-off is made between accessibility and security. In many cases the governing election authorities may determine that the risks of election hacking or coercion are low, deeming internet-voting appropriate. However, the US 2016 presidential elections showed that is not the case for the US and that our voting systems must be designed to protect against foreign interference.

The inventors of end-to-end verifiable voting systems have often cautioned against mobile or internet-voting in important elections where interference is anticipated, even though their systems can support mobile and internet-voting. In the words of the creator of the end-to-end verifiable system Helios, “For some elections, notably US Federal and State elections, the stakes are too high, and we recommend against capturing votes over the Internet.”

While the ubiquity of mobile apps and the focus on blockchains may be relatively new, the concept of remote voting and issues regarding internet voting are not. US voters can send in absentee ballots by mail, email, or fax, depending on their State.

This is a form of remote voting, and absentee ballots have been available in the US since the times of the Civil War, when states extended the vote to military personnel stationed outside their home districts.

Vote by mail with absentee ballots: Civil War cover for mailing Ohio’s 1864 state election tally sheet from out-of-state military voters. (Source: Smithsonian National Postal Museum)

In the early 2000’s the US Department of Defense pursued a congressionally mandated online voting project for military and overseas voters. However, after evaluating the feasibility of securely submitting votes over the internet and ensuring the legitimacy of ballots, the Pentagon cancelled this program in 2004, citing security concerns.

Yet serious proposals and pilots for internet voting continued in the U.S. This led to a group of respected computer scientists issuing a cautionary statement in 2008 about the “serious, potentially insurmountable” challenges standing in the way of creating a safe internet-based voting system.

Vote by mail with absentee ballots: Drawing of Pennsylvania soldiers voting by William Waud, published in Harper’s Weekly, October 29, 1864. (Source: Smithsonian National Postal Museum).

Concerns regarding internet voting are not just about cyber security and malware compromising users’ systems. They are also about voter coercion and authentication. Remote voting systems cannot ensure the secrecy of ballots in the way that the privacy of in-person voting booths can, making voters vulnerable to coercion, and elections vulnerable to vote-buying.

How to best remotely authenticate the identity of voters, to ensure that only eligible voters vote, and that they vote at most once, is an open question.

Blockchain-Based Mobile Voting Apps: A Problematic Example

Despite the decades of developments and security concerns from computer scientists and voting systems experts, there is renewed interest in internet-based voting for US elections, this time with a focus on blockchains and mobile apps.

One such mobile app, Voatz, has recently done a series of pilots in West Virginia, Denver Colorado, and Utah County.

Voatz handles remote authentication by requiring its users to upload either their state ID or their passport photo ID page, along with a live “selfie” video of their face through the Voatz app.

Voatz has contracted third-party companies to handle this authentication procedure. For their Denver pilot, this third-party was a Palo Alto company named Jumio. Jumio uses machine learning facial comparison software to compare the uploaded photo ID and selfie in order to authenticate the user.

This introduces new accessibility concerns. For example, facial recognition software has been shown to perform poorly on dark skinned people as compared to their lighter skinned counterparts. This process also raises privacy and security concerns. Jumio’s terms of service grants Jumio “a perpetual and irrevocable license to use, reproduce, modify, create derivative works from, distribute, perform, transmit, anonymize and display the User Information (including any rights specifically pertaining to biometric information)…”. Voatz sends sensitive user information to Jumio, and seems to have granted Jumio the right to keep and use it for their own purposes.

As for their use of blockchains, blockchains seem more useful for marketing than securing the transmission of ballots, to which they add unnecessary complexity.

Voatz claims its system is more secure due to blockchain technology, but has not specified why, or what threat model a blockchain secures it against. A caveat to its use of a distributed blockchain is that the final step in the Voatz process is the printing of paper ballots for each mobile vote recorded.

Election officials then tally these printed ballots with their standard processes. This centralized reliance on election officials to properly handle printed ballots seems at odds with whatever benefits a distributed blockchain could have possibly provided.

Another issue is transparency. Other than saying that their blockchain is built using HyperLedger, Voatz has provided little information about its blockchain or its management.

Voatz has made neither its blockchain nor its source code open or transparent for outside audit. Nor has it answered the numerous other questions posed by voting systems experts, such as how the system can be audited, how voters can verify that their ballots were properly recorded and counted, or how votes are kept secret and voters protected from coercion.

The system does not show that it provides the features of integrity, secrecy, or auditability that the US election system necessitates, or that it provides transparency, verifiability, or security, as end-to-end verifiable systems do.

Why have US local election officials partnered with Voatz on pilots? At least in the case of the pilot in Denver, Colorado, there was no financial cost to Denver. The pilot was completely funded by a venture capitalist’s organization.

In general, Voatz has positioned each of its pilots as a means to improve the convenience and security of voting for overseas military personnel. Given that it would be politically unsavvy to stand in the way of these initiatives, it is understandable that this has been a successful approach.

However, mobile voting is not the only way to improve voting for those deployed overseas, who have traditionally used absentee ballots that they submit by either postal mail, fax, or email. The military excels in logistics and is accustomed to securely moving materials in and out of war zones.

Paper ballots are likely among the simplest items to securely get to and from soldiers. If the U.S. government wanted to commit effort to improve the security of absentee ballots for soldiers, and give soldiers the comfort of time and convenience to vote, they could likely do so.

Social Changes and Technical Changes

Improving access to voting and increasing voter turnout are important initiatives towards advancing our democracy, but the US does not need mobile apps or internet-voting systems, and the security concerns they introduce, to pursue these goals.

In the words of cryptographer Ron Rivest, who developed algorithms that help make the internet more secure, “Voting is too important to put online.” Social changes, rather than technical changes, can make voting more accessible: extend the number of days and hours when people can go to the polls (many states and counties already have early voting, such as New York), or make election day a national holiday.

A voting holiday could be a day to celebrate the triumphs of democracy, as patriotically as we celebrate July 4th.

Technology can still play an important role in the future of voting. While social changes can make voting more accessible, technical changes can make voting more secure.

End-to-end verifiable voting technology can enhance the integrity, transparency, and security of elections. This is in contrast to hackable “black box” voting systems in current use, or mobile internet-based apps like Voatz that have been successfully marketed with blockchains.

Experts have been researching and advocating for end-to-end verifiable voting systems as a means to make secure and transparent elections possible for decades, and these systems should be used.

Appendix

footnotes and details

[1] Andrew Yang is a 2020 presidential candidate and has blockchain-based mobile voting as part of his campaign platform.

From https://www.yang2020.com/policies/modernize-voting/; Accessed Jan. 2020

[2] An example of why “usability” is important in the design of voting systems: In the 2000 presidential election in Palm Beach County, Florida, a confusing ballot design (the “butterfly ballots”) caused many voters to accidentally vote for the wrong candidate or spoil their ballots (link).

[3] For the ThreeBallot system to keep votes secret, some assumed conditions must be met. Each of the individual three ballots on a ThreeBallot have unique IDs. These ballots are separated when the voters cast their votes, and all ballots are posted on the bulletin board. No one should then be able to figure out which three ballots go together, because then someone’s receipt could be used to figure out how they voted. It is therefore important that the unique IDs on the three ballots are randomly distributed.

[4] In his critical “The Trouble With Triples” paper, Charlie Strauss of Verified Voting New Mexico described issues he found in Ron Rivest’s ThreeBallot voting system. This critique led Rivest to revise ThreeBallot. However many of the issues Strauss found can be resolved by an electronic device and clear user interface to help voters cast their ThreeBallots. Below are short descriptions of issues Strauss found, and how an electronic voting device used to cast the ballots could circumvent them.

Coercion Issue: Pattern Attacks. A voter could be told to fill our their ballot with a specific and unusual pattern. Since all ballots are public record on the public bulletin board, the vote coercer could check that the voter voted as instructed. Tech solution: Voter indicates votes on device, and the device fills out the ThreeBallot with a random distribution that matches their indicated choices. The voter can check the device did so correctly. A voter has no opportunity to mark ballots with a specific pattern.

Coercion Issue: Voter records all 3 ballot IDs. Strauss says a voter could record all 3 of their ThreeBallot IDs to provide to their vote coercer as proof of their vote. Tech solution: Ballot IDs are not revealed to the voter, except for the ballot they choose to keep as a receipt.

A large part of Strauss’ critique was that the ThreeBallot voting system was about its daunting complexity for a voter, especially for ballots with many choices. This too can be resolved with a simple user interface on an electronic voting system that shields the average voter from its complexity. The average voter can simply select their choices once, while the system fills out the ThreeBallot for them. Then only auditors or concerned voters need utilize the full end-to-end verifiability features of the ThreeBallot system.

[5] The candidates on Prêt à Voter ballots are listed in a pseudo-random order that differs by ballot. Changing the order of candidates might help prevent bias towards the top candidate, but is not always appropriate by US election rules.

[6] With Prêt à Voter, votes can even be kept secret from the device that scans and uploads ballots to the public web bulletin board. The side of the ballot that records how votes were filled in can be separated from the side that matches votes to candidate names before the ballot is scanned. Designing Prêt à Voter to work this way is just one small example of how the creators of end-to-end verifiable voting systems are mindful of security and the ways that the devices and technologies involved in their systems can be potentially compromised. They design their systems so that the roles of the necessary devices can be separated and the devices can work with as little information about voters or ballots as possible.

[7] The implementation of Prêt à Voter developed for the 2014 parliamentary elections in the Australian state of Victoria supported ranked choice and single transferable votes. Many other end-to-end verifiable systems can support ranked choice voting as well, but the Prêt à Voter design provided for an especially clean implementation.

[8] Many of the ideas and implementations of these end-to-end voting systems were pioneered by a small set of computer scientists who are well known and respected in the academic world of cryptography and voting systems. They include but are not limited to David Chaum, Ron Rivest, Josh Benaloh, and Ben Adida.

[9] There are issues with the US voting technology market picking up end-to-end verifiable systems, and STAR-vote, an open-source end-to-end verifiable voting system, provides a case study example of such issues. It was slated for implementation in Travis County, Texas for the 2020 elections, with an RFP, but the project was put on hold because no vendors submitted satisfactory bids for the RFP. This is despite the fact that the system would cost less to implement and service than standard voting system products.

Cryptography Section Appendix

The following notes are for the Cryptography section. These notes assume familiarity with modular arithmetic.

[10] With threshold encryption, no single entity holds the secret key. Instead, the information necessary to construct and use the secret key is split across multiple parties, and decryption can only happen when enough of them agree to combine their information. Consider the number of parties involved as n, and the desired number of threshold shareholders needed to decrypt as k. n and k can be varied to meet the voting system’s needs. How could this be done? The idea described below is a brief sketch of Shamir’s (k, n) secret sharing scheme and is meant to provide intuition for how this could be possible, rather than a detailed implementation.

Core to the idea is that it takes k points to define a polynomial of degree (k-1). So consider a polynomial with k coefficients a₀, a₁, a₂, a₃, … , a₍ᴋ₋₁₎

f(x) = a₀ + a₁∗x + a₂∗x² + a₃∗x³ + … + a₍ᴋ₋₁₎∗x⁽ᵏ⁻¹⁾

This polynomial can be constructed by setting a0 as the secret key that must be shared, and choosing the remaining k-1 coefficients randomly. Each of the n shareholders get a point (x, f(x)) defined by the polynomial. I.e. shareholder 1 gets point (1, f(1)), shareholder 2 gets point (2, f(2)), and so on.

No one shareholder knows the polynomial, each shareholder is only given their point. And due to its random construction, the polynomial and secret f(0) = a0 value are computationally hard to guess. When at least k shareholders cooperate they can use their points to reconstruct the polynomial (e.g., with Lagrange interpolation) and recover the secret key (f(0)).

This polynomial is defined over a finite field, such as the integers modulo p, Zp, where p is a prime number greater than n and the number of possible secrets.

[11] This note is to show how ElGamal encryption uses random bits to encrypt a message. This allows encrypting the same message multiple times to produce different ciphertexts, each time using different random bits, but with the same public key. This encryption scheme also then supports re-encryption, where a ciphertext can be encrypted again, with new random bits, to produce a new ciphertext, where this new ciphertext can still be decrypted with the secret key to yield the original message. This latter feature is exploited for the above described use of mix-nets.

With ElGamal, a large prime number p and a generator g of the multiplicative subgroup of integers modulo p are chosen and publicly shared. A public key can then be defined as a tuple (G, g, q, h) where G is the cyclic group with generator g, and q is the order of the group. A secret key s where s<q is chosen randomly. h is computed as h = gˢ mod p.

For convenience, mod p is omitted from the below description, but all computations are done mod p.

A ciphertext is also a tuple. Let M be a message. The random value r where r<q is chosen and the encrypted message is the tuple.

(x, y) = (M∗hʳ, gʳ)

Note that the part of the ciphertext, x of (x, y), that hides the message M is hʳ and h=gˢ, so hʳ = gʳˢ.

The other item in the ciphertext is y = gʳ. Decryption can then be done with secret key s by computing yˢ = gʳˢ = hʳ.

x/yˢ = M∗hʳ/gʳˢ = M∗gʳˢ/gʳˢ = M

The security of this protocol is based on the Diffie-Hellman Assumption and decryption without knowledge of the value of s is assumed to be computationally hard.

Encryption can then be composed for re-encryption with new random values, such as r1 or r2. For example, consider

(x1, y1) = (x∗hʳ¹, y∗gʳ¹) = (M∗hʳ⁺ʳ¹, gʳ⁺ʳ¹)

and

(x2, y2) = (x∗hʳ², y∗gʳ²) = (M∗hʳ⁺ʳ², gʳ⁺ʳ²)

(x1, y1) and (x2, y2) are both valid re-encryptions of (x, y) that can be decrypted with s to recover the same original message M.

[12] A note on using partially homomorphic cryptosystems for vote tallying: Partially homomorphic cryptosystems that support either addition or multiplication can be used. Fully homomorphic cryptosystems support both addition and multiplication but they are more complicated and unnecessary for tallying votes, which can be done with either addition or multiplication.

[13] ElGamal is a multiplicative homomorphic cryptosystem. It can be used as “exponential ElGamal” to add encrypted votes, where votes for candidates are encoded in exponents, so that their final sum can then be decrypted for the final vote tally. In this case, a single vote may be a vector of 0s and 1s, e.g. <0, 1, 0, …, 0>, where each index in the vector corresponds to a candidate. So if there are N candidates, ordered as Alice, Bob, Carol, …, then a single vote can be encoded as a vector of length N, where a 1 in the second index means a vote for the second candidate, Bob. A vote vector can then be encrypted element-wise, e.g.,

c = <Enc(0), Enc(1), Enc(0), …>

And no one else should be able to know which encrypted elements in the vector correspond to 0s or 1s, since each element is encrypted with different random bits, r.

Votes can then be combined element-wise. So if voter 1, voter 2, and voter 3 have encrypted vote vectors

c1 = <Enc(0), Enc(1), …>

c2 = <Enc(1), Enc(0), …>

c3 = <Enc(0), Enc(1), …>

Then their votes can be combined while encrypted as

c1 • c2 • c3 = <Enc(0)•Enc(1)•Enc(0), Enc(1)•Enc(0)•Enc(1), …>

c1 • c2 • c3 = <Enc(0 • 1 • 0), Enc(1 • 0 • 1), …>

When the encrypted votes of 0s and 1s are combined, they are essentially summed, so once all of the encrypted votes are combined, their combination can then be decrypted and the final tally for a candidate is the sum of the number of 1’s they received.

How is this done with ElGamal? Recall from the above descriptions that a message M is encrypted with public key (G, g, q, h) as

(x, y) = (M∗hʳ, gʳ)

Where g is a generator for a group G of order q, and h = gˢ mod p, with secret key s and prime p.

Before, we saw that if a vote (message) was m, then M = m. Now the message m is encoded as

M = gᵐ

Where the message m is either a 0 or 1, so

M = g⁰ = 1

or

M = g¹ = g

This scheme can now combine messages using multiplication in a way that is additively homomorphic. For example, for vote messages m1 and m2,

E(m1) ∗ E(m2)

= (gᵐ¹∗hʳ¹, gʳ¹) ∗ (gᵐ²∗hʳ², gʳ²)

= (gᵐ¹⁺ᵐ²∗hʳ¹⁺ʳ², gʳ¹⁺ʳ²)

= E(m1 + m2)

If all the vote messages for a given candidate, m1, m2, m3, …, sum to the tally t, then the result will decrypt to gᵗ. Taking discrete logarithms and recovering t from gᵗ is generally considered hard, but the tally t is relatively small and can be determined by exhaustive search or other more efficient methods (e.g. precomputed tables or the “baby-step giant-step method”) and can work for values of t well in excess of the number of voters in any precinct.

For a more complete description, see the paper “A Secure and Optimally Efficient Multi-Authority Election Scheme.” The paper also shows how it can be proved that each encrypted vote is valid.

[14] When a mix server in a mix-net re-encrypts and shuffles a set of messages, instead of using randomness to permute the order of the messages, it could simply output the ciphertexts in lexicographical order.

[15] Each mix in a mix network is responsible for re-encrypting and shuffling a set of ballots, without knowing their decrypted contents. This can be done in a verifiable way using the Fiat-Shamir Heuristic. Josh Benaloh clearly explains how in his paper “Simple Verifiable Elections.” The basic idea is for the mix to produce multiple sets of re-encrypted ballots, including the output ballot set, and show that each ballot set is equivalent. The reason that multiple ballot sets are used is to create a layer of indirection. A direct demonstration that the input and output ballot sets were equivalent would defeat the entire purpose of the shuffle.

Thank you to Rhys Lindmark (MIT Digital Currency Initiative), Josh Benaloh (Microsoft Research), Susan Dzieduszycka-Suinat (US Vote Foundation), Ron Rivest (MIT), and Hannah Sears for contributing their helpful time and feedback.