Posts Tagged ‘ Secure Multiparty Computation ’

An MPC based privacy-preserving flexible cryptographic voting scheme

There are various reasons for why electronic voting isn’t widely used, and some of their biggest problems 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…

That’s a pretty long list of dangers!


My own idea for a cryptographic voting scheme below attempts to account for all these problems, as well as some more. Originally I posted about this idea on Reddit here.

This voting scheme relies on the usage of a variety of cryptographic primitives, including symmetric cryptography like key derivation functions (KDF, like HKDF) and encryption (such as XChaCha20+Poly1305), public key encryption / asymmetric encryption (ECC / ECIES), Secure Multiparty Computation (MPC, like SCALE-MAMBA), Shamir’s Secure Sharing Scheme (SSSS), Zero-knowledge proofs (ZKP, like ZK-STARKs) and personal smartcards to implement signing and encryption of the votes.


As a fundamental requirement every voter must have their own personal cryptographic asymmetric keypair on a smartcard. This card could for example be integrated in a state issued ID card, like they do in Estonia. As a simple way of improving the security margin for these keys (to avoid risks like insecure key generation), a new keypair is generated on the card when the owner has received it, and they digitally sign a notification to the issuer to replace the old keypair and register the new one. 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.

The MPC participants would include a number of different organizations involved in the voting process which has conflicting interests (to prevent them from willingly collaborating), such as the major parties (as an assurance for them), civil organizations like EFF and ACLU (as an assurance for the people), federal agencies like NSA, FBI and the White House (as a assurance for the government), the department running the election, and more.

Because they all only runs one node each following the MPC protocols, they know nothing more than what they put in and what they are supposed to get as an output from it – and because they DO NOT want to work together (due to conflicting goals) to spy on or alter the result, it’s safe*!

  • For various probabilities of safe. You also have to assume nobody’s able to hack a majority of the participants, or blackmail enough participants, or break the cryptography.

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 input seeds, it combines them with a HKDF to ensure the output is properly random – this means that only one participant needs to be honest and use a true random number, in order for the result to be both unpredictability random and secret from all the participants. This result is the MPC seed.

Then that output is used as the seed for generating secure keys and random numbers, including the main MPC voting system’s main keypair. The MPC participants also provides a list of the registered 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 audit the list of voters in advance, because the list can’t be altered after they all have decided together on which version 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) and encryption to split it’s private key into one part for each MPC participant (more on this below), and provide each MPC participant with the MPC 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 (reaching a defined threshold), which in the case of the vote system would be all all the shares of all the MPC participants (if you don’t have enough shares to reach the threshold, the key can’t be recovered). Setting other tresholds is possible, such as 2 of 3 or 45 of 57 or anything else you need.


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 his own keypair, he CAN NOT decrypt it which means that nobody can prove what he voted for using just the encrypted message (for as long as the MPC remains secure!). To know what a person voted 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 or similar timestamping mechanism such as through Bitcoin, and they are digitally signed by the voting management organization to that prove they too have seen them. This means that you can nearly instantly verify that your vote is going to be included unmodified in the count. Attempts at excluding votes from certain areas or certain users would be obvious and provable as soon as the voting result is published.

Encrypted votes can’t be modified without detection, and once timestamped they can also NOT be modified in a way which would change what it would count towards and yet 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. After the deadline, a final list of encrypted votes is signed and published.

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. The signed vote list is published 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 and decrypted inside the MPC system. 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; alternatively a more recent vote 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 option 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 yours 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 still can’t say which 10 000 (or more) it was that voted for somebody else or prove anybody wrong. (The MPC would then also report the total number of decoy nonces vs real ones).

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 organizations won’t all conspire together against the voters, 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!

Advantages

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

Potential weaknesses

  • 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.

Advertisements
Advertisements
%d bloggers like this: