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
Abstract

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. In this work, we propose 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
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
History
2023-01-24: last of 2 revisions
2022-04-06: received
See all versions
Short URL
https://ia.cr/2022/422
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/422,
      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},
      note = {\url{https://eprint.iacr.org/2022/422}},
      url = {https://eprint.iacr.org/2022/422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.