Can a voting system be secure without it being possible to prove who you voted for?

[Donald Ian Rankin]

Last edited Sat Mar 26, 2016, 09:11 AM - Edit history (1)

A voting system would ideal have the following properties:

Reliability:
1a) It should be impossible* to rig it by discounting genuine votes.
1b) It should be impossible* to rig it by adding fake votes.

Secrecy:
2a) It should be impossible to find out who someone else voted for without their consent
2b) It should be impossible to find out who someone else voted for with their consent - i.e. it should be impossible to prove who you voted for.

Standard paper-and-ballot-box systems, and most electronic voting systems, achieve 2a and 2b, but not 1a or 1b.

It's easy to achieve 1a and 1b without 2a and 2b: just have an open vote, with the list of who voted for whom publically available.

With electronic voting, it's possible to achieve 1a and 2a: have each voter create a password, and when they vote hash** together their identity, password and a salt together with who they voted for; publish a list of hashes for each candidate. Any voter can then check that their hash appears in the correct column, but no-one else can check that without their password.

If you combine that with counting votes cast at each polling station, you can get 1a, 1b and 2a - a wholly secure voting system where it's impossible to find out how someone else voted without their password.

If you hack a voting machine, you can find out how people vote, and break 2a, but - critically, given the major objections raised to electronic voting - you can't break 1a or 1b without being discovered; if you move people's votes around then they can easily find out that you have done so. So, contrary to popular wisdom, this approach to electronic voting is actually much harder to rig undetectably than paper-trail voting, where you can just stuff or lose ballot papers - it's even impossible to rig undetectably if you conduct it on unsecured computers connected to the internet!

But what it doesn't give is 2b - it's still possible to prove that you voted for someone, and hence potentially viable to bribe people into voting.

Can you devise a system which provably gives you both security and deniability - that is, which lets voters check that their vote has been counted correctly, but makes it impossible for them to prove that to anyone else?

*Technically, here I mean "impossible to do this without it being easily detectable". No system can ever be proof against people turning up with bayonets and tampering with it by force; all you can do is ensure that if the system is rigged then you can see it's been rigged.

**Hashing: use clever maths to generate a number h depending on the identity, password, person voted for and "salt" such that given those four facts it is easy to compute h, but given h you can't recover any of the four facts without more computation power than there will be time for before the heat-death of the universe, and you also can't pick a bunch of facts that will given value.

The "salt" is a random number to stop people recovering the person voted for by guessing what the password is and seeing if that gives the right value.

It's relatively easy to do this reliably - see https://en.wikipedia.org/wiki/Hash_function

[Wilms]

1. You did a GREAT job laying out the requirements and challenges.

But using hash functions may also be problematic. (And it takes a lot of faith to believe it's working right.)

https://en.wikipedia.org/wiki/Security_of_cryptographic_hash_functions

Hand Counting and/or use Lever Voting.

[mythology]

2. Not with passwords

People make really really crappy passwords

For example in 2015 the 5 most popular passwords were:

123456
password
12345678
qwerty
12345
123456789

You could do it if we ever effectively replace passwords. But with how many people use insecure passwords, it wouldn't be secure enough. And if you make people choose a real password, they will forget it when they next go to vote.

[Donald Ian Rankin]

3. That's what the salt is for.

As well as getting people to choose their own password, you randomly generate a number, give them that as well, and use both together as the password.

As I envisage it, you'd only choose your password in the voting booth. So if you forgot it, you'd be unable to verify your vote afterwards, but it wouldn't stop it being registered

[MH1]

4. That's a good, well-written problem statement. Do you know -

Is there any public interest working group working on solving this?

[Donald Ian Rankin]

5. I am not aware of one, but I probably wouldn't be even if there was.

For what it's worth, though, I rather doubt it - I think the symbolic power of the ballot box is such that there won't be much appetite for attempting to replace them.

[MH1]

6. I guess I took that as an unwritten assumption.

I agree that a successful solution would not attempt to (fully) replace the ballot box.

Ballot boxes have already been replaced in some places. (Vote by mail, for instance). But people can still walk into the polling place and cast a vote the old fashioned way. I think any solution would have to still allow that, for exactly the reason you state. Although eventually the need may fade away.

[Igel]

7. Democracy--modern civilization, heck any civilization that meets the definition of the word--

relies on trust.

If all you have is ill-will, it's Mad Max time.

No, wait. Even in Mad Max there was a community that had a decent amount of good will for in-group members. Some see omnipotent scheming enemies everywhere, all the time, in conjunction with perceptions of their own superiority. (This was an observation about perceptions of the Jews--most anti-Semites viewed their enemies as somehow superior in most ways, whereas most racists viewed their enemies as inherently inferior. Nowadays most view their enemies as superior in all ways but moral, but still say that their enemies are inferior in every way. It's all very confusing, our enemies being smarter than their intellectual superiors.)


Note that part of the problem in Belgium is that there are two large ethnic groups with mutual distrust, in addition to all the modern views on privacy, etc. We pretend that Switzerlands are the norm, insisting on what is counterfactual. There have been perhaps a handful of such communities (and even there not all is well). Meanwhile, in some areas of the world the norm for centuries was a 30% genocide rate per century. Elsewhere, genocide and slavery, ethnic and linguistic oppression have been the norm. Even my half-brother's grandmother was really quite explicit--"Those Calabrese, you can't trust them, they're all thieves and they're stupid, not really people." She refused to go to an Italian-American seniors club because of the sheer number of Calabrese that were there, and she couldn't stand being around "those people." Such virulence from classic anti-black racists I've seldom encountered. She was Sicilian; from DU's perspective, they weren't merely both Italian, but "white." My students find the idea of ethnic violence in my old school remarkable; the Poles and Italians fought, but they can't believe that non-racial ethnicity could possibly matter, it's only skin color is really important. Their breadth of perspective can be measured in angstroms and they consider themselves mature, wise, worldly.

They also consider this kind of mutual distrust to be a good thing. They're fools. You can fix stupid--people can learn facts, acquire knowledge; we're all born stupid. A lack of intelligence you can work with a bit, but that can't be helped very much and people aren't all that responsible for a large portion of intelligence. What, about 50%, current studies show, is just inherited? You can teach some metacognitive tricks like chunking, work on increasing what people have. But foolishness? The first thing about foolishness is fools suffer from an anosognosia that makes dementia patients look brilliant.

[Donald Ian Rankin]

8. I'm not sure what this has to do with my OP?

If the point is that voting systems should be based on trust, I don't agree - I think a voting system should be set up to make it as hard to rig as possible.

[Yo_Mama]

12. Modern civilization is very much based on ACCOUNTING - a system of reconciling counts.

With multiple layers of proof.

And since the development of agricultural societies with centralized food storage, accounting seems to have been a necessary function.

A hell of a lot of the problems the Chinese are seeing now is because of bad government and business accounting.

[Yo_Mama]

9. Good question, and I doubt it. n/t

[Donald Ian Rankin]

10. Can you prove that?

It looks like the kind of thing that ought to be susceptible to a mathematical proof, but I can't construct one.

[Yo_Mama]

11. Set theory? We want to be able to prove that Set 1 = Set 2

You aren't going to make me pull out my textbooks, are you?

Without a way to evaluate or revaluate the first set (votes cast by voters) we cannot know certainly that the second set (tabulated and reported votes) equals the first set.

Even with mail-in voting or internet voting, one should design the system so that the voter receives a copy of their tabulated vote by mail or email so that checking is possible.

[Yo_Mama]

13. Bert Mendelson, Introduction to Topology

In order for sets to be equal, we must be able to say that Set A is contained in Set B AND that Set B is contained in Set A.

A set is contained within another set if all members of the first set are present in the other set.

Without the ability to examine the members of the first set, it is impossible to say that it is contained in the other set.

Therefore, defining the members of Set A as legal ballots as cast by legal voters, and defining the members of Set B as ballots as tabulated and recorded, it is proven that without a separate recording and retention mechanism for the members of Set A, it is impossible to certaintly state that Set B contains Set A, much less that Set A contains Set B.

"Thank you, don't forget the waitstaff. I'll be playing here all week, let your friends and family know."

This is proof that I am a boring person who does not get many invitations to parties.

[Donald Ian Rankin]

14. That isn't quite the right problem, though.

Because we're not asking for any individual to be able to prove single-handedly that the two sets are equal. We're dealing with multiple people, each with imperfect information.

What we're asking is more like

1) For every element of A, the person who cast that vote can prove that it is in B using only the information they have.
2) Everyone can prove that for every element of B there is exactly one element of A (although they can't deduce which it is).

But I think it's still a bit more complicated than that.


Anyone given complete information can easily test whether the two sets are equal, as you set out. But the hard part of the problem is distributing information so that no one person can deduce things they shouldn't be able to, but collectively they can be confident that everything has worked.