Practical Quantum-Safe Voting from Lattices

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.