0
$\begingroup$

Given n voters and p candidates, how can we design a trustless voting algorithm that satisfies the following properties. Each voter can only vote for exactly one candidate.

The algorithm needs to:

  • Keep all voters' vote private, i.e. only known to the voter itself
  • Keep the number of votes each candidate receive private. No one should know exactly how many votes each candidate get.
  • Does not rely on a trusted 3rd party. It relies only on the voters themselves.

The algorithm should be able to answer this question publicly:

  • For any two given candidates A and B, did A get more/same/less votes than B?

Using this primitive we should be able to find who got the most votes.

--

I did some research and it seems like partially homomorphic encoding like the Paillier system is not able to do this. Would this require fully homomorphic encoding? Any pointers will be appreciated, thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

This is a challenging problem with few "good" solutions. However, the problem more abstractly is known as private aggregation (in this case, you want to aggregate votes). You might be able to find more research by searching through the private aggregation and measurement literature.

That said, most solutions require "splitting trust" between two or more entities, settling for "noisy" aggregates (e.g., via differential privacy), or assuming a trusted 3rd party. See this survey for some private measurement/aggregation techniques. Unfortunately, it appears like you want to avoid making any of these trust assumptions, which might make a solution to the problem impossible (see my note at the end).

However, I will outline some approaches to the problem (which do assume some kind of trust assumption), to give you a better overview of the problem space. IMO, Non-Interactive Anonymous Shuffling is probably the best solution to your problem in terms of trust requirements, however, it still requires a one-time "trusted setup" phase.

Using additively-homomorphic encryption

Any additively-homomorphic encryption scheme would be an option if you assume distributed decryption capability (or a trusted 3rd party decryption authority). However, this would require a trusted 3rd party or a setup procedure to generate the public encryption key and distribute the decryption key with two or more parties. Note that these "decryption parties", who collectively have shares of the secret key, can be a subset of the clients, or the p candidates for example. However, this solution, by default, would only work if the clients are honest and contribute valid votes (don't send inflated or garbage ciphertexts). See the AdScale paper (and references therein) for some techniques on how to ensure that the votes cast by clients are "well formed" via zero-knowledge proofs.

Moreover, note that fully-homomorphic encryption (FHE) does not resolve the problem of needing a distributed decryption procedure (or decryption authority) since there is still a "secret key" that must be used to recover the final aggregate. This means that, even with FHE, we would still require a trusted 3rd party decryption authority or several non-colluding parties instantiating this decryption functionality.

Noisy techniques

An alternative option, that has no secret keys and therefore does not require a decryption authority, is to rely on differential privacy or randomized response, which introduces noise into the final aggregated votes. For example, RAPPOR is a protocol developed by people at Google for collecting statistics (e.g., most visited websites in chrome) in a privacy-preserving manner.

Noisy approaches may not be a good solution for the voting problem because it would not resolve "close ties" between any two candidates (based on your question, it appears you want to detect ties or determine a winner in a case where votes are close). In other words, these solutions are tailored to gathering statistics (e.g., frequently visited websites), where some noise does not destroy the "signal". In the case of voting, having an exact measurement is often important and therefore these solutions are typically not employed in the voting literature.

A solution with a one-time trusted setup

To my knowledge, the only work that comes close to achieving all the requirements you outline is a recent protocol called Non-Interactive Anonymous Shuffling (NIAS) (see also followup work). In NIAS, a trusted 3rd party generates n secret keys $\mathsf{sk}_1, \dots, \mathsf{sk}_n$ and a public routing key $\mathsf{rk}$. Secret key $\mathsf{sk}_i$ is given to the $i$-th client. The routing key $\mathsf{rk}$ is given to some (possibly untrusted) routing server (you can also think of this server as a bulletin board or blockchain). The $i$-th client encrypts their vote using secret key $\mathsf{sk}_i$ and sends the resulting ciphertext to the router. With all n ciphertexts (one from each client) the router (or if these votes are posted on the blockchain, any verifying entity) can use the routing key $\mathsf{rk}$ to output the n votes in some randomly-permuted order (the permutation is baked into the routing key $\mathsf{rk}$), which would hide which client voted for which candidate. NIAS is the best one can hope to achieve in terms of trust assumptions (only a one-time trusted setup). However, note that NIAS requires each client to contribute a ciphertext---a malicious client can disrupt the whole protocol by simply going offline or sending a garbage ciphertext. This is known as a "dropout" and, unfortunately, there are no good solutions to prevent this problem (see Section 8 of NIAR for some ideas on how to mitigate this issue), which can prevent practical deployments in the real world. Additionally, NIAS is constructed from a very heavy cryptographic primitive known as indistinguishability obfuscation, which makes the protocol only of theoretical interest.

A note on why a "trustless" solution is impossible

To briefly illustrate why a solution to the voting problem that does not make a trust assumption is impossible, consider the following proof sketch. Suppose that there is no trusted third party and that no subset of clients trust each other. Then, each client's (encoded) vote is generated in a way that (1) is computed independently of all other (encoded) votes because no trusted setup or coordination is possible, (2) is computationally or statistically hidden because we require privacy, and (3) with all n (encoded) votes one can recover the true (error-free) vote for candidate $1 \le i \le $ p because we require correctness of the scheme. Observe that we can only choose two out of three properties!

  • If you choose (1) and (2), then you need to add noise; otherwise the encoding would directly reveal the raw vote because of the independence of the encoding (1) that prevents any "correlated" randomization/encoding. However, adding (independent) noise violates (3) because it would violate the correctness of the scheme.

  • If you choose (2) and (3), then you need to makes the individual contributions "cancel out" (i.e., introduce "correlated" noise), which requires the encoded votes to depend on one another in some way (e.g., the encodings need to have correlated randomness that cancels out), which violates (1) since now each encoding has to be generated in a way that depends on encodings generated by other clients and requires a trusted setup (see e.g., NIAS).

  • If you choose (1) and (3), then the vote is not hidden, which violates (2), because no noise can be added by correctness of (3) and the encoding was generated independently of all other encodings due to (1).

Unfortunately, I am not aware of any formalization of the above proof sketch (I believe it's "folklore" at this point). Would be happy to edit my answer if someone has come across a formal impossibility result that elaborates on the above.

$\endgroup$
6
  • $\begingroup$ Hi @Sacha Servan-Schreiber, thanks a lot for the thorough and comprehensive explanation!!! I have a couple of following up questions. For the additively-homomorphic encryption approach and the NIAS approach, can they keep the final votes for each candidate private and still be able to compare the votes? It reads like NIAS will decrypt the votes. Additively-homomorphic encryption cannot compare without decryption. Do you think that FHE would solve this problem? Since we don't need to know the exact votes, just need to compare, maybe we don't need to decrypt using FHE? $\endgroup$ Jun 7 at 23:54
  • $\begingroup$ For "a setup procedure to generate the public encryption key and distribute the decryption key with two or more parties", I think that is totally acceptable for me. I have found this paper eprint.iacr.org/2019/1136.pdf . Adding ZKP to prevent the participants from deviating from the protocol also sounds good to me. $\endgroup$ Jun 8 at 0:00
  • $\begingroup$ I might have misled the question by saying "trustless". I mostly refer to the scenario of blockchain but I think it is totally fine for the parties to coordinate a set up (without relying on a 3rd party) and use zkp to ensure that everyone are honest. I think it is also ok if a participant's info stays private as long as not everyone else are colluding. (a different threshold would also be acceptable if needed) $\endgroup$ Jun 8 at 0:01
  • $\begingroup$ In the FHE case, who decrypts? You can do comparisons, etc, but at the end of the day you will have a ciphertext that contains the tally. To get the actual (plaintext) tally you will need to decrypt (e.g., the clients would need to do a multi-party computation to recover the plaintext). If you're fine with having parties decrypt, then most threshold-decryption solutions should be fit this use case. However, I strongly recommend looking into the e-voting literature before implementing/designing your own protocol. There is a long history of attacks on voting protocols out there! $\endgroup$ Jun 8 at 12:02
  • $\begingroup$ Also, be sure to take a look at the related questions/posts. There is a rich discussion of similar problems/protocols crypto stackexchange. $\endgroup$ Jun 8 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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