Paper 2022/422

Verifiable Mix-Nets and Distributed Decryption for Voting from Lattice-Based Assumptions

Diego F. Aranha, Aarhus University
Carsten Baum, Technical University of Denmark, Aarhus University
Kristian Gjøsteen, Norwegian University of Science and Technology
Tjerand Silde, Norwegian University of Science and Technology

Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland, France, and Australia. Practical protocols usually rely on tested designs such as the mixing-and-decryption paradigm. There, multiple servers verifiably shuffle encrypted ballots, which are then decrypted in a distributed manner. While several efficient protocols implementing this paradigm exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because the design ideas of the discrete log-based voting protocols do not carry over easily to the lattice setting, due to specific problems such as noise growth and approximate relations. This work proposes a new verifiable secret shuffle for BGV ciphertexts and a compatible verifiable distributed decryption protocol. The shuffle is based on an extension of a shuffle of commitments to known values which is combined with an amortized proof of correct re-randomization. The verifiable distributed decryption protocol uses noise drowning, proving the correctness of decryption steps in zero-knowledge. Both primitives are then used to instantiate the mixing-and-decryption electronic voting paradigm from lattice-based assumptions. We give concrete parameters for our system, estimate the size of each component and provide implementations of all important sub-protocols. Our experiments show that the shuffle and decryption protocol is suitable for use in real-world e-voting schemes.

Note: This is the full version of the paper published at ACM CCS 2023. Note the updated timings for the exact amortized proof of shortness being twice the size compared to the conference version since it must be run twice to get appropriate soundness levels.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2023
lattice cryptographyverifiable mix-netsdistributed decryptionzero-knowledge proofscryptographic votingimplementation
Contact author(s)
dfaranha @ cs au dk
cabau @ dtu dk
kristian gjosteen @ ntnu no
tjerand silde @ ntnu no
2023-10-16: last of 6 revisions
2022-04-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Diego F.  Aranha and Carsten Baum and Kristian Gjøsteen and Tjerand Silde},
      title = {Verifiable Mix-Nets and Distributed Decryption for Voting from Lattice-Based Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/422},
      year = {2022},
      doi = {10.1145/3576915.3616683},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.