Paper 2022/422

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

Diego F. Aranha, Carsten Baum, Kristian Gjøsteen, and Tjerand Silde


Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland and Australia. Many organizations also use Helios for elections. While many efficient protocols exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because previous voting protocols do not carry over easily due to issues such as noise growth and approximate relations. In particular, this is a problem for tested designs such as verifiable mixing and decryption of ballot ciphertexts. In this work, we make progress in this direction. We propose a new verifiable secret shuffle for BGV ciphertexts as well as 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 for BGV decryption, proving correctness of decryption steps in zero-knowledge. We give concrete parameters for our system, estimate the size of each component and provide an implementation of all sub-protocols. Together, the shuffle and the decryption protocol are suitable for use in real-world cryptographic voting schemes, which we demonstrate with a prototype voting protocol design.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
lattice cryptographyverifiable mix-netsdistributed decryptionzero-knowledge proofscryptographic votingimplementation
Contact author(s)
dfaranha @ cs au dk
cbaum @ cs au dk
kristian gjosteen @ ntnu no
tjerand silde @ ntnu no
2022-05-22: revised
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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.