Post-Quantum Resistant E-Voting Scheme

Guillaume Kaim, Sébastien Canard, Adeline Roux-Langlois, Jacques Traoré

Abstract

We propose a new post-quantum e-voting scheme whose security relies on lattice assumptions. Compared to the state-of-the-art, our work does not make use of homomorphic primitives nor mix-nets servers, that are more traditional ways to build electronic voting protocols. The main reason is that zero-knowledge proofs, mandatory in the two aforementioned frameworks, are far to be as efficient as in "classical" cryptography, leading us to explore another alternative. We therefore base our work on a framework introduced by Fujioka et al. at Auscrypt 1992 that makes use of a blind signature scheme as the main building block. We depart however from this seminal work by allowing threshold issuance of blind signatures (to prevent ballot stuffing by malicious authorities) and by using a threshold post-quantum public key encryption scheme (rather than a commitment scheme) to allow voters to "vote and go" and to prevent "partial results". We instantiate all the required primitives with lattice-based constructions leading to a new secure Internet voting scheme which is conjectured to resist attacks by quantum computers. One key advantage of our protocol is that it can efficiently handle elections with several candidates (and not only referendums). Indeed, we can consider as many candidates as the message space of the underlying encryption scheme allows it without weakening the whole voting protocol by increasing the parameters size as with previous post-quantum voting schemes.