Privacy preserving digital voting
A secure election process is an important prerequisite not only for democracy, but also to construct robust and efficient solutions for the industry. The electronic voting is an active field of research. There are many proposals that were already deployed and tested in practice, e.g the DRE system deployed in Brazil  and the internet voting carried out in Estonia . However, it’s not enough to just accept votes remotely, the platform has to be ready to scale on city, state and even country levels. The results must be verifiable, auditable; the voters have to be eligible and their votes stay private and unforgettable.
Many challenges ahead to design strong enough voting solution, but pandemic underscores the needs in such systems.
I would like to share my experience in designing and deploying production ready voting system. The part I introduces general privacy preserving techniques related to voting platforms; the part II provides end-to-end design for Zug, Swiss solution.
Voting System Design
An electronic voting system is a network protocol which results in having a sequential flow to achieve uniform view on the bulletin board. A general approach is to create a new poll and a bulletin board where it is possible to cast the votes, then calculate and publish final results and, most importantly, to verify the correctness of such results.
The protocol itself is managed by a model where at least the following business roles usually exist:
- Voter is a person who holds a digital ID and eligible to vote
- Registrar is an authority who initiates and manages a voting poll, inc. final results sum up
- Voting Gateway, sometimes referred as polling station, is an authority that provides interface for voting. It can be Government web portal or any independent organisation (school, university or even library)
There are 2 global categories of privacy that can be considered. The first one is the voters confidence about anonymity of casted votes, unlinkability between different polls and verifiability of final results. The second one is a voting process itself, where the protocol has to tolerate to colluding authorities, prevent early access to results and ensure ballot secrecy and unforgeability.
Privacy Preserving Techniques
A bulletin board construction is a significant and hard process for any voting protocols. An access to a poll is always regulated by dedicated authority to prevent fraud. Thus the voter has to be eligible to participate and at the same time the system must guarantee that it’s not possible to correlate identity and casted vote. However, during the eligibility check a voter normally reveals a personal information and gets some virtual ticket or ballot to cast the vote.
This section provides some technics that have been proposed to address this challenge.
Trusted Third Party - a really standard and well-known approach is to have dedicated trusted third parties who split the voting responsibility. Security relies on a number of authorities and the protocol assumes that the polling station, commissioning service and registrar are different and isolated parties. The casting vote and eligibility check are managed by different entities
Verifiable Shuffle/Mixing - Another way to implement a universally verifiable election protocol is to use verifiable shuffling technique. The shuffle protocols are constructed entirely from elementary arithmetic operations and guarantee same kind of random, yet verifiable permutation of an input sequence. The voting systems usually intend shuffle protocol within a mixing center and rotate either encrypted votes or ballots.
Multi-party computation (MPC) - perfect ballot secrecy means that no information is revealed about who sent which message, no matter how many parties are corrupt. Significant contributions have been done by Kiayias and Yung  and Groth . Kiayias and Yung introduced the notion of perfect ballot secrecy together with self-tallying and dispute-freeness. Self-tallying means there is no need for authorities to tally the votes. Dispute-freeness says that anybody may verify that indeed the parties do follow the protocol. The protocol is a modification of the Trusted Third Party strategy and assumes authenticated public channel for every participant. The trusted third parties are involved to construct anonymous channel, but not to generate ballots. The protocol is self-contained and excludes role-based model.
Ring Signatures - a ring signature scheme can be viewed as alternative to group signature schemes. In group signatures, we have that any member of a group of n signers is able to generate a signature such that any public verifier can determine if the signature was generated by a group member. They are typically achieved by generating a group secret element and then sharing it out using either a centralized method, for example through the group manager, or by using distributed methods. One of the ring signature benefits is the construction of ad hoc groups and the avoidance of single group manager. Some works apply modified versions of ring signatures as linkable and one-time signatures to solve the double spend problem in the underlying voting protocol by linking two signatures of the same person without revealing the subjacent identity. Using ring signatures, the voting process is significantly simplified. There are no ballots in the scheme, and the voter joins an authenticated channel, proceeds with the eligibility check and then registers his personal public key. The set of keys is published to an immutable data storage alongside with the voting options. Every voter anonymously signs the desirable choice on behalf of the constructed group. The tallying is trivially carried out by simply verifying all received linkable ring signatures, dropping the invalid or linked ones, and tallying the remaining ones according to their signed messages.
A recent result from another research by Rafael, Vadim, Gregory & Gregor proposes the construction of a quantum-resistant scheme based on lattices. It uses ZKP to prove that each vote is well formed and also to allow authorities to recommit to votes, while still possible to prove in zero knowledge that it is consistent with previous commitments.
In the next part, I will provide overview of end-to-end design for experimental digital voting project in Zug, Swiss.
- Diego F. Aranha and Jeroen van de Graaf. The good, the bad, and the ugly: Two decades of e-voting in brazil. IEEE Security & Privacy, 16(6):22–30, 2018.
- Priit Vinkel. Internet voting in estonia. In Peeter Laud, editor, Information Security Technology for Applications, pages 4–12, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
- Aggelos Kiayias and Moti Yung. Self-tallying elections and perfect ballot secrecy. In David Naccache and Pascal Paillier, editors, Public Key Cryptography, pages 141–158, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
- Jens Groth. Efficient maximal privacy in boardroom voting and anonymous broadcast. In Ari Juels, editor, Financial Cryptography, pages 90–104, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
- Rafae ̈l del Pino, Vadim Lyubashevsky, Gregory Neven, and Gregor Seiler. Practical quantum-safe voting from lattices. Cryptology ePrint Archive, Report 2017/1235, 2017. https://eprint.iacr.org/2017/1235.