Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Secure internet voting

Proof-of-Vote: A Simple Cryptosystem for Secure Internet Voting

by David Ernst, www.united.vote

A method to democratically vote online, that provably ensures to the individual voter that their vote was cast and counted correctly, without tampering, while still protecting their vote privacy.

Note: This is designed for our issue-based liquid democracy platform, not traditional elections.

Goals:

  • Allow individuals to vote using their own digital devices.
  • Allow any voter to verify that their vote was entered correctly.
  • Allow any third party to independently tabulate the results of the vote.
  • Don't reveal the contents of anyone's vote.
  • Don't require individuals to manage their own cryptographic keys, or install any new software.
  • Support hundreds of millions of active users.

Requirements:

  • The voter controls an email address that no one else has access to.
  • The voting platform has already determined who is eligible to vote, and has an email address for each.
  • During the voting period, the voter has access to an internet device that can make secure https connections to the voting platform.

Procedure

  1. Voter Registration: A user, identified by an email address example@email.com, is already verified as an eligible voter in their district.

  2. Email authentication: The user can login to the voting platform with a special link sent to their email.

  3. The user views an individual voting item — 2016-e: Should the city approve $10,000,000 in new bonds to fix the potholes on Main St?

  4. Voting: The user decides to vote yea. The user also picks a secret passphrase that allows them to verify their vote isn't tampered with: CorrectHorseBatteryStaple.

  5. Unique hash: Based on the unique characteristics of their vote — their email, the item-id, their position, and their passphrase — a unique vote identifier is calculated using a one-way hashing function (this example uses https://www.browserling.com/tools/scrypt).

scrypt({
  plaintext: "<example@email.com>, 2016-e, yea, CorrectHorseBatteryStaple",
  salt: undefined,
  outputSize: 32,
  cpuDifficulty: 16384,
  memoryDifficulty: 8,
  parallelizationDifficulty: 1,
}) => 1bbed06e1afe7b52c72c13da4fb7b860ca75be682d515d002b4d894c143068b6
  1. Publish vote: An entry is added to a public record of all votes to represent their vote:
yea 1bbed06e1afe7b52c72c13da4fb7b860ca75be682d515d002b4d894c143068b6
  • The platform can automatically give the voter their unique vote id, so they don't have to go through the trouble of manually calculating the hash themselves. But the individual always can (and occassionally ought to) do it themselves, to keep the platform honest.
  1. View results: At the end of the voting period, the entire public record of votes can be viewed to calculate a winner. Example:
# https://united.vote/audit/2016-e.txt

yea 77a14de056bf7ee73629501fd7942c41e59dc857c404b4f6f426a3c2fdbfbab2
yea 609a0a0f6a08067930e5671ff7ac768323b9d4694f4d201622b1db3d5c271df8
yea 1bbed06e1afe7b52c72c13da4fb7b860ca75be682d515d002b4d894c143068b6
nay ee1d08fa4a2419d65077b247a089165f4a83b6cac8c3e651fcbe937e81fd954d
yea fcd651f744bef16442162c166df2e06d439a472820917d976cd5d3e8acbb5ced
nay 039d4af6f0cceebce7b9cd0f28243861cdea8ca86118e8e108a5d7a865759e0f

The results are: 4 votes yea, 2 votes nay.

Review:

Does the procedure meet the stated goals?

Allow individuals to vote using their own digital devices.

Yes, this goal is met.

In addition to their own devices, a voter can also use a device provided to them by others. This could be from a friend, or for public use such as in a library or community center.

Allow any voter to verify that their vote was entered correctly.

Yes, this goal is met, assuming the hashing algorithm is open-source and cryptographically secure, and the voter remembers the 4 unique pieces that make up their vote — their email, the item-id, their position, and their passphrase. They can independently calculate their vote's unique identifier and confirm (CTRL-F) their unique vote is in the list of all votes, with the correct position.

One concern is that this process is too technical for the everyday voter. Even so, the platform is still kept accountable because of the possibility that any voter may independently audit their vote.

Allow any third party to independently tabulate the results of the election.

Yes, this goal is met, since the record of all votes is published.

Don't reveal the author of any votes.

Yes, this goal is met, but this privacy could be lost.

While all votes are published, only the position and the vote's unique identifier, created from a one-way hashing function, are included in the public record. So by default, the individual voter's position is kept private.

This privacy could be compromised if another party learns the input that went into the hashing function: their email, the item-id, their position, and their secret passphrase.

This privacy could be compromised if the voter's device is compromised. A keylogger, screen recorder, or a man-in-middle attack could all reveal a voter's position to a third party at the time the vote was cast.

This privacy could be compromised from a brute-force attack on the hash.

The item-id acts like a simple salt, so that pre-computed hashes can't be re-used across votes, when the voter, position (a simple yea or nay), and secret may all remain the same.

Brute-force attacks can be strengthened against by using longer and unique inputs, in particular by using a passphrase with greater entropy.

Additional strength comes from the expensive hashing function: scrypt. Since this function has adjustable difficulty, the system can limit the number of hashes that can be calculated within a certain timeframe. This significantly raises the cost of a successful brute-force attack.

Although the system may be assumed reasonably secure at the time of the vote, this will not hold in the future. Developments in computing hardware will eventually compromise the privacy of individuals' past votes.

Don't require individuals to manage their own cryptographic keys, or install any new software.

Yes, this goal is met.

No additional software needs to be installed by the end user. Their security is based on protecting their email inbox, similar to requirements for mainstream online banking and other everyday online tasks.

The platform can offer additional security features like Two Factor Authentication, as extra identity checks, but that is outside the scope of this document.

Support hundreds of millions of active users.

Yes, this goal is met.

This cryptosystem offers similar verification and immutability benefits as a blockchain-based system, but can be built upon traditional SQL infrastructure already proven to scale to billions of active users.

Owner

dsernst commented Oct 28, 2016

Comment from @cannoneyed:

The voter-side stuff all checks out but what about the public record? I might have missed it but it seems like the onus is on each voter to verify their own position, not sure how to ensure that the public record is not tampered with

The voter record can be a simple text document the voting platform publishes, e.g:

# https://united.vote/audit/2016-e.txt

yea 77a14de056bf7ee73629501fd7942c41e59dc857c404b4f6f426a3c2fdbfbab2
yea 609a0a0f6a08067930e5671ff7ac768323b9d4694f4d201622b1db3d5c271df8
yea 1bbed06e1afe7b52c72c13da4fb7b860ca75be682d515d002b4d894c143068b6
nay ee1d08fa4a2419d65077b247a089165f4a83b6cac8c3e651fcbe937e81fd954d
yea fcd651f744bef16442162c166df2e06d439a472820917d976cd5d3e8acbb5ced
nay 039d4af6f0cceebce7b9cd0f28243861cdea8ca86118e8e108a5d7a865759e0f

The results are: 4 votes yea, 2 votes nay.

The voter isn't required to verify their own position, but the opportunity is always available to them. The voter can do this audit offline (without alerting the voting platform), which keeps it honest.

The voting record document can be cryptographically signed by the platform, so that it can be redistributed and still deemed authentic.

A hash of the document's content can be published to a blockchain as a trusted timestamp to provably show when the document was last edited.

Owner

dsernst commented Oct 28, 2016

Another reviewer's comment:

The crypto stuff is all over my head, but I appreciate that any third party can count the results themselves and there's ways to keep it accountable. Seems like a big improvement over what we do now even for presidential elections, where I know that I voted but I have no idea if it was counted correctly, and no way to check.

Similar to @cannoneyed my concern is on relying on voters to audit their own votes and ensure that the vote value is still consistent with their given hash.

Aside from the cryptographic signature on the chain. Is there anything in place to automate the auditing process?

Owner

dsernst commented Jul 18, 2017

@15chrjef: Automating the auditing process can be done by 3rd-party software. Sure the platform could offer it, but one design goal of this cryptosystem is that the end-user may not trust the platform.

We could help write some open-source software for the user to run themselves to automate the verification... That sort of solves the issue since the source would be inspectable.

But better long term would probably be multiple 3rd party "verifiers" that users could choose among. Those could be run as web-apps and handle everything automatically. Up to the user... they have the choice of convenience vs security, similar to choices among cryptocurrency wallets.

Owner

dsernst commented Nov 13, 2017

I've added a comment to the intro that this system is designed for our liquid democracy platform use-case (www.united.vote), not real-world elections. Different risk profile. Much more independent security review necessary as we grow.

XertroV commented Feb 20, 2018

This platform is not secure, and users must trust the electoral authority. Reasons are below.

Disclosure: I am the CTO of a company (SecureVote) specialising in secure voting. I am also the architect of our software and the creator of our voting anonymisation algorithm.

(@dsernst PS. We actually provide SecureVote free to organisations and initiatives like yours).

Preface: I'm writing this because secure voting systems are both hard and important. These criticisms are provided because anything good and robust must be resistant to criticism. I think it's important to strive for quality and robustness generally, and especially when it comes to online voting.

Criticisms

Integrity of Ballot Is Not a Goal

Upholding the integrity of ballots run is not a goal of this system. To claim a system provides secure online voting this must be a criterion.

Private Electoral Roll

The electoral roll is not published - the only time users/voters would detect extra votes is if the number of total ballots exceeds the size of the electoral roll. Even in Australia with mandatory voting we only have 95% participation, and 5% manipulation is plenty of play to determine most elections.

All security around the roll can only come from a centralised authority, e.g. untitled.vote. (This only applies to this system; there are trustless voting systems). Users therefore must trust the electoral authority.

No Protection Against Double-Voting

There is no ability to tell if someone has voted twice due to the private electoral roll.

Proving Manipulation Requires Deanonymisation

The only way for a user to prove something was done maliciously to their vote is to reveal their public identity and vote. This proposal therefore does not conserve secret ballot.

Voters cannot prove malicious actions which occur on votes other than theirs.

Third Parties Cannot Audit the Ballot

Third parties must trust that all votes (yea/nay) correspond to the hashed documents. Without users actively checking their ballots a third party auditor has to trust the electoral authority. Even if users do check their ballots they need to deanonymise themselves to prove anything.

If third parties can audit the ballot then they automatically have access to all private details; this means auditing becomes a privileged position opening up the possibility of collusion and other forms of manipulation. Furthermore voters will still need to trust this auditing authority.

Auditors Cannot Detect Double-Voting

Since the electoral roll is private and users' details are private there is no ability for non-privileged third parties to detect double voting.

Auditors Cannot Detect Fraudulent Votes Cast by the Authority

Even a privileged auditor with access to all private data cannot determine if a ballot was cast by a legitimate voter or the electoral authority since there is no user authentication.

Not Censorship Resistant

Users have no guarantee their vote will be accepted as it must go through a central authority. They have no means to prove censorship has occurred.

No Consensus

Users and auditors have no way to tell which votes should be included or excluded except by trusting the electoral authority.

Unauthenticated Users

There is no proof users or voters have any connection to the email address published.

Users Can Lie / Electoral Authority Cannot Prove Innocence

Users can easily lie and claim they voted nay and that it was recorded yea. There is no way to prove or disprove this statement because users are unauthenticated and there is no protection against a MITM from the election authority. This means that even when the electoral authority is 100% honest they can never disprove an allegation of tampering.

Closed Platform

Users have no idea what code is running on the server and no way to validate any claims about this.

Scalability - Comments

Scalability is not a concern for voting for multiple reasons:

  1. Auditing requires all the data anyway
  2. Votes are small and cheap, even when fully signed (96 bytes is plenty for any electoral system used today, including LD)
  3. SecureVote has already shown that 1.5 billion votes in 24hrs anchored to a blockchain is totally achievable and can be audited from a modern MacBook Pro (it'd take 60-90 minutes provided internet speed and bandwidth are not an issue). Link. In this case the votes were anchored to the Bitcoin blockchain. A modern MacBook Pro can handle (at 100% capacity with no overheads) about 14 billion votes per day.

User Managing Cryptographic Keys - Comments

Users don't need to manage keys or install software to get the benefits of trustless cryptosystems - the main exception here is DNS redirection attacks on domains and phishing. Basically: use FIDO authentication. (Now, there are many reasons it's on-the-whole bad for this sort of thing, but it's better than non-cryptographic passwords and requires no set-up from the user - ideally you have users manage keys or use something like SQRL (possibly a modified version) to do authentication. Additionally you can use an in-browser blockchain light client; SecureVote is producing one for our blockchains.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment