Hacker News new | past | comments | ask | show | jobs | submit login
An idea for encrypted, verifiable voting (mpcsh.xyz)
28 points by mpcsh on Nov 11, 2016 | hide | past | web | favorite | 60 comments

There's a bunch of academic research in this area -- how to build an encrypted ballot box that lets you audit that your vote was counted correctly, but prevents anyone else from seeing what your vote was.

However, a fundamental problem with any kind of online voting is that it doesn't prevent your vote from being coerced: https://freedom-to-tinker.com/2006/12/12/erosion-secret-ball... The best known way to do that is to make you walk into a secure area, secretly make your vote on a piece of paper, and put it in a common ballot box. That's the system most countries already have!

E-voting also fails to solve voter suppression problems -- how do you decide who gets a voting ID?

Finally, this kind of thing just isn't needed right now. Is anybody claiming that fraudulent voting was a significant problem in this election, or in any recent US election? Where's the evidence? The current highly decentralized system is already pretty robust against widespread fraud (though slightly less so as electronic voting machines become more popular).

There are far more important problems to solve, like voter suppression and the extreme polarization of politics.

> a fundamental problem with any kind of online voting is that it doesn't prevent your vote from being coerced

That's not exactly true. In many countries the vote is not strictly secret, in the sense that the secrecy of the vote is not enforced: you can show what you are going to put in the ballot to others before casting your vote... and therefore your vote can be coerced or bought as others can verify that you voted as they wanted.

In electronic/online elections, vote coercion is not generally solved BUT the situation is better: normally you can cast your vote as many times as you want and only your last vote will count. Therefore you can vote in presence of your boss, for example, and vote whatever you actually want afterwards.

Ah, I didn't know that! I'm only familiar with the UK and US systems, where you cast a secret ballot and you have no way afterwards to prove how you voted (unless you used mail-in voting).

And that's a good point about being able to change your vote.

There is little evidence of voter fraud because nobody who wants to look for fraud is able to do so (due to many measures put in place to keep voting private, make it easy, and keep it simple), and as Feynman said "absence of evidence is not evidence of absence". Evidence of fraud does exist, but it is difficult to discern whether it is the tip of an iceberg, or just an ice-cube.[1][2] Given the fact that presidential candidates are spending $5-$200+ per vote, it seems like voting fraud would be cost effective, and is likely done at some scale.

[1] https://en.wikipedia.org/wiki/Lyndon_B._Johnson#Contested_19...

[2] http://ktla.com/2016/11/03/possible-voter-fraud-being-invest...

Agreed. The best way to avoid fraud is to ensure it can't be done, and cryptography might be a valuable tool to enfore that.

[1] is from 1948, but [2] is definitely worth looking into. 83 ballots isn't widespread fraud unless it's happening a lot, everywhere. Maybe it is! But it would require a massive and very disciplined conspiracy working at many levels across the country. To me, the burden of proof lies on anyone claiming there is such a conspiracy.

(Trump complained of a vote-rigging conspiracy, of course, but unsurprisingly he shut up once he actually won. He changes his position too often to be credible.)

I am not saying there is a vast voter-fraud conspiracy, and those two links are not meant to be an exhaustive list; I included the Johnson link because it is so famous, and the more recent link to show that the phenomenon seems to persist. If there is widespread voter fraud, I would guess that it exists as a (large) number of relatively small operations, probably emanating from 'get-out-the-vote' campaigns.

I am not a 'team player' for any party, and take all allegations by candidates with a heaping mound of salt.

I didn't mean to imply you had an agenda, sorry! Trump is just the most recent example of someone making vote-rigging claims.

As people have commented elsewhere in this discussion, an online voting system would probably be more vulnerable to fraud, given what we know of the methods and capabilities of the NSA and other organisations.

I agree that there's probably petty fraud going on here and there but I don't see the need for sweeping and risky changes to try to fix it.

A key part of the America system of voting is that we use a "secret" ballot. This important to prevent vote buying and voter intimidation. I like the rest of the proposal.

Right, it's important that no one else would be able to know how you voted.

Perhaps the election commission would also have a paper receipt with a different unique key.

Then both your receipt and the county's receipt would be necessary to locate your vote on the blockchain. Then vote verification could be restricted to the same level of privacy as when voting takes place.

Great comment. Without privacy for verification the election is open for vote buying which I think is the biggest flaw with the proposed system.

I also like the idea of using 2 paper receipts which I think is easy for people to understand.

It's not just vote buying, it's pressuring. If you don't want your employees to unionize, insist they vote for right-to-work laws. You don't have to insist very openly. Just take them out to drinks and mention the election in passing, see who voluntarily shows you their receipt on their phone, and prioritize them for bonuses and promotions.

How does this solve the problem? Previously, if I wanted to verify someone else's vote, I would need their SSN and Voter ID. Now I also need the county's receipt.

If someone would so readily hand over their SSN and Voter ID, what will stop them from handing over the county receipt?

It is held by the county, think of it like the bank holding the second key to your safe deposit box.

Perhaps this could be combined with a zero-knowledge proof? From wikipedia[1] with context:

zero-knowledge protocol is a method by which one party (the voting machine) can prove to another party (the voter) that a given statement is true (their ballot was cast, untampered), without conveying any information apart from the fact that the statement is indeed true. ... the definition implies that the voter will not be able to prove the statement in turn to anyone else (a vote buyer/intimidator), since the voter does not possess the secret information.

[1]: https://en.wikipedia.org/wiki/Zero-knowledge_proof

We know how to make a simple, verifiable, understandable voting system: paper ballot, maybe with an electronic counter.

You can explain in about 30 seconds that the ballots shouldn't be individually identifiable, you have a record that is difficult to tamper with, etc.

How many people have a rigorous understanding of Zero Knowledge proofs? How many people would be able to audit the implementation of such a system?

The benefits that come from electronic voting are small, and we can get them in other ways. Why are people so eager to add so much complexity to such an important civic function?

I live in Colorado, where we recently (a few cycles ago) introduced nearly 100% mail-in voting. In my opinion, we should move the whole country to this system; participation will likely go up, lines for folks who show up on election day are manageable and there is significantly less human error when you don't have to rush it all in one day.

I agree that a blockchain solution may be overly complex, but I think the spirit of what they're after is in the right place.

The problem with mail-in voting is voter influence. When you vote at a polling place, you're guaranteed to be able to vote in a booth on your own, without other people or party advertising to influence you. With mail-in voting there's no way to stop voters' controlling spouse and/or cult leader from influencing their vote or even voting for them.

Yeah, there's a fundamental tension between secrecy and verifiability. The main way I've seen this resolved is immediate verification, eg displaying the vote in a paper receipt kept by the elections board for recounts.

This idea encrypts your ballot with your voter ID + some secret key that you know and creates encrypted data E. It, then, publishes a (E, your ballot) pair. Since only you can decrypt E, others won't know how you vote.

A third party can now pressure you to produce your secrets to verify who you voted for. This is not possible in the current system: as long as the final tally reports at least 1 vote for the person you claim to have voted for, no one can prove your claim wrong.

"$5 off your next purchase if you can produce a receipt for candidate X!"

"You must vote for X if you wish to join my organization."

Some states in US allow you to take a photo of your ballot. This means they can already do the things you mention. But they don't, because it is illegal. It will continue to remain illegal.

If you are very worried about such a scenario, verify that your vote is on the blockchain, then destroy your receipt.

The fact that a receipt exists means that you can be pressured to provide it. If my boss wants me to vote for pro-business-owner anti-union candidates, he's not going to take "Yeah I promise I voted for your guy, but I destroyed my receipt" for an answer.

I don't really buy "it's illegal" as a counterargument. There are a lot of things employers pressure their employees to do that are illegal, but the employees don't really have the ability to do anything about it, because they're taking a risk on the legal system working out for them, and in the meantime they'll probably lose their job and be known as an employee who litigates against their employers. As a wise man once said, if you're a single-digit millionaire, you have no effective access to our legal system.

I can take a photo of my ballot, then mark it as invalid and ask for a new one.

Another great reason to keep this practice illegal.

But doesn't this protocol make it impossible to prove what your secret key is? i.e. there are multiple (user-derivable) keys that look valid, as in deniable encryption?

(And I'm sure everyone's in agreement with the importance of making the ballot secret.)

Right, if you throw out the requirement of secrecy, it's pretty easy to produce a verifiable system. That's the whole problem to begin with.

There's a lot of academic work in this area, some of it going back 20 years. The keyword to look for when searching for papers is "receipt-free" voting.

The most common form of vote fraud is probably ballot stuffing by an insider. With this type of attack every voter who actually voted can verify that there vote was counted properly but the aggregate is still not legitimate. One of the advantages of a paper system is that 10000 ballots is physically large and would be difficult to sneak in to a polling place/ballot box.

With something like this you just need a USB stick, the voter registration database, and the records from the last few elections (and/or death records) to figure out which votes are safe to stuff. If you do make a mistake you will end up with some people who's votes are rejected and no way for an election official to differentiate between that and someone trying to vote twice.

Honestly, a very naïve solution.

I tried formalizing the protocol but there are so many inconsistencies. E.g. the ephemeral key is mentioned briefly... Who generates this key? Who encrypts the message? What's the purpose?

Critique of the few parts that are clear:

1. It mentions a vote blockchain. Why blockchain? There's (apparently) no reason to have a chain of votes here. Even a spreadsheet would be fine. Buzzword alert! I know it's irrelevant but it's a huge red flag that a blockchain is crammed there for no reason at all.

2. "the government can know who individuals voted for" This is a no-no. HUGE no-no. TFA trivializes the impact but I definitely wouldn't vote in a system where anyone but me can verify my vote.

3. Even if you can verify your own vote, that's pretty much it for verifiability. Everything else relies on trusting election officials. What?

And I stopped analyzing there because frankly that's pretty much a broken system.

Yep, the blockchain is uncalled for. I work at an electronic voting company and sometimes we get clients that want to add the blockchain for the system. We patiently explain it to them that yeah, the blockchain has some interesting properties that can be used but that it's not really necessary and it would only be used by a small piece of the voting system...

In regards to 2, for most Americans, it's probably a fairly trivial* matter to infer who they voted for. For a large number, almost their entire lives are digitized in some form or another. I wouldn't be at all surprised if a modern AI could deduce your voting preference just using your public data.

EDIT: *In retrospect, "trivial" is probably vastly understating the difficulty. However, I still don't think this is a "hard" problem.

That's a personal choice and, even then, you really can't be sure. Someone might be a Dem in public and vote Rep in the privacy of the booth. I'm sure this happens a lot more than you think.

There should be a zeroth rule that an voting system intended to be used for government which would be that the average person is able to audit / understand the system. This was in an ACM magazine article.

Indeed. Pencil & paper, with multi-party oversight, and long nights of counting.

Number of ways are developed to circumvent that in countries where police and court are not strong enough:

* bribing of voters to bring their empty ballot to briber;

* fake voters (commission is not police, they are not checking documents as carefully as police do);

* bribing of counters for direct replacement of votes;

* pens with ink which is easy to remove and correct;


The main problem with digitally signing/encrypting a vote is that the public key must be known, which means that someone's vote cannot be anonymous.

I like the idea of a county/precinct/district being the entity who signs the results of a vote. This would protect the anonymity of individual voters, since results are reported on a per county basis today anyways. And if a county is suspected of voter fraud, you could always add their public key to a blacklist..

You assume that a key pair is (publicly?) associated with an individual. I can generate a key pair, sign something (publishing the public part of the key, but not the fact that it was me owning it), then discard the key pair.

How will you associate the public key to me?

What's stopping a single person from generating multiple keys?

> the public key must be known, which means that someone's vote cannot be anonymous.

How does this follow?

In order to verify a signature, you'd need to know the public key of the person who signed the vote. At least that's how I understand it.

The contents of the ballot can still remain anonymous.

You create a plaintext ballot, then you encrypt the ballot with the election authorities' keys, then you sign your encrypted ballot with your own private key (then you send the ballot to the server).

You are signing a ballot that is already encrypted.

Unless I misunderstood you, the government would know who I specifically voted for in your scheme? That would be a huge no-go!

Yes, you misunderstood me. Imagine there are many election authorities, maybe perhaps every candidate has their own election authority. Each election authority creates their own public/private key and the public key of the election is created by joining the public key of all authorities.

Using a mixnet (note: Tor uses mixnets too), you can anonymize and decrypt the ballots while preserving the secrecy of the ballot. Not even the servers know at any point that you voted to Hillary/Trump, but the tally is done. And the whole process is end-to-end verifiable by any external party.

It's the magic of math.

I made this comment on a related thread yesterday[0]:

You don't need crypto. You just need a machine that prints out a human readable receipt that the voter can see but not alter, which then drops into a secure holding area on the machine. At the end of the day, you randomly select say 1% of all the machines and hand count all the ballots inside, making sure the counts and votes match. If they do, then you can be reasonably sure it wasn't tampered with, and if they don't match, then you can hand count all the paper ballots using the old system to verify the computer.


How does this accomplish goals #1 and #2 of TFA?

What do you mean? It meets all six goals:

- Be verifiable - you should be able to see your own vote.

You can view the print out of your vote before it drops into the secure box.

- Be auditable - anyone should be able to tally up the results of the election.

Anyone can count the paper ballots

- Be secure - it must not leak anyone's vote to anyone else.

It's on an unidentified piece of paper

- Be genuine - it should be cryptographically impossible to commit voter fraud.

Well, you have to rely on standard methods of preventing voter fraud, but since there have only been five cases of proven voter fraud in the history of US elections, it's not really a big deal

- Be tamper-proof - it must be impossible to forge results from the inside.

Since the paper is in the machine and verified by a human, you can't really tamper with it any more than you can tamper with paper ballots today, and since those or monitored by adversarial groups, it's basically impossible to tamper with them.

It's a fun idea, but I would like to see you expand the article with a little more consideration around the edges. The core idea isn't really new.

Possible expansion topics:

  - Handling a ballot with multiple separate races
  - Backup system for when the computers have gone down
  - Can it assist in any way with "voter suppression" issues
I don't like the idea that the encryption of the full list would be reversible. If I had contrarian views, I might be afraid to vote if that would put me on a list. Stick to one-way with a guardian to entry.

I can't believe this talk hasn't been posted yet!

Theory and Practice of Cryptography: Verifying Elections with Cryptography


This is probably one of the homomorphic schemes mentioned in TFA.

It's very old (2007-ish?) and the state of the art probably advanced, but it's very interesting and addresses a number of points that are not cared for in TFA (like secret ballots verifiable by the voter but impossible to prove to anyone else).

I think a major problem with this proposal is that all votes could eventually be knowable. Let's be honest, the state of the art encryption we use today will one day be sub-par. New has become antiquated a dozen times over the last 30 years already.

Put enough compute behind that blockchain and eventually you'll crack it, or run Shor's algorithm on the first Quantum Computer and votes from a decade ago are now public.

My contacts in the intelligence community say this is their biggest fear with intercepted communications today. They may be 'secure enough' today, but some of the information moved around would still be devastating if it were decrypted 20 years from now by a bad actor, not all, but some.

The way you should go about this is little different IMHO. Have two blockchains, one that checks if people have voted, and one that records the vote. If you have not voted, then one anonymous vote may be added to the ledger of votes for final tallying. If you have voted, your request is blocked. Maybe you get a random key that gives you the right to add a vote if you pass the first checkpoint, but that key can not be associated with the record that you voted on the other blockchain.

Cool idea. I for one prefer physical voting. It sucks, but I feel safer with it.

You already have open-source end-to-end verifiable secure voting systems.

Full Disclosure: yes I work at nVotes/Agora Voting https://nvotes.com https://github.com/agoravoting/agora-dev-box

This approach uses a mixnet (like Tor) to anonymize the ballot so that the secrecy of the vote is preserved. Only if all the election authorities are compromised, the secrecy of the ballot is at stake, but in any case the election is end to end verifiable (this is a sentence that means that specific requirements are fulfilled).

This particular internet/electronic voting system is already being used by many organizations in Spain and Europe.

PD: Yep, nothing is 100% secure. PD2: Yep, census/user authentication is still an unresolved problem in computer science. In Spain we have a government-issued electronic ids but it's no use because of the difficulty of using them.

As a software engineer who knows very little about government security and voting security, can someone explain why you can't just build it like a regular web app (with very good security measures -- the usual HTTPS, database encryption, proper firewall rules to servers, etc.), and have the user enter their voter ID and social security and submit their vote via a web form?

From reading this article, it would seem that it satisfies the first 4 points, just not the 5th. Is that the main reason to have to use the blockchain, to prevent tampering from the inside?

Because whomever owns the server is now a dictator who can decide the result of the election. When it comes to democracy, "tampering from the inside" is your primary threat model.

Take it for someone who lived in a country where we had 70 years of elections with the same party winning each and every one. Tampering from the inside, when possible and hard to detect, becomes ubiquitous. We only started moving towards semi-fair elections when the election authorities begun to include representatives of all major parties. But in the server example, you would need very complex procedures to replicate that, and make sure there is not a single administrator that can tamper invisibly with the server. It is actually easier to build a tamper evident distributed system than a tamper evident single-node server.

The current level you're playing at is: protect against script kiddies, XSS, and drive by server attacks.

The level that system would play at is: protect against other nations with sophistication at the level of the NSA, protect against other nations that compromise an employee of said system, and to protect against large scale DDOS attacks during a critical time in our democracy

The presidential election would arguably be the biggest target of hackers. With the right hack you're essentially directing hundreds of billions of dollars where you want to if you elect the right candidate.

You need the voting system to be end-to-end verifiable.

The secrecy of the vote must be preserved, meaning that not even the servers can know, at any step of the process, that voter A voted for option X.

Voters must be able to verify that when they choose option A, option A is correctly coded into their ballot.

Voters must be able to verify that their ballot is included in the tally and that their ballot is unmodified.

Anyone must be able to verify the process of mixing/anonymizing, decrypting and tallying the ballots.

So it's not easy at all because the requirements are quite contradictory. But you can do it with mixnets, for example, using them in a similar fashion as Tor. That's the way Scytl or nVotes do it :)

There is an excellent talk about Internet Voting and why this is extremely difficult [1] https://www.youtube.com/watch?v=JY_pHvhE4os

At least in California, this part is impossible to accomplish:

"And so long as the counties can protect their secret keys..."

If want to know why Internet Voting won't work, you should watch Alex J. Halderman's talk at the 31c3 conference about internet voting in Estonia https://www.youtube.com/watch?v=JY_pHvhE4os

Internet voting and/or the ability to verify your vote electronically seems like a great idea until you realize how many voters do not have internet access.

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact