Before you go, check out these stories!

0
Hackernoon logoCryptography-Based Voting and The US Elections: The Reality by@aberke

Cryptography-Based Voting and The US Elections: The Reality

Author profile picture

@aberkeAlex Berke

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 à VoterPunchscan, 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, rm 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 VirginiaDenver Colorado, and Utah County.