ZK-SNARKs for Ballot Validity: A Feasibility Study

Nicolas Huber; Ralf Kuesters; Julian Liedtke; Daniel Rausch

Paper 2024/1902

ZK-SNARKs for Ballot Validity: A Feasibility Study

Nicolas Huber

, University of Stuttgart

Ralf Kuesters

, University of Stuttgart

Julian Liedtke

, University of Stuttgart

Daniel Rausch

, University of Stuttgart

Abstract

Electronic voting (e-voting) systems have become more prevalent in recent years, but security concerns have also increased, especially regarding the privacy and verifiability of votes. As an essential ingredient for constructing secure e-voting systems, designers often employ zero-knowledge proofs (ZKPs), allowing voters to prove their votes are valid without revealing them. Invalid votes can then be discarded to protect verifiability without compromising the privacy of valid votes. General purpose zero-knowledge proofs (GPZKPs) such as ZK-SNARKs can be used to prove arbitrary statements, including ballot validity. While a specialized ZKP that is constructed only for a specific election type/voting method, ballot format, and encryption/commitment scheme can be more efficient than a GPZKP, the flexibility offered by GPZKPs would allow for quickly constructing e-voting systems for new voting methods and new ballot formats. So far, however, the viability of GPZKPs for showing ballot validity for various ballot formats, in particular, whether and in how far they are practical for voters to compute, has only recently been investigated for ballots that are computed as Pedersen vector commitments in an ACM CCS 2022 paper by Huber et al. Here, we continue this line of research by performing a feasibility study of GPZKPs for the more common case of ballots encrypted via Exponential ElGamal encryption. Specifically, building on the work by Huber et al., we describe how the Groth16 ZK-SNARK can be instantiated to show ballot validity for arbitrary election types and ballot formats encrypted via Exponential ElGamal. As our main contribution, we implement, benchmark, and compare several such instances for a wide range of voting methods and ballot formats. Our benchmarks not only establish a basis for protocol designers to make an educated choice for or against such a GPZKP, but also show that GPZKPs are actually viable for showing ballot validity in voting systems using Exponential ElGamal.

Note: This is a full version of a paper published at E-Vote-ID 2024 with extended material.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. E-Vote-ID 2024
DOI: 10.1007/978-3-031-72244-8_7
Keywords: electronic voting verfiability privacy SNARKs zk-SNARKs Zero knowledge proof
Contact author(s): nicolas huber @ sec uni-stuttgart de
ralf kuesters @ sec uni-stuttgart de
julian liedtke @ sec uni-stuttgart de
daniel rausch @ sec uni-stuttgart de
History: 2024-11-25: approved; 2024-11-22: received; See all versions
Short URL: https://ia.cr/2024/1902
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1902,
      author = {Nicolas Huber and Ralf Kuesters and Julian Liedtke and Daniel Rausch},
      title = {{ZK}-{SNARKs} for Ballot Validity: A Feasibility Study},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1902},
      year = {2024},
      doi = {10.1007/978-3-031-72244-8_7},
      url = {https://eprint.iacr.org/2024/1902}
}