Paper Info
Title
Practical Quantum-Safe Voting from Lattices.
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 $20$KB 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 $15$KB per voter, which we believe is well within the practical bounds for a large-scale election.
Year
DOI
Venue
2017
10.1145/3133956.3134101
CCS
Keywords
DocType
Volume
E-Voting, Lattices, Implementation, Zero-Knowledge, Post-Quantum
Journal
2017
ISBN
Citations 
PageRank 
978-1-4503-4946-8
3
0.39
References 
Authors
18
4
Name
Order
Citations
PageRank
Rafaël Del Pino1172.97
Vadim Lyubashevsky2117459.91
Gregory Neven3140568.87
Gregor Seiler4268.73