In previous posts we have discussed the idea of degree of privacy and its application to weighted voting. In those posts we were concerned about what can be revealed about voter’s choices given an election result. We saw an attack method where privacy was outright broken, as well as a more general way to compute probabilities over choices. Both these methods used techniques from polyhedral geometry as implemented in programs developed by researchers in that area. Having covered this ground, here we suggest a simple modification to incorporate weighted to a standard mixnet-based secure voting scheme we have discussed before. To be clear, this scheme addresses ballot privacy specifically, and does not handle information leaks of the type discussed before.

The original scheme is described at a high level here. You can also find additional technical information at nMix github page and its guide, which implements the protocol.

The main steps of the protocol are

  1. Key generation
  2. Voting
  3. Mixing
  4. Decrypting
  5. Tally and verification

Our proposal for adding support for weighted voting is simple, modifications need to be made only at the voting step. During this step, users cast votes through the voting booth, which is in charge of encoding and encrypting their choices. The voting booth then sends this encrypted content to the ballotbox, where they are stored prior to mixing, decrypting and then tallying. We would like to add some mechanism by which the vote tally reflects the weights of their corresponding users. A naive first idea would be to encode and then multiply vote values such that when the plaintexts are added together they automatically reflect weights. Unfortunately, this is not a good idea, even if it sounds like it’s a good fit for the homomorphic property of ElGamal encryption.

The first problem is that weighted votes have to be validated such that they fit the census data that specifies who’s vote has which weight. If the weights are part of the ciphertext, you cannot directly verify they are correct, and instead need to resort to zero knowledge proofs which make the scheme more complicated.

Second, there are ballot flexibility problems. For some electoral systems, for example those using preferential ballots, there is no way to reflect the user’s greater weight in the vote value. Note that this would also be a problem if attempting to carry out the entire tally in ciphertext space, as is the case for systems based on homomorphic encryption (see Adida 2009).

Finally, and this is the show stopper, the vote weights would appear when decrypting into plaintexts, which would compromise privacy. This is a severe version of the problem discussed in the previous posts: the ballots are linkable to users with the corresponding weight, irrespective of the result.

There is a simple solution, instead of multiplying values in the votes, one can multiply the entire ballots themselves. During the voting phase, encrypted ballots are received at the ballotbox. But instead of just storing the received ballot, the ballotbox (or equivalent component) can duplicate said ballot according to the user’s weight. The resulting set of ballots is then stored as usual. Cast-as-intended and recorded-as-cast verifiability mechanisms are the same, except for the fact that in the latter case, the voter can not only verify the ballot was received correctly, but that it was duplicated the required number of times.

From then on, the mixing, decrypting and tallying phases are identical. Note that, since the votes are anonymized in the mix, the duplication of input ballots has no effect and no consequences for privacy. In particular, a set of duplicate plaintexts from one voter are indistinguishable from a set of individual plaintexts from several voters (modulo our previous posts). During the tally and verification phase, the proofs of shuffle grant counted-as-recorded verifiability and thus the scheme as a whole is still end-to-end verifiable. And because weighting occurs at the ballot level, it works for any electoral method or ballot design.

There is a price to pay for the simplicity, however, and that is the obvious fact that there will be more ballots to process in the mixnet, and the tally will take longer. The extent of this problem depends on the weights, how large they are, and how many users have them. Additionally, if there are non-integer weights it may be necessary to duplicate large integer values to preserve relative power. Or one could reduce duplicity at the expense of reducing tally accuracy. A related tradeoff is discussed in (Adida 2009).

Depending on the magnitudes involved, the weighting via duplicating solution may not be appropriate. In spite of this possibility, it seems that in general the extra computation and tally time is well worth the simplicity of the scheme, both theoretically and in terms of implementation.

Adida 2009 – Electing a University President using Open-Audit Voting: Analysis of real-world use of Helios