{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T09:01:15Z","timestamp":1767085275422,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031722431"},{"type":"electronic","value":"9783031722448"}],"license":[{"start":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T00:00:00Z","timestamp":1727049600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T00:00:00Z","timestamp":1727049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/978-3-031-72244-8_7","type":"book-chapter","created":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T19:01:32Z","timestamp":1727031692000},"page":"107-123","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["ZK-SNARKs for\u00a0Ballot Validity: A Feasibility Study"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6905-3571","authenticated-orcid":false,"given":"Nicolas","family":"Huber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9071-9312","authenticated-orcid":false,"given":"Ralf","family":"K\u00fcsters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8289-4970","authenticated-orcid":false,"given":"Julian","family":"Liedtke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1901-3659","authenticated-orcid":false,"given":"Daniel","family":"Rausch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,23]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Abdolmaleki, B., et\u00a0al.: UC-Secure CRS Generation for SNARKs. In: AFRICACRYPT 2019, Proceedings. LNCS, vol. 11627, pp. 99\u2013117. Springer (2019)","DOI":"10.1007\/978-3-030-23696-0_6"},{"key":"7_CR2","unstructured":"Adida, B., et\u00a0al.: Electing a university president using open-audit voting: analysis of real-world use of helios. In: USENIX\/ACCURATE Electronic Voting Technology (EVT 2009) (2009)"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Ames, S., et\u00a0al.: Ligero: lightweight sublinear arguments without a trusted setup. In: ACM CCS 2017, pp. 2087\u20132104 (2017)","DOI":"10.1145\/3133956.3134104"},{"issue":"6","key":"7_CR4","doi-asserted-by":"publisher","first-page":"4733","DOI":"10.1109\/TDSC.2022.3232813","volume":"20","author":"M Bell\u00e9s-Mu\u00f1oz","year":"2023","unstructured":"Bell\u00e9s-Mu\u00f1oz, M., et al.: Circom: a circuit description language for building zero-knowledge applications. IEEE Trans. Dependable Secur. Comput. 20(6), 4733\u20134751 (2023)","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., et\u00a0al.: Secure sampling of public parameters for succinct zero knowledge proofs. In: IEEE SP 2015, pp. 287\u2013304. IEEE Computer Society (2015)","DOI":"10.1109\/SP.2015.25"},{"key":"7_CR6","first-page":"46","volume":"2018","author":"E Ben-Sasson","year":"2018","unstructured":"Ben-Sasson, E., et al.: Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive 2018, 46 (2018)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"7_CR7","first-page":"1050","volume":"2017","author":"S Bowe","year":"2017","unstructured":"Bowe, S., Gabizon, A., Miers, I.: Scalable multi-party computation for zk-SNARK parameters in the random beacon model. IACR Cryptol. ePrint Arch. 2017, 1050 (2017)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., et\u00a0al.: Bulletproofs: short proofs for confidential transactions and more. In: SP 2018, pp. 315\u2013334 (2018)","DOI":"10.1109\/SP.2018.00020"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chaum, D., Pedersen, T.P.: Wallet databases with observers. In: CRYPTO \u201992. LNCS, vol.\u00a0740, pp. 89\u2013105. Springer (1992)","DOI":"10.1007\/3-540-48071-4_7"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: EUROCRYPT 2020, pp. 769\u2013793 (2020)","DOI":"10.1007\/978-3-030-45721-1_27"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-030-19052-1_14","volume-title":"Foundations of Security, Protocols, and Equational Reasoning","author":"V Cortier","year":"2019","unstructured":"Cortier, V., Gaudry, P., Glondu, S.: Belenios: a simple private and verifiable electronic voting system. In: Guttman, J.D., Landwehr, C.E., Meseguer, J., Pavlovic, D. (eds.) Foundations of Security, Protocols, and Equational Reasoning. LNCS, vol. 11565, pp. 214\u2013238. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-19052-1_14"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Cortier, V., Gaudry, P., Yang, Q.: A toolbox for verifiable tally-hiding e-voting systems. In: ESORICS 2022. LNCS, vol. 13555, pp. 631\u2013652. Springer (2022)","DOI":"10.1007\/978-3-031-17146-8_31"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Cramer, R., Damg\u00e5rd, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: CRYPTO 1994, pp.174\u2013187. Springer (1994)","DOI":"10.1007\/3-540-48658-5_19"},{"key":"7_CR14","unstructured":"Debian Project: Debian Voting Information (2024). https:\/\/www.debian.org\/vote\/"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Devillez, H., Pereira, O., Peters, T.: How to verifiably encrypt many bits for an election? In: ESORICS 2022. LNCS, vol. 13555, pp. 653\u2013671. Springer (2022)","DOI":"10.1007\/978-3-031-17146-8_32"},{"key":"7_CR16","unstructured":"European Broadcasting Union: Eurovision Song Contest - How it works (2024). https:\/\/eurovision.tv\/about\/how-it-works"},{"key":"7_CR17","first-page":"953","volume":"2019","author":"A Gabizon","year":"2019","unstructured":"Gabizon, A., Williamson, Z.J., Ciobotaru, O.: Plonk: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptol. ePrint Arch. 2019, 953 (2019)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"7_CR18","unstructured":"Gaudry, P.: Some ZK security proofs for belenios (2017)"},{"key":"7_CR19","unstructured":"Gautam Botrel and Others: Consensys\/gnark: v0.10.0 (2024). https:\/\/doi.org\/10.5281\/zenodo.11034183"},{"key":"7_CR20","unstructured":"Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster Zero-Knowledge for boolean circuits. In: USENIX Security Symposium 2016, pp. 1069\u20131083. USENIX Association (2016)"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Groth, J.: Non-interactive zero-knowledge arguments for voting. In: ACNS 2005. LNCS, vol.\u00a03531, pp. 467\u2013482 (2005)","DOI":"10.1007\/11496137_32"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: EUROCRYPT 2016. LNCS, vol.\u00a09666, pp. 305\u2013326. Springer (2016)","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"7_CR23","unstructured":"Hertel, F., et\u00a0al.: Extending the tally-hiding ordinos system: implementations for borda, hare-niemeyer, condorcet, and instant-runoff voting. In: E-Vote-ID 2021, pp. 269\u2013284. University of Tartu Press (2021)"},{"key":"7_CR24","unstructured":"Hopwood, D.E., et\u00a0al.: Zcash Protocol Specification (2024). https:\/\/zips.z.cash\/protocol\/protocol.pdf"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Huber, N., et\u00a0al.: Kryvos: publicly tally-hiding verifiable e-voting. In: CCS 2022, pp. 1443\u20131457. ACM (2022)","DOI":"10.1145\/3548606.3560701"},{"key":"7_CR26","unstructured":"Huber, N., et\u00a0al.: Implementation of our Circuits (2024). https:\/\/github.com\/HicolasNuber\/ballotsnarks"},{"issue":"2","key":"7_CR27","first-page":"130","volume":"19","author":"R Joaquim","year":"2014","unstructured":"Joaquim, R.: How to prove the validity of a complex ballot encryption to the voter and the public. JISA 19(2), 130\u2013142 (2014)","journal-title":"JISA"},{"key":"7_CR28","unstructured":"Kosba, A., et\u00a0al.: C$$\\emptyset $$C$$\\emptyset $$: A framework for building composable zero-knowledge proofs. Cryptology ePrint Archive (2015)"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Maller, M., et\u00a0al.: Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In: Proceedings of the 2019 ACM CCS, pp. 2111\u20132128 (2019)","DOI":"10.1145\/3319535.3339817"},{"issue":"5","key":"7_CR30","doi-asserted-by":"publisher","first-page":"421","DOI":"10.3233\/JCS-230047","volume":"31","author":"D Mestel","year":"2023","unstructured":"Mestel, D., M\u00fcller, J., Reisert, P.: How efficient are replay attacks against vote privacy? A formal quantitative analysis. J. Comput. Secur. 31(5), 421\u2013467 (2023)","journal-title":"J. Comput. Secur."},{"issue":"8","key":"7_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s42452-019-0989-z","volume":"1","author":"E Morais","year":"2019","unstructured":"Morais, E., Koens, T., van Wijk, C., Koren, A.: A survey on zero knowledge range proofs and applications. SN Appl. Sci. 1(8), 1\u201317 (2019). https:\/\/doi.org\/10.1007\/s42452-019-0989-z","journal-title":"SN Appl. Sci."},{"key":"7_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/3-540-44709-1_12","volume-title":"Cryptographic Hardware and Embedded Systems \u2014 CHES 2001","author":"K Okeya","year":"2001","unstructured":"Okeya, K., Sakurai, K.: Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve. In: Ko\u00e7, \u00c7.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 126\u2013141. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44709-1_12"},{"key":"7_CR33","unstructured":"Republic of Nauru: Electoral Act No. 15 (2024). http:\/\/ronlaw.gov.nr\/nauru_lpms\/files\/acts\/d83250a1ebdc56c1701fa7aa245af5b1.pdf"},{"key":"7_CR34","unstructured":"scipr-lab: libsnark (2024). https:\/\/github.com\/scipr-lab\/libsnark"}],"container-title":["Lecture Notes in Computer Science","Electronic Voting"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72244-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T19:02:14Z","timestamp":1727031734000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72244-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,23]]},"ISBN":["9783031722431","9783031722448"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72244-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,23]]},"assertion":[{"value":"23 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"E-Vote-ID","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Joint Conference on Electronic Voting","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tarragona","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"evoteid2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}