Anonymized Votes

Question

Background

Looking to create an anonymous voting system. The system must track whether or not a user voted on an item (public information), but only that user is ever allowed to know whether they voted for or against an item (private information).

Users must login with a unique identifier and a password.

Problem

All data and all software is open to the public for inspection.

Question

How would you prevent people from mining the public database to discover how constituents voted, yet permit constituents to see how they voted?

Idea #1

Encrypt:

Client-side encrypts vote (up/down) using AES (JSAES) against their hashed password.
Client sends vote (for tallying) and AES-encrypted vote to the server.
Server logs the tally (public) and the AES-encrypted vote (for/against) separately.

Decrypt:

Client requests vote record.
Server transfers AES-encrypted vote.
Client decodes AES-encrypted vote using hashed password.

I picture two hashed password instances: one for the AES-encrypted password applied to votes and one for the user's actual password.

For authentication purposes, the client might send a hash of the password repeated twice to use for the actual password hash. I don't know if that would add any information attackers could use to target the AES-encrypted vote.

Constraints

The system has the following constraints:

All data is transferred over a secure protocol (e.g., HTTPS).
People use the system in private (i.e., no peeking at screens).
Web-based system (no information may be permanently stored on user computers).

Mitigating Buy Offs

The system entails voting for policies. Policies are submitted anonymously, subjected to moderation, and require sufficient reputation (like StackExchanges) before going "live." You can change your vote at any time, so even if you were (somehow) awarded a payout, the payer has no guarantee that you don't switch the vote after payment. After the policy is enacted, you can no longer see how you voted.

Related Links

Verified, anonymized votes is on the roadmap for this project https://github.com/zeropki and https://twitter.com/zero_pki — makerofthings7, Sep 02 '18 at 14:33

AJ Henderson · Accepted Answer · 2013-03-18T17:54:49.683

6

The easiest way I can think of would be to assign each user a public and private key. Protect the private key with their password. Upon starting a vote, generate a token and keypair for each token. Issue one token to each user by encrypting the token and private key with their public key such that only they know that it is their token. Store the public key and token as a public record. When the user goes to vote, they can decrypt the private key for their token, cast their vote and sign it with their token's private key.

Since nobody other than the user can determine that the token belongs to them and no user can use the token without holding the private key for that token (which only the valid user has), the system will allow the voter to change their vote at any time while maintaining anonymity.

The crux of the system is the token issuance which must make sure that it only issues a single token per voter and that no record of the private key or the token issued to the user is kept. Alternately, tokens could be generated on user request, but this would enable an attack whereby people could look at the order that tokens were created and associated to users to try and guess which token belongs to which user since the system would have to keep track of which votes a user has requested a token for.

Expressed in terms of records you have:(Encryption described as Encrypt(key,data))

User record: userId, userPubKey, Encrypt(passwordDerivedKey, userPrivKey)

Vote record: eventId

Voting record: eventId, tokenId, tokenPublicKey, Encrypt(tokenPrivKey, voteChoice)

UserTokenAssignment: userId, Encrypt(userPubKey, tokenId), Encrypt(userPubKey, tokenPrivKey)

Thus, when a vote is started, the server knows the userPubKey for each user and can create a token(ballot) for each user. Since the userPrivKey is required for each user to determine which ballot is theirs, anonymity is maintained. Since only the user can sign the ballot, integrity is maintained. The user can change their choice at any time since they know their ballot(token) number.

The one weakness is that if the data is being watched actively then the change is visible in the data and the token can possibly be identified. Putting random time delays in could prevent this problem however as long as the server is privately controlled and only the data and code are public.

edited Mar 18 '13 at 17:54

answered Mar 18 '13 at 17:01

AJ Henderson

41,816
5
63
110

Where does the user's token get stored? – Dave Jarvis Mar 18 '13 at 17:03
@DaveJarvis The association between a user and a token is in the DB protected by their private key. The public record of the token (which isn't tied to the user, but holds the vote information) is stored in a signed format in the DB so that everyone can see the anonymous vote records. – AJ Henderson Mar 18 '13 at 17:04
And the private key is stored in the DB as well? – Dave Jarvis Mar 18 '13 at 17:06
@DaveJarvis The private key for the user is stored in the DB, but protected with the user's password (it could alternately be stored locally, but I was trying to design a purely server side system). The private key for the token itself (along with the token id being assigned to the user) is stored protected by the user's public key (such that only the user can read the private key and know that it is their token). – AJ Henderson Mar 18 '13 at 17:08
@DaveJarvis - to explain another way, think of each token as a ballot. When starting a vote, you make a bunch of numbered ballots. You issue one ballot to each person in random such that nobody knows the number of the ballot. Each ballot is also protected so that only they can write on the ballot. Everyone can see the ballots and verify that only the person that was given the ballot can write on it. Also, since each person knows (in secret) their ballot number, they can alter their ballot at any time. That is effectively what the cryptosystem I described does. – AJ Henderson Mar 18 '13 at 17:16
What I'm wondering is why, if someone had access to the database, they couldn't just apply all the private keys to unlock the public keys. Is it because you still don't know who owns the private key? – Dave Jarvis Mar 18 '13 at 17:17
@DaveJarvis - you can use any number of key derivation methods. The simplest of which would be hash the password, and generate a symmetric key off the hash, but there are also better ways that the same thing can be done. You can take your pick of the many options that are available for key derivation. – AJ Henderson Mar 18 '13 at 17:17
@DaveJarvis - The token private keys are protected by the public keys of each user, thus only the holder of the user private key can use each token. Only the user with their password can unlock their user private key to open the private key for their token. – AJ Henderson Mar 18 '13 at 17:19
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/7972/discussion-between-aj-henderson-and-dave-jarvis) – AJ Henderson Mar 18 '13 at 17:19
@AJ love the idea, how would you link up the token to the user though? Let's imagine a login: a username, or name in this case, and password. The token is assigned to the username, but we can't know what the username is since it has to be anonymous... so why not make a salt of the username and match against that, JoeD & JaneD would match against two distinct different salts generated at initial vote that would then let them retrieve their usernames, which then we'd then match against the password, so 2 salts instead of 1 and a token? – RandomUs1r Mar 18 '13 at 17:40
@RandomUs1r - it's easier than that. The only public information is the vote record which is (tokenId, tokenPublicKey, Encrypt(tokenPrivKey,VoteChoice)). The token assignment is (Encrypt(userPubKey, tokenId), Encrypt(userPubKey, tokenPrivKey), userID). Only the user can tell which token they were assigned and how to sign the vote. Anyone can verify that the vote was properly cast however. – AJ Henderson Mar 18 '13 at 17:44
@RandomUs1r - also, hashing the username would not help any. Hashes are great to prevent figuring out the unknown original, but the list of usernames is known and could be hashed by anyone to identify which hash belongs to which user. – AJ Henderson Mar 18 '13 at 17:59

score 4 · Answer 2 · answered Mar 18 '13 at 18:09

My favorite answer to this type of problem is additive homomorphic encryption.

This is, in simple terms, a cryptographic function E(m), such that E(a) + E(b) = E(a + b).

You could implement a Paillier cryptosystem to tally votes. This allows fully anonymous voting that is verifiable individually (my vote is correct and was counted) and publicly (all votes were counted correctly).

I'm not aware of any ready-baked implementations of this, so you'd be implementing it from scratch, which is complicated to say the least.

score 4 · Answer 3 · edited Mar 18 '13 at 22:12

Electronic voting systems are complex, requiring many characteristics: anonymity (one cannot link votes to voters), verifiability (the fairness of the tally must be verifiable by all participants), prevention of double votes, impossibility to "sell your vote", and others. Cryptographers have found a few ways of realizing voting systems:

Mix networks: a sequence of relay nodes who randomly permute the votes. This gives anonymity out of the box, as long as at least one of the nodes is honest. But then, checking that the vote was not gamed is hard (in particular, verifying that no one voted twice).
Homomorphic encryption: votes are an encrypted value, and the tally is done under the protection of mathematics. The final result is decrypted with a group decryption (decryption key is split among several key holders, who cooperate for this single decryption).

Helios Voting is a well-known implementation of a homomorphic encryption protocol (with ElGamal). See its documentation. The International Association for Cryptologic Research regularly elects its directors using Helios Voting.

Read this introduction.

score 3 · Answer 4 · answered Mar 18 '13 at 16:30

UProve allows you to provision a cryptographic token to each user, and have them anonymously post a response on a website.

The cryptography and the data transfer aren't integrated into web-browsers so in order to make it a web-based system you will need an intermediate to host the UProve token on behalf of the user.

This technology isn't widely adopted, and information is sparse, but if you read the Technology Overview you'll see that is addresses many of your concerns.

Since you seem to enjoy speculating about AES and protocols, this video describes the technical inner workings of UProve. I highly recommend giving it a listen.

Also on that page is a link to the Java and C# SDK

@DaveJarvis see [why javascript crypto is a bad idea](http://rdist.root.org/2010/11/29/final-post-on-javascript-crypto/) — makerofthings7, Mar 18 '13 at 16:37