Browsing by Author "Röhr, Felix"

Now showing 1 - 1 of 1

Open Access
Comparative analysis of zk-SNARK instantiations for ensuring ballot validity
(2025) Röhr, Felix
As e-voting schemes become increasingly prevalent, ensuring their security is essential. In many cases, Zero Knowledge Proofs (ZKPs) are used to allow users to prove the validity of their (encrypted) votes without revealing them. One class of ZKPs that can be used to prove (essentially) arbitrary valid statements are General Purpose ZKPs (GPZKPs) with Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) being one type of such. zk-SNARKs are a good choice for our use case since voters are usually resource constrained in practice and zk-SNARKs typically offer small proofs and efficient proof generation algorithms. A typical form of encrypting ballots in e-voting schemes is Exponential ElGamal (EEG) encryption. The feasability of GPZKPs for showing validity of ballots that are component-wise encrypted using EEG ciphertexts in voting systems with arbitrary election types and ballot formats using Groth16-SNARKs has been shown by Huber et al. To demonstrate the versatility of GPZKPs, the authors implemented ballot validity relations for the different election types Single Vote, Multi-Vote, Line-Vote, Multi-Vote with Rules, the ranked election types Pointlist-Borda and Borda Tournament Style, Condorcet methods and Majority Judgment in libsnark and benchmarked their performance. We extend on this research by implementing ballot validity relations for the same election types in Circom and generating the ZKPs using snarkjs. First, we follow the same approach as Huber et al. for our implementation, using EEG encryption instantiated with elliptic curves in Montgomery form for the encryption of individual ballot entries. Then, as our main contribution, we introduce a novel variant of computing EEG ciphertexts: Precomputed Powers EEG (PPEEG). By providing some precomputed powers of group elements to the encryption, we reduce the computations needed for ZKPs of ballot validity. Additionally, we instantiate PPEEG encryption with elliptic curves in Twisted Edwards form rather than elliptic curves in Montgomery form, reducing the computational effort further. Furthermore, we improve the performance of the election type specific computations in the ballot validity proofs for several election types, most notably for Condorcet methods. However, these improvements are negligible compared to the reduction of computational effort in the encryption part in most cases. Compared to the results by Huber et. al, we reduce the computational effort for the ballot validity proofs accross all election types by 35% to 82% depending on the metric. Moreover, we can compute ballot validity proofs for ballots with up to 1000 votes on a standard PC which is sufficient for almost all real-world applications of any of the covered election types.