INNOVATE

Anonymous Elections

Mix-Nets and Homomorphic Tallying

There is probably one thing that all voters have in common: we do not want anyone to know what or whom we voted for without our consent. In traditional paper-based elections we can use a voting booth to choose our preferred voting option without anyone observing us and, once we cast our vote, we can easily see that the ballot we leave in the ballot box no longer has any relationship to us. Thus, when the ballot box is opened, it is not possible to know who cast each of the ballots. In online voting systems, there are different mechanisms that can help us achieve these same goals.

Voter privacy is one of the security requirements that an online voting system should satisfy. The content of the cast votes, or the voting options selected by each voter, must be confidential during the entire voting phase and it should never be possible to link a vote to the voter who cast it. The former is ensured by end-to-end encryption: votes are encrypted on a voter’s device and they are not decrypted until the end of the election, using a digital key held only by the Electoral Authority during the entire voting process. For the latter, there are different approaches which can be implemented in order to provide anonymity. In this post we are going to focus on mix-nets and homomorphic tallying.

Votes are stored in the digital ballot box in the same order they arrive at the server. If they are directly decrypted once the voting phase is over and we know in which order voters have voted, it is possible to infer which voter corresponds with the first decrypted vote, the second one and so on. For this reason, it is important to break any correlation between the votes stored in the ballot box and the votes that are going to be decrypted. To do this, we can use a mix-net.

A mix-net is defined as a network composed of mixing nodes, each of which performs in turns the same operation: a shuffling. This operation tries to emulate real elections when ballot boxes are shaken and shuffled in order to break the order of how the votes were cast. In a mixing protocol, this “shaking” is done by applying a permutation and a cryptographic transformation to the encrypted votes, which makes the output of the process look completely unique from the input. Thanks to this, votes cannot be linked to the voters who cast them, and they can be decrypted without breaking anonymity.

Since the input and the output of the mix-net +do not have any correlation, it is important to provide a mechanism to verify that the mix-net has not modified, added or deleted any vote during the process. This is done by generating zero-knowledge proofs, which can be verified by any third party. If the online voting system also implements verifiable decryption, it has full universal verifiability

This anonymization procedure differs from mix-nets in that it consists of aggregating the encrypted votes once the election has finished and decrypting only the result of the aggregation. This aggregation is possible due to the homomorphic properties of the encryption scheme used, which allows operations to be carried out on the contents of the encrypted votes, without needing to decrypt them.

Homomorphic tallying systems need a concrete encoding of the voting options to make the aggregation feasible. Imagine a referendum, in which there is a question with only two possible answers, yes or no. If a voter votes yes to the question, the answer is encoded as a 1. On the contrary, if they vote no, the answer is encoded as a 0. At the end of the voting phase, all the answers are summed up and the result is calculated directly from the number of times the answer yes has been selected.

Since the operation of aggregating the encrypted votes does not need any secret information in order to be performed, it is publicly verifiable, i.e., it can be repeated from the votes stored in the ballot box.

Online voting systems which implement this anonymization procedure together with a verifiable decryption step, provide universal verifiability.

This article was written by Núria Costa, Cryptography Researcher at Scytl.