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:

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

Decrypt:

1. Client requests vote record.
2. Server transfers AES-encrypted vote.
3. 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

Related:

• https://softwareengineering.stackexchange.com/questions/187947/i-need-advice-developing-a-sensitive-data-transfer-storage-encryption-system?rq=1
• http://rdist.root.org/2010/11/29/final-post-on-javascript-crypto/

Answer 1

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.

Record Type	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.

Answer 2

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.

Answer 3

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.

Answer 4

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