Secure Internet Polling

Question

In the United States, there has been a lot of talk about creating a secure polling system that would operate over the internet. I have also heard that Securing a poll over the Internet is impossible. The system would need to be secure enough that politicians could make policy decisions based on voter decisions and be (reasonable) certain that the results had not been bought, hacked, or filled with spam votes.

So my question to security experts is: Is it possible? And what is the best security setup that is currently available? (code, language, servers, everything you consider important.)

Answer 1

Voting in a polling booth definitely has advantages as you can enforce that a voter is isolated. That makes internet voting difficult, but not impossible. In general we want some of 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 want (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.

Answer 2

There are two (four technically, see link below) basic problems that need to be solved:

1. How do you prevent false voting (coerced, bought, multiple votes, etc)?
2. How do you protect the person's right to voter privacy?

To solve problem one you need to secure the voting station (the website), the connection to the website, the computer browsing the website, and the person doing the actual voting. Securing the website isn't impossible; securing the connection isn't impossible; securing the computer is next to impossible; and securing the person voting would be done through auditing and authentication. I.e. John Smith (with authentication credentials xyz) voted once for Peter Doe in the presidential election. This adds another problem of what do you use for authentication though? This is kind of like how online banking is protected. If something goes wrong, there is an audit trail, and the bank corrects the problem after reviewing the audit.

This however totally, completely, absolutely makes problem two impossible to solve. To protect the privacy of the person, you can't know what they voted, but to protect the integrity of the election, you need to know what the person voted.

Bruce Schneier has written about this problem quite a bit: http://www.schneier.com/blog/archives/2004/11/the_problem_wit.html

Answer 3

Internet Voting from home or office computers for high-stakes elections is pretty far off the scale of "unsolved problems". It is particularly important to voters who are overseas and/or in the armed forces and have no fast, reliable way to return a voter-verified paper ballot (think submarines :). It was nominated as worthy of an X-PRIZE at DESSEC: DEsigning a Secure Systems Engineering Competition

Ron Rivest, the "R" in "RSA", gave one of several convincing talks on that at the 2010 UOCAVA Remote Voting Systems Workshop. You can see the presentations on the "Agenda and Presentations" page here http://www.nist.gov/itl/csd/ct/uocava_workshop_aug2010.cfm

The problem is much harder than the secure e-commerce problem since votes must be anonymous, the voter must be protected from coercion and prevented from selling votes, and the system must be highly transparent. It also involves:

1. the intractability of securing servers in a world with attacks like stuxnet from well-funded attackers
2. the intractability of securing clients in a world of viruses and inexperienced users
3. the ease of DDNS attacks on servers that have to be up during a particularly crucial day and hour.

In reviewing the recent crash-and-burn of an Internet Voting public test by the District of Columbia, the Washington Post got it right.

See more at the USACM Issue Brief on Internet Voting and UOCAVA - http://usacm.acm.org/usacm/PDF/IB_Internet_Voting_UOCAVA.pdf

On the other side of the coin, some amazing advances are being made in end-to-end independently verifiable elections. in E2E elections, clever cryptographic and zero-knowledge methods are used to allow the voter to actually prove to themselves (but only to themselves) that their vote was counted properly in the final tally. Furthermore, anyone can analyze the public, but anonymized, "bulletin board" of all votes to see the the total was added up properly. For example, that has been demonstrated for in-person elections at a Takoma Park election in 2009, using the scantegrity system. There is currently an effort to satisfy many, but not all, of the requirements above for remote voters via the related "Remotegrity" project being considered for Takoma Park elections in 2011.

Another example of E2E voting is the free online open source un-patented Helios Voting system, which is suitable for use in low-stakes elections (e.g. for the board of a non-profit organization, or even for a simple poll among friends) where adversaries are unlikely to mount a big DDOS effort or employ a variety of zero-day attacks in order to steal votes, prevent people from voting, or otherwise disrupt the election. See also the comments of Ben Adida, author of Helios, at In what ways does Full or Partial Homomorphic Encryption benefit the cloud?

E2E schemes have been pretty successful at allowing people to detect problems, but it is still a challenge to recover from the problems. There are also unresolved questions about whether these schemes will be overly complicated from the standpoint of the voters, and how much voters will trust them.

Answer 4

I know the question is about the US, but I think this court decision by the constitutional court of Germany on voting computers gets down to the important point:

German court decision on voting computers

In Germany the highest court ruled on the subject of voting computers that black box voting is illegal:

Der Grundsatz der Öffentlichkeit der Wahl, der sich aus den verfassungsrechtlichen Grundentscheidungen für Demokratie, Republik und Rechtsstaat ergibt, gebietet, dass alle wesentlichen Schritte der Wahl öffentlich überprüfbar sind, soweit nicht andere verfassungsrechtliche Belange eine Ausnahme rechtfertigen

Roughly translated:

The principal of elections, which is based on the constitutional decision for democracy, republic and a constitutional state, requires that all important steps of the election process are verifiable by the public, unless other parts of the constitution require an exception.

http://www.bundesverfassungsgericht.de/pressemitteilungen/bvg09-019.html

In the classical paper based election he or she can watch the complete voting process at one location:

• the vote collection box is empty before the vote
• every person only gets one voting sheet (they are ticked off in a list)
• no other persons joins them in the voting booth
• the counting process can be witnessed (a computer counting electronic votes cannot be verified according to the verdict).

There are some more issues that one person alone cannot check easily (other voting locations, the list of voters, etc.). Assuming that most party members have an interest in their own party getting lots of votes, fraud gets really difficult.

Yes, special voting arrangements such as mail vote and supporting people assisting disassembled people violate those rules. But that is accepted on the grounds that only a relatively small number of people require those arrangements and they have very valid reasons for it.

Internet

So what does this mean for Internet based voting?

For large scale voting, we again need a way for an average person to check the items mentioned above.

The issue of not being able to verify electronic votes applies as well. If I vote for party A, all I can check is that there is at least one vote for party A. All the other votes for party A might have been counted for party B instead.

The following approach is often suggested: Every voter gets a random id. A list of those IDs and the votes is published after the election. How to verify that there are no additional votes? Someone, who wants to buy votes, can ask for the id before the list is published to verify that the seller voted correctly.

Another issues is authentication and anonymity of votes. Using the next generation ID cards and two different authorities (one to check permission to vote and one to count votes) this can be archived. But an average person is not able to verify that this is done correctly.

The simple issue of mail voting applies, too: It cannot be verified that people are unwatched while they cast their vote. So they might be forced to vote in a specific way (by force or money).

Answer 5

It's not possible, because a secure voting system requires that you can't show anyone else how you voted, even if you want to (so that you can't sell your vote or be otherwise coerced), so the voter's location has to be secured, at which point it's pointless to operate it over the Internet. Yes, postal votes violate this rule and should not be permitted.

Answer 6

Securing Internet voting is very challenging. There is a good description of the challenges in the 2004 report, A Security Analysis of the Secure Electronic Registration and Voting Experiment (SERVE). Some key challenges include:

• Auditability. How do we prove that the votes were counted accurately, and that they weren't tampered with maliciously?

• Client-side malware. Having voters vote from their own computers introduces significant challenges. Those computers are outside the control of election officials and may be infected with malware (including, possibly, malware deliberately crafted to tamper with the voter's vote before it is transmitted to the server). How do we protect an election against targeted client-side malware?

• Server-side security. When votes are collected on a central server, securing that server becomes critical. It is a challenge to ensure that this server is impenetrable and that all operations are conducted securely -- especially given the limited budget available for elections. Given that even Google, RSA, banks, many other other major companies, and even our military have had their servers and website hacked, defending against this will be a challenge.

• Vote-buying/selling/coercion. Defending against electronic remote vote-buying is not trivial. There is some debate about how much protection against vote-buying and coercion is needed, but if a system needs to defend against these threats, that will pose additional challenges.

Recent research advances (e.g., on end-to-end cryptographic voting systems) may provide a path to solve these problems -- though more testing of their usability is needed. Personally, I believe it is probably possible to mitigate the risks enough to use Internet voting on a limited scale, but it will be very challenging. At present, adopting Internet voting on a broad scale would be too dangerous.