Quick Guide to E2E Verifiable Internet Voting

I’ve spent a lot of time recently on crypto and security stack exchange. Some of the comments I’ve left could make good blog posts, so I will be republishing them here occasionally. This one is cross-posted from here.

Internet voting introduces certain challenges that are not present (or as present) when voting is done in-person and in a private, isolated polling booth. Internet voting is difficult, but not impossible.

In general we want five properties:

  1. Ballot Secrecy – That each voter’s choices remain secret.
  2. Integrity – That each voter’s choice is included unmodified in the final tally.
  3. Untrustworthy Platform – A voter’s ballot should be reliable and accurately transmitted from their personal computer.
  4. Coercion Resistance – A voter should be able to cast the ballot of their choice even if they are voting in an unsupervised environment (and an adversary may be standing over their shoulder).
  5. DOS-Prevention – The system should prevent small-scale and large-scale (D)DOS attacks.

For in-person voting, we concentrate on (1) and (2). For internet voting, we want (1) and (2) plus (3), (4), & (5).

Ballot Secrecy

Most current voting systems only achieve (1) ballot secrecy. For polling place voting, once you leave, you do not have (2) integrity and if you are using a computer (DRE) to cast your ballot, you do not have (2) even if you observe the entire day. It is possible that they even mess up (1): for example, if voters arrive and are timestamped when registered, and then ballots are timestamped when cast, you can correlate votes to voters.

Ballot Secrecy & Integrity

End-to-end verifiable (E2E) systems allow you to achieve (1) and (2). E2E systems have been used for in-person voting in governmental elections: Scantegrity in a municipal election in Maryland. For internet voting, E2E systems that achieve (1) and (2) only (not 3,4,5) include Helios, which has been used in student elections.

These systems work by throwing a bunch of cryptography at the problem. A voter essentially encrypts their vote (either explicitly if using a computer as in Helios, or through some human computable operation if using a paper ballot, like revealing a hidden code in Scantegrity). It is possible to use encryption functions that do not completely lock down the message: for example, you could take some encrypted messages and add them together under encryption and then just decrypt the sum (see homomorphic encryption), or you can take a list of encrypted ballots and shuffle them up under encryption so that you can’t determine which ballot corresponds to which voter (see mix networks). Each step of the tally can be proved to be done correctly with zero-knowledge proofs.

Since the votes are encrypted, they can be posted publicly without breaking ballot secrecy, and voters can check to see that their votes are included unmodified for the final tally.

Ballot Secrecy & Integrity & Untrustworthy Platform

Systems that solve these three problems have not been used in an election yet, however there are two elections on the horizon that will use them: Remotegrity in Maryland (alondside Scantegrity for in-person voting) and the system in Norway.

These systems use two tricks: two-channels with the assumption that either one is trustworthy, and a technique called code voting. Over one channel (e.g., mail), voters receive a list of candidates with a serial number and unique codes (3 alphanumeric characters) beside their names. Over another channel (e.g., internet via their computer) they vote by submitting the serial number and code for the candidate they want. Assuming the computer is compromised, it can see the code but does not know (a) which candidate is being voted for and (b) what the valid code is for the candidate it would like to switch the vote to (or any candidate for that matter). It can guess, which will likely lead to an invalid code or it could just not let the voter submit anything: both have the equivalent effect.

Each vote that is received is posted publicly. Since only the person with the card knows which code belongs to which candidate, no one else knows how anyone voted. Voters can check the list to make sure their vote made it (and then there is some additional steps they can use to lock in their ballots).

Instead of assuming the codes are delivered by mail (which the malicious computer can’t read), they could come through the computer but in the form of a CAPTCHA or something the computer can’t read. One way of doing this is SpeakUp.

In any case, if someone showed their card to an attacker or the attacker was physically present with the voter, they could be coerced. This leads to…

Ballot Secrecy & Integrity & Coercion-Resistance

There are two approaches to addressing the coercion-resistance problem. One is to let voters cast as many ballot as they want, so they can overwrite previous ballots. It is possible to use cryptography to have hidden tags that can link votes from the same voter together, so that only one is kept. The problem with this approach is that an attacker just needs to wait until the end of the voting period (5 min before the polls close) to coerce a voter.

The second approach is to have real ballots and fake ballots. Voters who are being coerced or selling votes can use/sell a fake ballot, and the attacker cannot tell them apart. The tricky bit is to make sure only real ballots are counted and fake ballots are discarded without revealing if a voter submitted a real or fake ballot. Like above, we can solve this by throwing lots of crypto at the problem.

Systems like this are research-level only. None has been used or even planned to be used.

One way of doing this is called Selections. In Selections, voters use a panic password system. To vote, they submit a password. If they use their real password, the crypto ensures the vote is cast. If they use one of a large set of panic passwords, the crypto ensures the vote is discarded. The casting/discarding can be verified to have been done correctly for the set of all votes (not for each individual vote as that would defeat the purpose).

Therefore voters can just make up a panic password (it is easy to do in your head) on the spot if someone coerces them or offers to buy their vote. Later (or maybe they have already) they can cast their real ballot with their real password. No one can link the two together.

Aside: (D)DOS

This is considered a problem that is not completely solvable. An infected computer can always deny a voter from casting their ballot: what the untrustworthy platform property allows is for you to detect this, not prevent it. The DOS attack could also happen at the network level, taking down the server(s) receiving the votes. The integrity property can detect if any ballots are deleted or modified, but cannot prevent this.

The only solution is to use standard approaches for any web-service.

Ballot Secrecy & Integrity & Untrustworthy Platform & Coercion-Resistance

If we set aside the (D)DOS issue, this is the best system that we can achieve. To my knowledge, designing such a system is an open problem. It is non-trivial to compose the solutions for the untrustworthy platform issue with the coercion-resistance issue.

Disclosure

Scantegrity, Remotegrity and Selections are all systems I have worked on.

One response to “Quick Guide to E2E Verifiable Internet Voting

  1. Johna778

    Thanksamundo for the post.Really thank you! Awesome. debeakededbe

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

About Me

Jeremy Clark is currently a postdoctoral fellow at Carleton University working under Paul Van Oorschot. His PhD is from the University of Waterloo and was awarded the Gold Medal. His research interests include the web trust model, cryptographic E2E election systems, and usable security.

%d bloggers like this: