Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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:

share|improve this question
add comment

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
show 8 more comments

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.

share|improve this answer
    
Thank you for the link to Helios Voting. –  Dave Jarvis Mar 18 '13 at 19:32
add comment

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

share|improve this answer
    
@DaveJarvis see why javascript crypto is a bad idea –  makerofthings7 Mar 18 '13 at 16:37
    
... also AES != UProve –  makerofthings7 Mar 18 '13 at 16:38
    
It looks interesting. It's too bad they haven't more documentation on their web site. Thank you. –  Dave Jarvis Mar 18 '13 at 17:00
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.