IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2023 > Lattice-Based Electronic Voting

Tjerand Silde

Friday, September 29, 2023

11:00am 302-Mountain View and Zoom3 (, password: @s3)

Tjerand Silde, Associate Professor, NTNU

Lattice-Based Electronic Voting


Cryptographic voting protocols have recently seen much interest from practitioners due to their 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 the lack of underlying zero-knowledge proofs and specific problems such as noise growth and approximate relations. In this talk, I will present recent results in lattice-based electronic voting schemes, showing that new constructions are getting close to practical. First, we gave the first lattice-based zero-knowledge proof of shuffle based on lattice assumption, with the constraint of only being able to mix messages, limiting the scheme to one shuffle-server. Then, we extended the shuffle protocol to ciphertexts and gave the first complete mixing network, allowing for an arbitrary number of shuffle servers. We also provided the first verifiable distributed decryption protocol for lattice-based encryption schemes and an implementation of all important sub-protocols. Recently, we improved the concrete efficiency of the scheme of the previous work by changing from the BGV scheme to the NTRU scheme, analyzing the concrete hardness of the NTRU problem, and adjusting recent zero-knowledge proof systems to fit in our setting. We obtain a factor 5.3 reduction in ciphertext size and 2.6 more efficient system overall, with ciphertexts of size 15KB, shuffle proofs of 130KB, and decryption proofs of 85 KB per ciphertext. This talk is based on joint work with Diego F. Aranha (Aarhus University), Carsten Baum (DTU), Kristian Gjøsteen (NTNU), Patrick Hough (Oxford University), Caroline Sandsbråten (NTNU), and Thor Tunge (NTNU).