Possibly stupid cryptography question

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

D-503
Posts: 78
Joined: Sun Apr 15, 2012 11:35 pm UTC

Possibly stupid cryptography question

Postby D-503 » Sun Sep 30, 2012 7:16 am UTC

Is it possible to build a program where every account with access the program has the ability to modify part of the program's state exactly once, anonymously, while everyone has perfect knowledge about the program and it's state?

Here's why I ask:
I'm thinking about how I could run a database that is completely open for anyone to query, that stores votes on various 'issues', without revealing which 'issues' individual users voted on. If information that identifies the user is not stored, there is no way to prevent ballot box stuffing. But if it is stored, it may be possible to use knowledge of the system simulate a vote from an user to see whether they voted on an issue by checking whether the simulated vote succeeds.

It seems impossible, but in light of public key encryption, zero knowledge proofs, homomorphic encryption, etc. I have zero faith in my intuition about this kind of thing.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Possibly stupid cryptography question

Postby snowyowl » Sun Sep 30, 2012 12:38 pm UTC

Why do you want it to be open for anyone to read?

I mean, you're already placing restrictions on who can write to it and what they can write. It's probably easier to put a proper interface in than it is to give everyone in the world read-only access. What's the reasoning behind this decision?
The preceding comment is an automated response.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Possibly stupid cryptography question

Postby snowyowl » Sun Sep 30, 2012 12:51 pm UTC

Anyway, let me suggest a way to do this and see if I understand your constraints right.

Everyone who has an account gets e-mailed a randomly generated password. (You get a new password for each issue that is proposed.) The server stores a hash of each password it creates, but it does not identify who owns which password. Anyone with access to the server gets to see this list of hashes.

Each hash also has a flag associated with it. At the start, this flag is set to "Not voted". Whenever a user wishes to vote on an issue, they send their password to the server. The server hashes their password and checks to see if the resulting hash is in its list. If so, the user can change the flag on their hash to "Voted yes", "Voted no", "Not voted" (if they're abstaining), or whatever the other options are. They can change their vote if they've already voted once - though if you don't want this to happen, it's simple enough to prevent them from doing so.

Any attacker who manages to get your database will have a list of hashes and will know how many people voted for what, but will not be able to recover the original passwords and will not know how to add new votes. However, if they have someone's password then they can find out what their vote was.

If you want to salt the passwords before hashing them (a good idea), the salts should be stored with the user's name and not with the password hash.
The preceding comment is an automated response.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Possibly stupid cryptography question

Postby mr-mitch » Sun Sep 30, 2012 1:02 pm UTC

One of the issues you'll face is a timing attack.

If you update the database after each person votes, then by tracking who votes and the result of the vote, you can determine the vote. The easy way around this, but costly in memory, is to calculate the result only after all the votes have been received (store user -> encrypted vote).

Other than that, you can sample the even numbers uniformly for a yes vote, and odd numbers for an odd vote, from a very large sample space, and use normal public key encryption methods (that hide parity) and will remain secure even if they can view all pairs. You might also have to hash the user in the pair.
Last edited by mr-mitch on Sun Sep 30, 2012 1:05 pm UTC, edited 1 time in total.

D-503
Posts: 78
Joined: Sun Apr 15, 2012 11:35 pm UTC

Re: Possibly stupid cryptography question

Postby D-503 » Sun Sep 30, 2012 5:31 pm UTC

snowyowl wrote:Why do you want it to be open for anyone to read?

I mean, you're already placing restrictions on who can write to it and what they can write. It's probably easier to put a proper interface in than it is to give everyone in the world read-only access. What's the reasoning behind this decision?


I want the system to be as open as possible, so it's completely transparent how it operates, and so it's easy to duplicate and run a new instances of in a distributed system.

snowyowl wrote:Anyway, let me suggest a way to do this and see if I understand your constraints right.

Everyone who has an account gets e-mailed a randomly generated password. (You get a new password for each issue that is proposed.) The server stores a hash of each password it creates, but it does not identify who owns which password. Anyone with access to the server gets to see this list of hashes.

Each hash also has a flag associated with it. At the start, this flag is set to "Not voted". Whenever a user wishes to vote on an issue, they send their password to the server. The server hashes their password and checks to see if the resulting hash is in its list. If so, the user can change the flag on their hash to "Voted yes", "Voted no", "Not voted" (if they're abstaining), or whatever the other options are. They can change their vote if they've already voted once - though if you don't want this to happen, it's simple enough to prevent them from doing so.

Any attacker who manages to get your database will have a list of hashes and will know how many people voted for what, but will not be able to recover the original passwords and will not know how to add new votes. However, if they have someone's password then they can find out what their vote was.

If you want to salt the passwords before hashing them (a good idea), the salts should be stored with the user's name and not with the password hash.


I'm not totally sure I understand my constraints right either :)

Account generation and authentication can be handled by another service.

Vote changing is a desirable feature to have, but not necessary.

One risk with storing hashes is that if someone says "I voted yes on X, Y and Z", that might be enough information to figure out how they voted on all issues.

mr-mitch wrote:One of the issues you'll face is a timing attack.

If you update the database after each person votes, then by tracking who votes and the result of the vote, you can determine the vote. The easy way around this, but costly in memory, is to calculate the result only after all the votes have been received (store user -> encrypted vote).


Good point. I suppose we could give the option for people who are publicly voting to have their vote come in after a random delay time.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Possibly stupid cryptography question

Postby mr-mitch » Mon Oct 01, 2012 8:10 am UTC

I was thinking about this more today.

If your goal is strictly to restrict the ability to determine a user's vote, you can't have such a system. Basically, a successful adversary just outputs the one for which there were the most votes. This is necessarily (in general) correct more than 50% of the time.

You can avoid this issue by changing the definition to 'not being able to tell the difference between a yes vote and a no vote'. This is more intuitive, as well.

If you make this change to the definition of anonymity, and you delay the calculation of the vote as I recommended, then as long as your vote encryption scheme is IND-CCA2, I'm fairly certain your voting scheme is secure.

I wouldn't pair (user, vote) though. I'd instead pair (user, boolean has_voted) and maintain the list of votes, if you don't want to change them (which is generally how votes work).

This also avoids implementing your own cryptographic primitive (since you're relying on something that is already believed to be IND-CCA2).

You need to make sure your spaces are large enough to accommodate your number of ballots * users, though.


I was also thinking of a better way to avoid storing the entire list of encrypted votes. My last thought before googling was to store the last vote, and flip a coin to either add your current vote, and store the next vote, or add the next vote and store the current vote.

It seems better to investigate commitment schemes. Wikipedia references a fairly recent (2009) paper on secure multiparty sum protocols

User avatar
Xanthir
My HERO!!!
Posts: 5334
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Possibly stupid cryptography question

Postby Xanthir » Mon Oct 01, 2012 11:08 pm UTC

D-503 wrote:Vote changing is a desirable feature to have, but not necessary.

You get vote changing for free with snowyowl's system - just vote again with the same password and it'll change your vote. To turn off vote-changing, you have to add an extra operation, such as deleting the password-hash after it's been used once, or just marking it as "used".

One risk with storing hashes is that if someone says "I voted yes on X, Y and Z", that might be enough information to figure out how they voted on all issues.

No, it won't be - you get a fresh password for every issue being voted on. You can prove your own votes, but you can't predict the votes of others using information about their other votes.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

beojan
Posts: 166
Joined: Mon May 23, 2011 12:11 pm UTC
Location: Oxford / London, United Kingdom, Europe

Re: Possibly stupid cryptography question

Postby beojan » Wed Nov 14, 2012 9:56 pm UTC

Why not simply generate random passwords, and store the hash while emailing the password to the user.
To vote, the user enters their password. The system checks if the hash is in its list, and if it is, the user is allowed to vote. After the user picks their vote and submits, the system again checks their hash, and if it is still in the list, adds one vote to the yes or no column for that issue, then removes the has from the list, preventing ballot stuffing.

Since the information of who voted for yes / no is not stored, only the number of votes for each, it is impossible to determine what a given user voted for.

Роберт
Posts: 4285
Joined: Wed May 14, 2008 1:56 am UTC

Re: Possibly stupid cryptography question

Postby Роберт » Fri Nov 16, 2012 5:11 pm UTC

Xanthir wrote:No, it won't be - you get a fresh password for every issue being voted on. You can prove your own votes, but you can't predict the votes of others using information about their other votes.

Couldn't you just salt the hash differently for every issue, allowing the user to only have one password?
The Great Hippo wrote:[T]he way we treat suspected terrorists genuinely terrifies me.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: Possibly stupid cryptography question

Postby dudiobugtron » Fri Nov 16, 2012 7:17 pm UTC

W.r.t usability: if you're going to email each person a password, it would be easier for them if you just emailed them a unique link to their voting page. The link could contain the password.
Image


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests