Practical Quantum-Safe Voting from Lattices
| Autor: | Gregor Seiler, Gregory Neven, Rafaël Del Pino, Vadim Lyubashevsky |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer Science::Computer Science and Game Theory
Theoretical computer science Computer science Electronic voting media_common.quotation_subject Homomorphic encryption 020206 networking & telecommunications 02 engineering and technology Mathematical proof Computer security computer.software_genre Cardinal voting systems Computer Science::Multiagent Systems Voting 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Homomorphism Commitment scheme Zero-knowledge proof computer media_common |
| Zdroj: | CCS |
| DOI: | 10.1145/3133956.3134101 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|