An MPC based privacy-preserving flexible cryptographic voting scheme
Some of the big problems with cryptographic voting schemes are to ensure anonymity for the voters, ensuring that votes can’t be manipulated or otherwise tampered with, that you can be certain your vote has been included and counted correctly, that the full vote count is performed correctly, that the implementation is secure, that votes can’t be selectively excluded, that fake votes won’t be counted, etc…
My suggested voting scheme below attempts to account for all these problems, as well as some more. Originally I posted about this idea on Reddit here; http://www.reddit.com/r/crypto/comments/r003r/are_others_interested_in_cryptographybased_voting/c42lo83
This voting scheme relies on the usage of public key encryption (asymmetric cryptography), Secure Multiparty Computation (MPC), Shamir’s Secure Sharing Scheme (SSSS), Zero-knowledge proofs (ZKP) and personal smartcards to implement signing and encryption of the votes.
Every voter has their a personal keypair, using asymmetric key cryptography, on a smartcard that may be embedded on a smartcard on for example state issued ID cards. As a simple way of improving the security margin (to reduce the risk of the private key having been logged and/or of the key being extracted in transmit through TEMPEST class attacks), a new keypair is generated on the card when the owner has received it and digitally signs a notification to replace the old keypair. The card issuing entity verifies the identity of the voters and thus of the card owners, and tracks which public key is linked to each card.
Secure Multiparty Computation (MPC) can described as a way of letting several entities create a shared “virtual machine” that nobody can manipulate or see the inside of, in order to simulate a secure trusted third party server. Thanks to advanced cryptography, we can use distrust to our advantage since strong implementations of MPC can’t be exploited unless the majority of the participants collude maliciously against the rest. A number of different organizations with conflicting interests participate in the MPC based voting process, such as EFF, ACLU, NSA, FBI, White House, those running the election and more. Because they all run one node each following the MPC protocols, the know nothing other than what they put in and what they are supposed to get as output from it – and because they DO NOT want to work together to spy on or alter the result, it’s safe!
As a part of the initial setup process, they all create a random “seed” each (a large random number) that they provide as input to the MPC. First of all, when the MPC system has the random seeds, it XOR them all together to ensure it’s random (XOR anything with a random string and the output is random – this means that only one participant needs to be honest and use a true random number). Then that output is used as the seed for generating secure keys and random numbers, including the main MPC voting system main keypair. The MPC participants also provide a list of the eligible voters and their respective public keys. All participants must provide IDENTICAL lists, or the MPC algorithm’s logic will detect it and just stop with an error. This means that all MPC participants have an equal chance to verify the list of voters in advance, because the list can’t be altered after they all have decided together which to use. Something like a “vote manifest” is also included to identify the particular vote and declare the rules in use.
The MPC system will then use its main keypair to sign the voter list and the manifest, and then it will use Shamir’s Secure Sharing Scheme (SSSS) to split it’s private key into one part for each MPC participant, and provide each MPC participant with the public key, the signed manifest, the voter list and an individual share of the main keypair’s private key. SSSS is a method of splitting up data so that it only can be recovered if you have enough shares, which in the case of the vote system would be all all the shares of all the MPC participants (setting other tresholds is possible, such as 2 of 3 or 45 of 57 or anything else you need). If you have less shares than the treshold then you aren’t any better off than if you had none if you are trying to restore the data.
Time for voting. The public MPC key is now distributed EVERYWHERE. On every advertisement about the vote, the key is there (maybe in Qr code form). This ensures that everybody knows what it is, and thus we prevent man-in-the-middle (MITM) attacks against voters (which would be somebody swapping out the MPC key to find out what people voted for).
Now, the voter makes his vote. He generate a nonce (unique number used once), makes his vote, signs it with his keypair, and encrypts this with the public MPC key (the signing and encryption is both done on the personal smartcard in one go). This vote is now sent to the voting management organization (maybe this is done on-the-spot if the voter is at a voting booth). Since the vote wasn’t encrypted with the keypair voter, he CAN NOT decrypt it which means that nobody can prove what he voted for using just the encrypted message. To know what a person votes for, you need to physically watch him vote.
To add a level of transparency in the vote submission process, all votes are registered on a blockchain (a series of data blocks all linked to the previous block in the chain using cryptographic hashes, so that you can’t replace or modify a block without all the hashes in the chain after that changing) such as Bitcoin’s or Namecoin’s, and they are digitally signed by the voting management organization to prove they have seen them. This means that you can nearly instantly verify that your vote is going to be included in the count and won’t be excluded. Attempts at excluding votes from certain areas or certain users would be obvious and provable within hours. Encrypted votes can’t be modified without detection, and they can also NOT be modified in a way which would change what it would count towards and remain valid – any modified votes WILL be detected by the MPC system and rejected. Fake votes will also be detected and rejected. To make sure your encrypted vote will be counted, you just need to make sure it is included unmodified. When the time to vote ends, new submissions is no longer accepted or signed by the vote management organization.
For efficiency in the MPC counting and for transparency, the voting management organization gathers all the encrypted votes that was signed and registered in the blockchain, takes the hash of the last block and generates a Zero-knowledge proof of that all votes submitted before that last block with the given hash is included in the vote list. They digitally sign this vote list and publishes it with the Zero-knowledge proof.
Then it is time for the vote counting. The MPC participants then hands the MPC their individual SSSS shares for the master keypair, the signed vote list with the blockchain hash and the Zero-knowledge proof, the manifest and list of voters, the counting rules, and random seeds, and all other data it needs. The MPC keypair is reassembled inside the MPC system using SSSS. It verifies the Zero-knowledge proof of the vote list being complete, decrypts the votes, verifies all votes (checks signatures, syntax and that it follows the rules from the manifest), checks that no voter’s key is used more than once (duplicates are discarded; also, a vote of yours registered later in the blockchain could replace previous ones), and counts them according to the chosen method of vote counting. When it is done it generates the voting statistics as output where each vote is listed together with all vote nonces listed next to it, it specifies which blockchain hash it was given (to show it has processed all votes registered in the blockchain), references the manifest, and the MPC then signs this output. Except for the vote result itself, the statistics could also include things like the number of possible voters (how many there was in the voting list), the number of votes, how many parties there were, how many votes each party got, etc…
So now you search for your nonce in the output and checks that the vote is correct. The nonce CAN NOT be tied to you, it’s just some random number. You can lie that it belongs to somebody else, you can pretend to have another one. The number of votes can be verified. However, done in this way we’re vulnerable to a so called “birthday attack”. The thing is that if there’s been 20 000 votes for political party X and their followers threaten 5 000 people, chances are that more than one voter will claim the same nonce voting for party X is theirs (roughly 22% risk per-voter). So how do we solve this? Simple: Let the voter make both one real vote and several fake votes (“decoy votes”). Then the voter has several false nonces that he can give, including one that says that he voted for party X. Only the voter himself can know which nonce belongs to the real vote! To prevent the adversary that threaten him from figuring out if and how many false votes the voter made, the size of the encrypted voting messages should be static with enough margin for a number of “decoy votes” (if there’s several possible adversaries that could threaten you based on your vote). Now these guys could threaten 30 000 people, but even if there’s just 20 000 voters for their party, they can’t say which 10 000 it was that voted for somebody else or prove anybody wrong.
The best part? We can use ANY type of voting, such as preferential, approval, wheighted, ranked, etc! It’s just a piece of text anyway that allows for arbitary syntax, and you can “encode” ANY kind of vote in it! You can use a simple most-number-of-votes, or score from 1-10, etc…
In the end, you know that your vote has been counted correctly, everybody knows no fake votes have been added, that none has been removed, it’s anonymous, and the only way to force individual voters to vote as you wish is to physically watch them vote.
If you trust that these maybe +10 agencies won’t all conspire together against the voters (including EFF & ACLU?), you can be pretty sure the voting has been anonymous AND secure. The only way to alter the counting or other computational parts on the side of the voting management requires nearly full cooperation between people in ALL participating organizations that have full access to the machines running the Secure Multiparty Computation protocol – and they MUST avoid ALL suspiscion while at it!
If you can distribute personal keypairs securely to the voters, nobody can alter/fake votes outside the Secure Multiparty Computation system.
- A majority of the Secure Multiparty Computation participants have to collude and be in (near) full agreement to break the security of the system. If their interests are conflicting, it just won’t happen.
- The security of the system relies on the cryptographic security + the low risk of collusion among enough MPC participants. If you accept both of these points as strong, this system is strong enough for you.
- It’s anonymous
- You can verify your vote
- You can’t be blackmailed/forced to reveal your vote, because you can fake *any* vote
- The public won’t fully understand it
- The ID smartcards with the personal keypairs must be protected, the new personal keys must be generated securely
- We need to ensure that the MPC and Zero-knowledge proof algorithms really are as secure as we assume they are
I’ve changed the scheme a bit now from the original version. It should be entirely secure against all “plausible” attacks except for hacking all the MPC participants at once or against an attacker that can watch you physically while you make the vote. The latter should not be an issue in most places and can probably not be defended against with any cryptographic scheme, while the first is all about infrastructure security, and also not cryptographic security.
Feedback is welcome. Am I missing anything? Do you have any suggestions for useful additions or modifications? Comment below.