It is a common belief that quantum computers will pose a security risk to current public key cryptography schemes in use, including remote electronic voting systems. This is mostly because most known online voting protocols make use of cryptosystems that are based on discrete logarithm or factoring problem which are hard for classical computers, but not quantum computers. Although, current quantum computers aren't complex enough to run these kinds of attacks yet, in a few decades they will be. Thus, there is a good reason to worry about the ballot's privacy already now.
Cryptographic voting can be classified into two categories depending on how tallying works. In Homomorphic voting, all encrypted ballots add up without being decrypted individually, and then the sum is decrypted to get the final tally. On the other hand, Shuffle-based voting schemes use mixing networks to shuffle re-encrypted ballots using secret permutation vector before decrypting them. Once encrypted ballots are decrypted, the final tally can be calculated. Currently, the Estonian online voting platform IVXV falls into the second category. There are known homomorphic voting schemes as well which were used in real elections.
A homomorphic encryption scheme is required for homomorphic voting such that Enc(a) ✱ Enc(b) = Enc(a · b). RSA and ElGamal are good examples, where ✱ and · are the usual multiplication. However, they are not quantum resistant. Lattice-based Learning With Errors (LWE) cryptosystem is post-quantum secure and additively homomorphic. But, when you add up LWE ciphertexts, the error term in the sum grows linearly in the number of summands, and the bigger the error, the more likely to get an incorrect answer. Although, theoretically it is possible to rescale the error and construct a Fully Homomorphic Encryption (FHE) scheme, it is not practical at all. Therefore, a widely adopted option is to bound the number of arithmetic operations (Somewhat or Levelled Homomorphic Encryption).
It is also possible to use homomorphic encryption schemes in shuffling-based voting schemes. Observe that Enc(a) + Enc(0) = Enc(a) for additively homomorphic encryption schemes. This can be thought of as re-encryption. As each encrypted ballot will be added exactly once per mixing node, the error term in the sum will not grow much. For ultimate security, 3 mixing nodes are enough to hide all links between input and output ciphertexts (assuming at least one of them is not malicious). Moreover, LWE can be useful in this context.
Now, did we solve the problem? Unfortunately, not. Both solutions, using Levelled HE in homomorphic voting or plain LWE in shuffling-based voting schemes are sufficient to design working protocol, but it will not be secure. In homomorphic voting, anyone can ruin the election by publishing an invalid ballot. Thus, they have to provide some kind of proof that they voted correctly without showing their vote. Also, the election authority can cheat on results. It has to provide another proof that the sum of encrypted ballots decrypts to final tally without leaking secret decryption key. If such proofs exist for some encryption (decryption), it is called verifiable encryption (decryption). On the other hand, in shuffling-based voting schemes, the mixing authority has to prove it knows the secret permutation vector without presenting it explicitly. Invalid ballots can be ignored in the tallying phase. Once all decrypted ballots are published publicly, anyone can easily verify the final tally matches with the cast votes. When the bulletin board is not public, then additional proofs are required to ensure that vote is cast as intended and counted as cast.
Zero-Knowledge Proof of Knowledge (ZKPoK) is a cryptographic protocol that solves the issue when asked to prove specific relations without leaking the secret. Generally, there are two parties involved in ZKPoK: a prover and a verifier. Prover tries to prove he knows a witness w to a secret x so that the pair (x, w) satisfies the specific condition. Verifier sends additional challenges to detect whether the prover knows x or is cheating. A ZKPoK has to satisfy three properties:
- completeness: if the statement is true, the verifier will be convinced of knowledge by the prover;
- soundness: if the statement is false, no prover can convince the verifier;
- zero-knowledge: if the statement is true, no verifier will learn anything more than the claim is true.
Non-Interactive Zero-Knowledge (NIZK) Proofs are protocols when there is no direct interaction between the prover and the verifier. Non-interactivity allows anyone to verify the proof at any time. There are ways to transform ZKPoK to NIZK Proofs.
To make voting schemes secure against adversaries and ensure the correctness of election output, NIZK proofs are essential. In the classical case, for example in ElGamal cryptosystem, practical and sound NIZK proofs of knowledge of shuffle, plaintext (verifiable encryption), and secret key (verifiable decryption) are known to allow us to build secure and verifiable voting protocols. However, this is not the case for the LWE cryptosystem. Even more, it is not known for FHE. Therefore, designing a post-quantum voting scheme is a tough challenge.
There is a trade-off between the practicality of a voting scheme and its verifiability in the post-quantum domain. However, there are several proposals in academic literature. The so-called EVOLVE (Electronic VOting from Lattices with VErification) is the first practical homomorphic voting proposal by IBM researchers [1]. Although, the protocol is proven to be post-quantum secure, votes aren't encrypted directly using the post-quantum secure encryption algorithm. Instead, a secret-sharing method is used to distribute the vote among several tallying authorities together with AES encrypted random values per each share. A randomness and the vote share are committed using lattice-based post-quantum secure commitment scheme. Each voter also provides proofs of the knowledge of each random value. In this voting protocol, a digital ballot consists of commitments to vote shares, encrypted randomnesses and zero-knowledge proofs. In their turn, authorities get cast ballots and decrypt encryption of random values. There is another assumption in the protocol that the authorities are independent of each other and do not leak random values between themselves. This is an important assumption, because the authorities also learn respective vote shares. At least one of them has to be a trustworthy authority to keep the votes private. Commitments and randomness are summed up by individual authorities and published together with proof of the validity of random values. The final tally can be calculated by anyone easily, again by summing up the results of authorities. This protocol limits the number of ballots to be summed in a single run by authorities ensuring error term will not grow much and change the outcome of the election. Therefore, authorities perform the summation in batches. The authors of this protocol measured its performance on a specific parameter set (Yes/No voting, 4 authorities, 11000 voters) and proved it to be practical (took less than 0.2 seconds per voter on a consumer-grade laptop). The main drawback is that in the single event of a malicious act by authority, the election has to stop and start over again. Besides, there is no proof of correct summation.
Norwegian researchers published another practical (659 candidates, 500 000 voters, 4:52 seconds overall on a powerful server) homomorphic post-quantum voting protocol designed for the Norwegian elections [2]. Their work is based on Brakerski-Gentry-Vaikuntanathan (BGV) Somewhat HE cryptosystem evaluating circuits of depth up to 50. Although, they haven't used any ZKPoK in the construction, authors claim that their scheme is provably verifiable using side-channel measurements. Yet another claim [3] came this year in which ZKPoK was avoided as well. Unlike previous examples, this scheme is based on mixing networks over the LWE cryptosystem and is claimed to achieve verifiability using audit trip-wires (online external auditors during mixing). Currently, there are two ZK proofs of a shuffle by two independent teams in the literature. While the first proposal [4] uses GSW Levelled HE, the other scheme [5] uses LWE (more precisely, Ring-LWE) cryptosystem. Both works are theoretically sound, however, their performance hasn't been measured yet. There is a good reason to argue that they will not be as practical as the first protocol mentioned above, but will be more efficient than the Norwegian's work.
Apparently, there are several teams around the world working on post-quantum voting protocol, and so is Cybernetica. We expect to get preliminary results on verifiable shuffling-based post-quantum voting protocol soon.
Written by Valeh Farzaliyev
References:
[1] Rafaël del Pino, Vadim Lyubashevsky, Gregory Neven, and Gregor Seiler. 2017. Practical Quantum-Safe Voting from Lattices. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17). Association for Computing Machinery, New York, NY, USA, 1565–1581. DOI: https://doi.org/10.1145/3133956.3134101
[2] Gjøsteen K., Strand M. (2017) A Roadmap to Fully Homomorphic Elections: Stronger Security, Better Verifiability. In: Brenner M. et al. (eds) Financial Cryptography and Data Security. FC 2017. Lecture Notes in Computer Science, vol 10323. Springer, Cham. https://doi.org/10.1007/978-3-319-70278-0_25
[3] Xavier Boyen, Thomas Haines, Johannes Mueller. 2020. A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing. IACR Cryptol. ePrint Arch. 2020: 115
[4] Costa N., Martínez R., Morillo P. (2020) Lattice-Based Proof of a Shuffle. In: Bracciali A., Clark J., Pintore F., Rønne P., Sala M. (eds) Financial Cryptography and Data Security. FC 2019. Lecture Notes in Computer Science, vol 11599. Springer, Cham. https://doi.org/10.1007/978-3-030-43725-1_23
[5] Strand M. (2019) A Verifiable Shuffle for the GSW Cryptosystem. In: Zohar A. et al. (eds) Financial Cryptography and Data Security. FC 2018. Lecture Notes in Computer Science, vol 10958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-58820-8_12