HN Theater @HNTheaterMonth

>The central issue with electronic voting is that it's opaque to observers.

There was this interesting talk years ago. https://www.youtube.com/watch?v=ZDnShu5V99s

Does anyone in the space have a more up to date reference on where things are at ?

https://youtu.be/ZDnShu5V99s?t=22m46s is a good lecture about the cryptography of electronic voting.

Going back to my original comment, widespread faith that the voting process is safe is just as important as whether it actually is. Casting doubt on the process without really solid evidence undermines this faith. By no means do I want to be Pollyannaish about this: it's too important. Which is why I want to see improvements in the voting process.

If voting integrity is something you feel particularly strongly about (I certainly do), I encourage to look into the work that's already out there. The 2000 election spurred a lot of research. Some good starting points are:

Ronald L. Rivest MIT

Auditability and Verifiability of Elections

ACM-IEEE talk March 16, 2016

https://people.csail.mit.edu/rivest/pubs/Riv16x.pdf

---

Ben Adida Google Tech Talks December 19, 2007

Theory and Practice of Cryptography: Verifying Electiosns with Cryptography

https://www.youtube.com/watch?v=ZDnShu5V99s

There's work being done along that line[1]

[1] https://www.youtube.com/watch?v=ZDnShu5V99s (long)

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

Theory and Practice of Cryptography: Verifying Elections with Cryptography

https://www.youtube.com/watch?v=ZDnShu5V99s

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).

There are documented issues with many existing electronic voting systems. E-voting encompasses a lot of different types of system that can involve computers in the chain, and not surprisingly all of them are equal.

There have been a few discussions around voting on HN recently, and that's good. It's an important topic, as trust in the integrity of elections is vital for democracy. There's a lot of existing material out there about verifiable and auditable voting systems, especially in the wake of the 2000 US Presidential elections. I encourage you to take a look at what's out there. It can provide a great foundation for discussion.

Here are some links I've found useful:

Wikipedia page on End-to-End Auditable Voting Systems https://en.wikipedia.org/wiki/End-to-end_auditable_voting_sy...

Ron Rivest slide deck from March 2016. Auditability and Verifiability of Elections https://people.csail.mit.edu/rivest/pubs/Riv16x.pdf

Ben Adida Google Tech Talks December 19, 2007 Theory and Practice of Cryptography: Verifying Electiosns with Cryptography https://www.youtube.com/watch?v=ZDnShu5V99s

I think blockchain might have some application, but I'm unconvinced that computer technology alone is going to solve it. Have a look at this slide deck from Ron Rivest (of RSA fame).

https://people.csail.mit.edu/rivest/pubs/Riv16x.pdf

I think he does a pretty good job of covering the history of modern voting and how technology can be properly applied.

You might find this Google Tech Talk by Ben Adida "Verifying Elections with Cryptography" interesting as well:

https://www.youtube.com/watch?v=ZDnShu5V99s

Here's a link to slides from a talk Ronald Rivest gave back in March 2016 at ACM-IEEE:

"Auditability and Verifiability of Elections"

https://people.csail.mit.edu/rivest/pubs/Riv16x.pdf

It covers a lot of what I'm sure is going to be discussed in this thread, including vote receipts, coercion, verifiability that your vote is counted.

Edit to add:

And heres a good talk by Ben Adida speaking at Google for a "Theory and Practice of Cryptography" TechTalk series entitled "Verifying Elections with Crytography" from 2007. Good stuff there, too.

https://www.youtube.com/watch?v=ZDnShu5V99s

It entirely depends if it's using cryptography or not [1]. For example, using zero knowledge proofs you can be given a receipt that lets you verify your vote was included in the total (without allowing you to prove to an attacker which party you voted for).

Using the computers as glorified counters is a security nightmare. Using them for what they're good at (crypto) would be a security boon, with the main downside being how hard it would be for non-computer-scientists to understand the nature of the security.

1: https://www.youtube.com/watch?v=ZDnShu5V99s

⬐ Lawtonfogle

How could it prove to you that your vote was included in the correct total without also being able to transfer that knowledge to a third party that is right there with you?

Say A and B were the options. Anywhere you take the receipt to verify it has to then display if it counted towards A or towards B. Someone there with you could then see which it confirms.

⬐ Strilanc

Inside the voting booth you pick an identified ballot and are given a zero knowledge proof that it corresponds to the candidate you want. The fact that it's a zero knowledge proof prevents you from using it to convince other people.

The video I linked has a good example where you get 1000 envelopes all claiming to contain "Obama", so you open and verify 999 of them at random and use that as evidence that the one you didn't unseal is good. You can't then use that to convince a third party, because they didn't get to pick the envelope to not open. The video also addresses lots of other security issues; you should watch it.

⬐ Lawtonfogle

My concern would be in proving that the envelope you didn't open is the same one that made it into the final count. If you have no more connection with it after you leave the booth, you can not verify that the letter wasn't tampered with (and also no one can coerce you into showing who you voted for). Any way that lets you verify that the last envelope wasn't tampered with would also let some third party see who you voted for.

Anything the machine electronically presents you with can be modified on a compromised machine, while physical printout that can be used later to verify will either be unable to prove that your vote wasn't switched (though it can prove that your vote was counted) or it will be able to prove you did vote for who you choose, the latter case meaning that a third party can then use this to know who you voted for.

⬐ Strilanc

You're attacking the parts of the analogy that don't apply to the actual cryptography. Best way to see how they get around the issue you're talking about is to watch the video.

⬐ gizmo686

I don't think the non expert voters not understanding the security is that big of a concern. Assuming that the security undisputed amongts experts, the media could convey this to the general population (absent some well supported opposition like climate science faces). At this point, the security points that need to be conveyed to the voters are relatively simple:

1) The receipt you are given may be used to confirm that your vote was correctly counted. Here is a list of websites/programs that you can use to verify your receipt.

2) It is impossible to use your receipt to prove to a third party how you voted.

If we could get major news source (New York Times, CNN, Fox News, etc) to publish their own tools for (1), then I suspect that should give a fair amount of credibility for the general public.

The problem I see is that any technical system of plausible deniability I can think of, would require that a voter is able to forge a receipt that would correctly validate as the incorrect vote. Otherwise, if an attacker wanted to verify that Alice voted Democrat, he could assume she voted Republican and attempt to verify the receipt.

Unfortunately this enables someone to coerce or bribe you into voting for a certain candidate, since the coercer would be able to demand to see your receipt and verify you complied.

Here's a rather long but very interesting tech talk about electronic voting schemes which maintain the secret ballot property: https://www.youtube.com/watch?v=ZDnShu5V99s

⬐ Buetol

Thanks, I looked a bit at the Helios voting system and thought it was a complicated mess but this video explains everything really well!

It's possible via homomorphic encryption, i.e. a way to manipulate cyphertext to make some mathematical operations like sums/products or logical comparisons without revealing the actual secrets. For example, it's possible to compare two encryptions of two numbers and get an encryption of their sum or to know which one is larger without knowing either.

However one drawback of such a voting system would be an inability to get actual vote tallies, only an ordering of the candidates.

There is an older google talk about this delving into more detail.

https://www.youtube.com/watch?v=ZDnShu5V99s

⬐ patcon

Ah thanks for the video!

> counted by hand.

By whom? Overseen by whom? Who oversees the overseers? Not to mention people make mistakes, ballots get dumped, and nobody has any evidence their vote was actually counted.

Here's a long but fascinating tech talk on a real solution:

https://www.youtube.com/watch?v=ZDnShu5V99s

⬐ vacri

In Australia, they're counted by an government official, and overseen by mutually hostile volunteers (scrutineers) supplied from the major parties. It's boring to be a scrutineer, but it's in the major party interests to ensure they are sent.

⬐ colmmacc

I can talk about Ireland, as I've been an election observer there. The way we do it is that ballot boxes are locked and sealed with tamper-evident seals after a polling station has closed. Elections observers; including representatives from the political parties may request to add their own seals. In some particularly contentious districts this is done, but for the most part people are happy with the official seals.

The ballot boxes are then transported by the police force to the nearest "count center". The next morning, the seals are inspected and those ballot boxes are opened. All of the ballot boxes in a constituency are counted together in a secure, but open area. Here's a flickr set with a good number of photos showing how it's done:

https://www.flickr.com/photos/redmum/sets/72157600270850764

the counters are within the fenced area, and the observers - including many people from the political parties, surround the fence. The entire process is easy to see.

One particularly important part is what happens when the boxes are opened. The contents are just dumped out on the table and one by one each vote is turned to face up and towards the observers. The observers then "tally" the votes and mark which candidate (or referendum choice) the voter marked as their first preference.

All parties participate in this tally and it provides the first take on what the result will be. The margin of error on the tally is < 1%. Some tallies with enough tally-takers also count the 2nd and 3rd preferences, but most tallies just project the transfers (we use a transfer based voting system) and that too is generally accurate.

Contentious votes with identifying or ambiguous marks and so on are kept aside and argued over by people like me for an hour or so, but they never make much of a difference.

The end result is a process is very verifiable and auditable, in easy-to-understand human ways; you can literally show up at a count center and count the votes yourself as they come out of the boxes, and make sure that you're not being duped. That's a nice accessibility property too.

⬐ aianus

I appreciate the thorough response and it does sound better than what I had envisaged.

However, there is still no way for me as an individual to know for certain that my vote has been counted. The best I can do is trust in the physical security practices surrounding the ballot box and the honesty of the volunteers involved. And even with a margin of error of < 1%, elections have been decided by fewer votes than that (~15 votes in my riding in Waterloo, ON in a recent election) and recounts are expensive, slow, and contentious.

I encourage you to watch the tech talk when you have a spare hour. We have the technology to create a much better and more transparent system.

⬐ hibikir

Full, transparency across time makes it easy to buy people's votes, or punish people for voting the wrong way. The moment I can check that my vote was counted, and was counted accurately, then my boss/landlord/wife/friend could pressure me into showing them said record.

The fact that I can vote very differently from what is socially acceptable in my social group, and there is no way for them to know is a feature, not a bug.

⬐ aianus

Watch the tech talk. It's possible to prove to yourself that your vote was counted correctly and simultaneously be unable to prove it to others.

⬐ dobbsbob

We don't. I remind every group that tries to automate voting in my province that on election day somebody is going to denial of service the system to use it as an attention seeking platform which will just force a physical vote anyways. Other ideas floated like blockchain decentralized voting are also impossible since none of us can run a trusted personal device to vote with, and plenty of voters have no access or don't want access to phones or any other devices. Worse, every couple of elections there's some sort of scandal where a foreign "politically exposed person" has been caught propping up local candidates or outright fielding their own puppet to seemingly unimportant elections like the parks board so they can reap real estate or resource mining benefits. Imagine what kind of havoc a foreign state could wreak on an electronic voting scheme.

It's much more transparent to just do it by hand count though they tried to sabotage that too http://fullcomment.nationalpost.com/2014/03/11/dont-undermin...

⬐ Maxious

This request came after an election in Australia where during a recount 1375 votes originally tallied were unable to be found http://www.aec.gov.au/media/media-releases/2013/e10-31.htm

An investigation was conducted http://www.aec.gov.au/About_AEC/Publications/Reports_On_Fede...

Rather than a police force transporting a sealed box, a commercial courier company or volunteer with their own car moved what might not have even looked like an official box (perhaps a printing firm's box) which in the end might have been thrown out in the recycling or might have been maliciously removed as the warehouse doors were left open or when a single security guard was on duty overnight.

As Mr Keelty wrote: "There is less concern for the security and integrity of Senate ballots because it is considered that they have less of an impact on the election outcome and in any event are warehoused for six years. This is a cultural problem within the AEC and it needs to be addressed. The fact that it had been thirty years since the last full recount of Senate ballots most likely added to the loss of care in routinely dealing with those ballots during the election."

Why not use a non-bitcoin-based system and completely avoid the 51% attack?

https://www.youtube.com/watch?v=ZDnShu5V99s

I'm not sure if this is state of the art[0] since the talk is 7 years old. This scheme provides proof to the voter, but not enough so he can prove his vote to someone else, avoiding vote selling altogether.

The biggest challenge IMHO is trust in the system.

[0] I'd appreciate criticism or any other progress in the field.

⬐ atmosx

I've seen the video you posted. It's a 2007 video, otherwise I'm sure the author would have mentioned the Bitcoin protocol time and again, because it solves all the problems mentioned + it's decentralized.

Decentralization is a key-aspect here. Votes count equally for all citizens. So every citizen has the opportunity to operate a node for the time (48hours) that the elections will take place, in order to inhibit possible corruption. Given the No of organizations, individuals (e.g. political activists, freedom believes, anarchists, you-name-it, conservatives, liberals, you-name-it) and geeks (who will do it for fun, get an RPi, setup a node for the elections, measure traffic, do a JS/CSS3 front-end to display traffic, real-time results etc.)

The government (formed by all parties) should be able to setup an X number of nodes that would allow the elections to take place anyway, without relying to third parties. But third parties will join to ensure reliability of the network.

A government could block the access of nodes from IP netmasks that are located outside the country's IP blocks, to avoid interference of foreign governments[1].

Now, I'm not 100% about the interface and the interaction which is equally important:

    * Should the voters use PKI? Should an account be linked with their IDs?
    * Should we use a dedicated machine with touch screen and accessibility options in a private chamber?
    * Should we use electronic signatures generated by a special 'card' which every citizen should have one?
    * etc

Estonia has an electronic card[2] for example that could turn handy into situations like these.

There many ways of deployment with pros/cons to be considered on a country by country scenario.

Bitcoin protocol solves the double voting, the possibility to re-count votes, the possibility (which is nowhere today) for citizens to review their votes even years later.

Also we should not underestimate the ability to vote from the comfort of your home, using any device: Imagine how greatly that would improve the % of people participating in the elections for example.

[1] I can't think of what the NSA could come with in this scenario. Would make an interesting discussion.

[2] http://en.wikipedia.org/wiki/Estonian_ID_card

⬐ nebulous1

I don't see the point in using a Bitcoin-esque protocol for a voting system (ie a hashing based blockchain). In fact the existence of a double spent vote could simply invalidate both (or all) votes; the user attempted to cheat, no need to decide which is valid. Otherwise vote acceptance could be based on the votes of the ids themselves rather than by hashing power. You say decentralization is a key aspect, but the distribution of whatever underlying identity the users are voting with still has to be centralized. Bitcoin has opened people up to these sorts of ideas, but that doesn't mean it has to form the basis for everything in the future.

Verifying that the right binary was uploaded is solving the wrong problem. Who cares what the source code claims to do? We care about what it actually does.

Real cryptographic voting systems use verifiable protocols. You don't trust the machine, you force it to follow a protocol that involves proving its actions are correct at every step.

You can verify basically everything except destruction of information (i.e. there's no way to prove with cryptography that a video camera didn't record the voter).

Video with an example of a verifiable voting protocol: http://www.youtube.com/watch?v=ZDnShu5V99s

⬐ rejschaap

You are right that it is not about the software. I think you are wrong thinking that it is about the protocol.

It probably should be about the data. The data should be openly available to everyone.

But there are some requirements to the data that make this tricky (understatement).

With the data in your hand it should be possible to independently verify the results. It should be possible to individually verify that your vote is somehow in there. But it should NOT be possible to link votes to individuals, it should be completely anonymous.

This is not a problem that is likely to be solved by software engineers. If there is a solution, it is in crypto and math more than software.

I do think this is an important problem to solve. It would enable the ultimate democratization. Instead of voting for representatives it would become feasible to directly vote on issues by referendum. If tech is about anything, it's about democratization and cutting out the middle man.

⬐ alexanderRohde

Actually this is a trivial problem to solve (as an engineer who knows a tad bit of cryptography).

⬐ kaoD

Yeah, it was just a tour over the most common flawed arguments in favor of e-vote. I just got tired and stopped somewhere (you can see I got a bit into secure protocols instead of secure programs).

Last time I checked the protocols had several drawbacks (including the "destruction" problem, vulnerable to collusion, etc.) Maybe I missed good protocols? Could you please point me to good papers? (a video is too slow and hard to skim over).

Thanks! I'll check the video ASAP and report back if I have questions!

⬐ Strilanc

I don't know enough to point you at good protocols. The video covers basically all I know, and it's five years old.

I mainly commented to remind people that computer voting systems don't have to be glorified counters. You can actually use their strengths (crypto), instead of only inheriting their weaknesses (malleability).

Youtube users: 'UserGroupsatGoogle' and 'GoogleTechTalks' post some epic content for the more advanced programmer.

Continuous Integration with Hudson: http://www.youtube.com/watch?v=6k0S4O2PnTc

Cryptography Theory and practice: http://www.youtube.com/watch?v=ZDnShu5V99s