[en] Elections are an important corner stone of democratic processes. In addition to publishing
the final result (e.g., the overall winner), elections typically publish the full tally consisting of all
(aggregated) individual votes. This causes several issues, including loss of privacy for both voters and election candidates as well as so-called Italian attacks that allow for easily coercing voters.
Several e-voting systems have been proposed to address these issues by hiding (parts of) the tally. This property is called tally-hiding. Existing tally-hiding e-voting systems in the literature aim at hiding (part of) the tally from everyone, including voting authorities, while at the same time offering verifiability, an important and standard feature of modern e-voting systems which allows voters and external observers to check that the published election result indeed corresponds to how voters actually voted. In contrast, real elections often follow a different common practice for hiding the tally: the voting authorities internally compute (and learn) the full tally but publish only the final result (e.g., the winner). This practice, which we coin publicly tally-hiding, indeed solves the aforementioned issues for the public, but currently has to sacrifice verifiability due to a lack of practical systems.
In this paper, we close this gap. We formalize the common notion of publicly tally-hiding and propose the first provably secure verifiable e-voting system, called Kryvos, which directly targets publicly tally-hiding elections. We instantiate our system for a wide range of both simple and complex voting methods and various result functions. We provide an extensive evaluation which shows that Kryvos is practical and able to handle a large number of candidates, complex voting methods and result functions. Altogether, Kryvos shows that the concept of publicly tally-hiding offers a new trade-off between privacy and efficiency that is different from all previous tally-hiding systems and which allows for a radically new protocol design resulting in a practical e-voting system.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Huber, Nicolas
Kuesters, Ralf
Krips, Toomas
Liedtke, Julian
MUELLER, Johannes ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
Rausch, Daniel
Reisert, Pascal
Vogt, Andreas
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Kryvos: Publicly Tally-Hiding Verifiable E-Voting
Date de publication/diffusion :
2022
Nom de la manifestation :
2022 ACM SIGSAC Conference on Computer and Communications Security
Date de la manifestation :
November 7-11, 2022
Titre de l'ouvrage principal :
2022 ACM SIGSAC Conference on Computer and Communications Security
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
Projet FnR :
FNR14698166 - Future-proofing Privacy In Secure Electronic Voting, 2020 (01/01/2021-31/12/2023) - Johannes Mueller
ACM. 2020. Q&A on ACM's Internet Voting. https: //www. Acm. org/binaries/ content/assets/acmelections/acminternetvoting-1. pdf.
B. Adida. 2008. Helios: Web-based Open-Audit Voting. In USENIX 2008. 335-348.
Ben Adida, Olivier de Marneffe, Olivier Pereira, and Jean-Jaques Quisquater. 2009. Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios. In USENIX/ACCURATE Electronic Voting Technology (EVT 2009).
Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. 2017. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In Proceedings of the 2017 ACM CCS. 2087-2104.
Thomas Attema, Ignacio Cascudo, Ronald Cramer, Ivan Bjerre Damgård, and Daniel Escudero. 2022. Vector Commitments over Rings and Compressed-Protocols. Cryptology ePrint Archive (2022).
Michel Balinski and Rida Laraki. 2007. A Theory of Measuring, Electing, and Ranking. Proceedings of the National Academy of Sciences 104, 21 (2007), 8720-8725.
Michel Balinski and Rida Laraki. 2014. Judge: Don't Vote Operations Research 62, 3 (2014), 483-511.
Susan Bell, Josh Benaloh, Mike Byrne, Dana DeBeauvoir, Bryce Eakin, Gail Fischer, Philip Kortum, Neal McBurnett, Julian Montoya, Michelle Parker, Olivier Pereira, Philip Stark, DanWallach, and Michael Winn. 2013. STAR-Vote: A Secure, Transparent, Auditable, and Reliable Voting System. USENIX Journal of Election Technology and Systems (JETS) 1 (August 2013), 18-37.
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2018. Scalable, Transparent, and Post-Quantum Secure Computational Integrity. IACR Cryptology ePrint Archive 2018 (2018), 46.
Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. 2019. Aurora: Transparent Succinct Arguments for R1CS. In Advances in Cryptology-EUROCRYPT 2019-38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 11476). Springer, 103-128.
J. G. Benaloh. 1987. Verifiable Secret Ballot Elections. Ph. D. Dissertation. Yale University.
Josh Benaloh. 2007. Ballot Casting Assurance via Voter-Initiated Poll Station Auditing. In 2007 USENIX/ACCURATE Electronic Voting Technology Workshop, EVT'07, Boston, MA, USA, August 6, 2007.
Josh Benaloh, Tal Moran, Lee Naish, Kim Ramchen, and Vanessa Teague. 2009. Shuffle-Sum: Coercion-Resistant Verifiable Tallying for STV Voting. IEEE Trans. Information Forensics and Security 4, 4 (2009), 685-698.
J. D. Benaloh. 1986. Improving Privacy in Cryptographic Elections (Technical Report). Technical Report. Technical report.
D. Bernhard, V. Cortier, D. Galindo, O. Pereira, and B. Warinschi. 2015. SoK: A Comprehensive Analysis of Game-Based Ballot Privacy Definitions. In IEEE S&P 2015. 499-516.
Jonathan Bootle and Jens Groth. 2018. Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials. In Public-Key Cryptography-PKC 2018-21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part II (Lecture Notes in Computer Science, Vol. 10770). Springer, 561-588.
Xavier Boyen, Thomas Haines, and Johannes Müller. 2020. A Verifiable and Practical Lattice-Based Decryption Mix Net with External Auditing. In Computer Security-25th European Symposium on Research in Computer Security, ESORICS 2020.
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, PieterWuille, and Gregory Maxwell. 2018. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA. IEEE Computer Society, 315-334.
Jan Camenisch and Victor Shoup. 2003. Practical Verifiable Encryption and Decryption of Discrete Logarithms. In CRYPTO 2003, Proceedings (LNCS, Vol. 2729). Springer, 126-144.
Matteo Campanelli, Dario Fiore, and Anaïs Querol. 2019. LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019. ACM, 2075-2092.
Sébastien Canard, David Pointcheval, Quentin Santos, and Jacques Traoré. 2018. Practical Strategy-Resistant Privacy-Preserving Elections. In ESORICS 2018. 331-349.
D. Chaum, R. Carback, J. Clark, A. Essex, S. Popoveniuc, R. L. Rivest, P. Y. A. Ryan, E. Shen, and A. T. Sherman. 2008. Scantegrity II: End-to-End Verifiability for Optical Scan Election Systems using Invisible Ink Confirmation Codes. In USENIX/ACCURATE Electronic Voting Technology (EVT 2008). USENIX Association.
Alessandro Chiesa, Dev Ojha, and Nicholas Spooner. 2020. Fractal: Post-quantum and Transparent Recursive Proofs from Holography. In EUROCRYPT 2020, Proceedings, Part I (LNCS, Vol. 12105). Springer, 769-793.
M. R. Clarkson, S. Chong, and A. C. Myers. 2008. Civitas: Toward a Secure Voting System. In S&P 2008. 354-368.
Michael R. Clarkson and Andrew C. Myers. 2005. Coercion-Resistant Remote Voting Using Decryption Mixes. In In Frontiers in Electronic Elections (FEE 2005).
V. Cortier, D. Galindo, S. Glondu, and M. Izabachène. 2014. Election Verifiability for Helios under Weaker Trust Assumptions. In ESORICS 2014. 327-344.
V. Cortier, D. Galindo, R. Küsters, J. Müller, and T. Truderung. 2016. SoK: Verifiability Notions for E-Voting Protocols. In S&P 2016. 779-798.
Véronique Cortier, Pierrick Gaudry, and Quentin Yang. 2021. A toolbox for verifiable tally-hiding e-voting systems. IACR Cryptol. ePrint Arch. 2021 (2021), 491.
Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. 1994. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Advances in Cryptology-CRYPTO '94, Proceedings. 174-187.
Ronald Cramer, Matthew K. Franklin, Berry Schoenmakers, and Moti Yung. 1996. Multi-Authority Secret-Ballot Elections with Linear Work. In EUROCRYPT 1996. 72-83.
Ronald Cramer and Victor Shoup. 1998. A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In Advances in Cryptology-CRYPTO '98, 18th Annual International Cryptology Conference, Proceedings (Lecture Notes in Computer Science, Vol. 1462), Hugo Krawczyk (Ed.). Springer, 13-25.
CrossRef. 2019. Election process and results. https: //www. crossref. org/boardand-governance/elections/.
Chris Culnane and Steve A. Schneider. 2014. A Peered Bulletin Board for Robust Use in Verifiable Voting Systems. In IEEE CSF 2014. 169-183.
Jeremy Epstein. 2015. Weakness in Depth: A Voting Machine's Demise. IEEE Secur. Priv. 13, 3 (2015), 55-58.
European Broadcasting Union. 2020. Eurovision Song Contest-How it works. https: //eurovision. Tv/about/how-it-works.
Boyuan Feng, Lianke Qin, Zhenfei Zhang, Yufei Ding, and Shumo Chu. 2021. ZEN: Efficient Zero-Knowledge Proofs for Neural Networks. Technical Report 2021/87. Cryptology ePrint Archive.
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. 2019. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR Cryptol. ePrint Arch. 2019 (2019), 953.
David Galindo, Sandra Guasch, and Jordi Puiggali. 2015. 2015 Neuchâtel's Castas-Intended Verification Mechanism. In VoteID 2015, Proceedings. 3-18.
Gesellschaft für Informatik (GI). 2019. GI Wahlen. https: //gi. de/wahlen.
Irene Giacomelli, Jesper Madsen, and Claudio Orlandi. 2016. ZKBoo: Faster Zero-Knowledge for Boolean Circuits. In 25th USENIX Security Symposium, 2016. USENIX Association, 1069-1083.
Government of India. 2020. Constitution of India. https: //www. india. gov. in/mygovernment/ constitution-india.
Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In EUROCRYPT 2016, Proceedings, Part II (LNCS, Vol. 9666). Springer, 305-326.
Thomas Haines, Sarah Jamie Lewis, Olivier Pereira, and Vanessa Teague. 2020. How Not to Prove Your Election Outcome. In 2020 IEEE SP 2020. IEEE, 644-660.
Thomas Haines and Johannes Müller. 2020. SoK: Techniques for Verifiable Mix Nets. In IEEE 33rd Computer Security Foundations Symposium, CSF, 2020. IEEE Computer Society.
Thomas Haines, Dirk Pattinson, and Mukesh Tiwari. 2019. Verifiable Homomorphic Tallying for the Schulze Vote Counting Scheme. In Verified Software. Theories, Tools, and Experiments-11th International Conference, VSTTE 2019, New York City, NY, USA, July 13-14, 2019, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 12031). Springer, 36-53.
James Heather. 2007. Implementing STV securely in Prêt à Voter. In IEEE CSF 2007. 157-169.
Fabian Hertel, Nicolas Huber, Jonas Kittelberger, Ralf Küsters, Julian Liedtke, and Daniel Rausch. 2021. Extending the Tally-Hiding Ordinos System: Implementations for Borda, Hare-Niemeyer, Condorcet, and Instant-Runoff Voting. Technical Report 2021/1420. Cryptology ePrint Archive.
Alejandro Hevia and Marcos A. Kiwi. 2002. Electronic Jury Voting Protocols. In LATIN 2002, Proceedings. 415-429.
Lucca Hirschi, Lara Schmid, and David A. Basin. 2020. Fixing the Achilles Heel of E-Voting: The Bulletin Board. IACR Cryptol. ePrint Arch. 2020 (2020), 109.
Nicolas Huber, Ralf Küsters, Toomas Krips, Julian Liedtke, Johannes Müller, Daniel Rausch, Pascal Reisert, and Andreas Vogt. 2022. Implementation of Kryvos. https: //github. com/JulianLiedtke/kryvos.
Nicolas Huber, Ralf Küsters, Toomas Krips, Julian Liedtke, Johannes Müller, Daniel Rausch, Pascal Reisert, and Andreas Vogt. 2022. Kryvos: Publicly Tally-Hiding Verifiable E-Voting. Cryptology ePrint Archive 2022/1132 (2022).
Wojciech Jamroga, Peter B. Rønne, Peter Y. A. Ryan, and Philip B. Stark. 2019. Risk-Limiting Tallies. In E-Vote-ID 2019, Proceedings (LNCS, Vol. 11759). Springer, 183-199.
A. Juels, D. Catalano, and M. Jakobsson. 2005. Coercion-Resistant Electronic Elections. In Proceedings of Workshop on Privacy in the Eletronic Society (WPES 2005). ACM Press, 61-70.
Sanket Kanjalkar, Ye Zhang, Shreyas Gandlur, and Andrew Miller. 2021. Publicly Auditable MPC-as-a-Service with succinct verification and universal setup. In IEEE European Symposium on Security and Privacy Workshops, EuroS&P 2021, Vienna, Austria, September 6-10, 2021. IEEE, 386-411.
Aggelos Kiayias, Annabell Kuldmaa, Helger Lipmaa, Janno Siim, and Thomas Zacharias. 2018. On the Security Properties of e-Voting Bulletin Boards. In SCN 2018, Proceedings. 505-523.
Aggelos Kiayias, Thomas Zacharias, and Bingsheng Zhang. 2015. DEMOS-2: Scalable E2E Verifiable Elections without Random Oracles. In CCS 2015. 352-363.
Aggelos Kiayias, Thomas Zacharias, and Bingsheng Zhang. 2015. End-to-End Verifiable Elections in the Standard Model. In EUROCRYPT 2015. 468-498.
Ahmed Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, Hubert Chan, Charalampos Papamanthou, Rafael Pass, Elaine Shi, et al. 2015. CC: A Framework for Building Composable Zero-Knowledge Proofs. Cryptology ePrint Archive (2015).
Ralf Küsters, Julian Liedtke, Johannes Müller, Daniel Rausch, and Andreas Vogt. 2020. Ordinos: A Verifiable Tally-Hiding Remote E-Voting System. In IEEE EuroS&P 2020.
R. Küsters, J. Müller, E. Scapin, and T. Truderung. 2016. sElect: A Lightweight Verifiable Remote Voting System. In CSF 2016. 341-354.
R. Küsters and T. Truderung. 2016. Security Analysis of Re-Encryption RPC Mix Nets. In IEEE EuroS&P 2016. IEEE Computer Society, 227-242.
R. Küsters, T. Truderung, and A. Vogt. 2010. Accountability: Definition and Relationship to Verifiability. In ACM CCS 2010. 526-535.
R. Küsters, T. Truderung, and A. Vogt. 2011. Verifiability, Privacy, and Coercion-Resistance: New Insights from a Case Study. In IEEE S&P 2011. 538-553.
R. Küsters, T. Truderung, and A. Vogt. 2012. Clash Attacks on the Verifiability of E-Voting Systems. In IEEE S&P 2012. 395-409.
R. Küsters, T. Truderung, and A. Vogt. 2014. Formal Analysis of Chaumian Mix Nets with Randomized Partial Checking. In S&P 2014. 343-358.
Jiwon Lee, Jaekyoung Choi, Jihye Kim, and Hyunok Oh. 2019. SAVER: Snarkfriendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization. IACR Cryptol. ePrint Arch. 2019 (2019), 1270.
Maine State Legislature. 2020. Ranked Choice Voting in Maine. http: //legislature. maine. gov/lawlibrary/ranked-choice-voting-in-maine/9509.
Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. 2019. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings. In Proceedings of the 2019 ACM CCS. 2111-2128.
David Mesten, Johannes Müller, and Pascal Reisert. 2022. To appear. How Efficient are Replay Attacks against Vote Privacy A Formal Quantitative Analysis. In IEEE 35rd Computer Security Foundations Symposium, CSF, 2022.
Katsuyuki Okeya and Kouichi Sakurai. 2001. Efficient Elliptic Curve Cryptosystems from a Scalar Multiplication Algorithm with Recovery of the y-Coordinate on a Montgomery-Form Elliptic Curve. In Cryptographic Hardware and Embedded Systems-CHES 2001, Third International Workshop, Paris, France, May 14-16, 2001, Proceedings (Lecture Notes in Computer Science, Vol. 2162). Springer, 126-141.
Alex Ozdemir and Dan Boneh. 2021. Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets. IACR Cryptol. ePrint Arch. (2021), 1530.
Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2013. Pinocchio: Nearly Practical Verifiable Computation. In 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19-22, 2013. IEEE Computer Society, 238-252.
Torben P. Pedersen. 1991. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Proceedings of the 11th Annual International Cryptology Conference (CRYPTO 1991) (Lecture Notes in Computer Science, Vol. 576). Springer, 129-140.
Personal communication (email) with Philip Wright, Technical Director of CES. 2020.
Kim Ramchen, Chris Culnane, Olivier Pereira, and Vanessa Teague. 2019. Universally Verifiable MPC and IRV Ballot Counting. In Financial Cryptography and Data Security-FC 2019, Revised Selected Papers (LNCS, Vol. 11598). Springer, 301-319.
Society for Industrial and Applied Mathematics (SIAM). 2019. SIAM Announces New 2020 Leadership. https: //sinews. siam. org/Details-Page/siam-announcesnew-2020-leadership-1.
D. Springall, T. Finkenauer, Z. Durumeric, J. Kitcat, H. Hursti, M. MacAlpine, and J. A. Halderman. 2014. Security Analysis of the Estonian Internet Voting System. In Proceedings of the 2014 ACM CCS. 703-715.
Alan Szepieniec and Bart Preneel. 2015. New Techniques for Electronic Voting. USENIX Journal of Election Technology and Systems (JETS) 3, 2 (2015), 46-69.
The National Archives. 2011. Greater London Authority Act 1999. https: //www. legislation. gov. uk/ukpga/1999/29/contents.
Roland Wen and Richard Buckland. 2009. Minimum Disclosure Counting for the Alternative Vote. In VoteID 2009. Proceedings (LNCS, Vol. 5767). Springer, 122-140.
S. Wolchok, E. Wustrow, J. A. Halderman, H. K. Prasad, A. Kankipati, S. K. Sakhamuri, V. Yagati, and R. Gonggrijp. 2010. Security Analysis of India's electronic Voting Machines. In Proceedings of the 17th ACM CCS. 1-14.
