Cryptology ePrint Archive: Report 2017/1235

Practical Quantum-Safe Voting from Lattices

Rafaël del Pino and Vadim Lyubashevsky and Gregory Neven and Gregor Seiler

Abstract: We propose a lattice-based electronic voting scheme, EVOLVE (Electronic Voting from Lattices with Verification), which is conjectured to resist attacks by quantum computers. Our protocol involves a number of voting authorities so that vote privacy is maintained as long as at least one of the authorities is honest, while the integrity of the result is guaranteed even when all authorities collude. Furthermore, the result of the vote can be independently computed by any observer. At the core of the protocol is the utilization of a homomorphic commitment scheme with strategically orchestrated zero-knowledge proofs: voters use approximate but efficient “Fiat-Shamir with Aborts” proofs to show the validity of their vote, while the authorities use amortized exact proofs to show that the commitments are well-formed. We also present a novel efficient zero-knowledge proof that one of two lattice-based statements is true (so-called OR proof) and a new mechanism to control the size of the randomness when applying the homomorphism to commitments. We give concrete parameter choices to securely instantiate and evaluate the efficiency of our scheme. Our prototype implementation shows that the voters require 8 milliseconds to submit a vote of size about 20KB to each authority and it takes each authority 0.15 seconds per voter to create a proof that his vote was valid. The size of the vote share that each authority produces is approximately 15KB per voter, which we believe is well within the practical bounds for a large-scale election.

Category / Keywords: cryptographic protocols / Voting, Commitment, Zero Knowledge, Post Quantum, Lattice

Original Publication (with minor differences): CCS

Date: received 22 Dec 2017

Contact author: delpino at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20171222:211245 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]