Kristian Gjøsteen, Department of Mathematical Sciences, NTNU
Elections are important.
Not just for our democracies, but also for churches, universities, labour unions and other civic organisations who organise regular elections.
But elections are expensive to run and getting voters to vote is a challenge.
Casting ballots via the internet can be cheaper than putting paper ballots in physical boxes, while likely also increasing participation for some types of elections.
For many types of elections, internet voting is an attractive option.
The question is, how do we secure internet voting?
More concretely, how do we explain to a reasonable voter that which ballot they cast will be kept secret?
And when the loser cries ‘RIGGED’, how do we convince a reasonable voter that all the ballots were counted correctly, that Venezuela or Italian satellites did not tamper with the count?
We discuss secrecy first.
The voter uses a computer to encrypt their ballot before sending it via the internet to an electronic ballot box, where they are stored until the polls close.
The encryption prevents anyone from seeing which ballot the voter cast.
Before we can decrypt the ciphertexts stored in the ballot box, we must break the link between who cast the ciphertext and their decryption.
To do this, the ciphertexts are sent through a sequence of computers that each shuffle and re-encrypt the ciphertexts, one after another.
As long as one of these computers are honest, we are left with a bunch of encrypted ballots and nobody knows which voter cast which encrypted ballot.
Now we can decrypt the shuffled and re-encrypted ballots.
To prevent any single computer from decrypting the ciphertexts in the ballot box, we distribute the decryption key among several computers who must all cooperate to decrypt the ballots.
In other words, the counting process is distributed among many computers in such a way that even if a few of them are controlled by Venezuela or Italian satellites, who cast which ballot remains secret.
Tampering
But what about tampering?
What prevents one of the shuffle computers from just making up some new ciphertexts, instead of re-encrypting and shuffling the given ciphertexts?
Every party is required to give a mathematical proof that they have done their computation correctly.
These proofs are so-called zero knowledge proofs, which means that they do not reveal anything about the computation except that it was done correctly.
In fact, it is possible to publish a transcript of the counting process so that every voter can verify that the cast ballots were counted correctly.
The voters can even verify that their own encrypted ballot was included in the count, that it was not discarded by the ballot box.
It is even possible to provide voters with receipts that they can use to prove that their ballot is missing from the count.
Obviously, nothing prevents losers from crying ‘RIGGED’, but if the count really was tampered with, they should have had evidence.
Practice
In practice, the security of internet voting is more complicated than sketched above (see Gjøsteen (2022) for some issues), but internet voting is deployed for many elections already, by the International Association for Cryptologic Research, the Church of Norway and Estonia, plus many others.
One complication is that the voter’s computer may be compromised. So-called return codes provide one mechanism whereby voters can verify that their computer correctly encrypted their ballot. Gjøsteen and Lund (2016) evaluated one return code mechanism in a carefully designed laboratory experiment, and found evidence that the mechanism would not protect every individual voter, but would provide some protection for the overall election.
Assurance is another key challenge. How do we know that the cryptography does as claimed? Programs called proof assistants can verify that the security proofs cryptographers give are correct. Dragan et al. (2023) show how this can be used to improve assurance for cryptographic voting systems.
Like most cryptographic systems, deployed cryptographic voting schemes are not quantum-safe. Continued use of electronic voting is contingent on the development of quantum-safe alternatives. Work like Aranha et al. (2023) are key steps towards practical quantum-safe cryptographic voting systems.
References:
Diego F. Aranha, Carsten Baum, Kristian Gjøsteen, Tjerand Silde: Verifiable Mix-Nets and Distributed Decryption for Voting from Lattice-Based Assumptions. CCS 2023: 1467-1481. https://doi.org/10.1145/3576915.3616683
Constantin Catalin Dragan, François Dupressoir, Ehsan Estaji, Kristian Gjøsteen, Thomas Haines, Peter Y. A. Ryan, Peter B. Rønne, Morten Rotvold Solberg: Machine-checked proofs of privacy against malicious boards for Selene & Co. J. Comput. Secur. 31(5): 469-499 (2023). https://doi.org/10.3233/JCS-230045
Gjøsteen, K., Lund, A.S. An experiment on the security of the Norwegian electronic voting protocol. Ann. Telecommun. 71, 299–307 (2016). https://doi.org/10.1007/s12243-016-0509-8
Kristian Gjøsteen, Practical Mathematical Cryptography. Chapman and Hall/CRC, 2023. https://doi.org/10.1201/9781003149422
