Distributed ElGamal à la Pedersen: Application to Helios

ABSTRACT

Real-world elections often require threshold cryptosystems so that any t out of l trustees can proceed to tallying. This is needed to protect the confidentiality of the voters' votes against curious authorities (at least t+1 trustees must collude to learn individual votes) as well as to increase the robustness of the election (in case some trustees become unavailable, t+1 trustees suffice to compute the election result). We describe a fully distributed (with no dealer) threshold cryptosystem suitable for the Helios voting system (in particular, suitable to partial decryption), and prove it secure under the Decisional Diffie-Hellman assumption. Secondly, we propose a fully distributed variant of Helios, that allows for arbitrary threshold parameters l,t, together with a proof of ballot privacy when used for referendums.

Our modification of Helios can be seen as revision of the seminal multi-authority election system from Cramer, Gennaro and Schoenmakers, upon which the original Helios system is based. As such, our work implies, to our knowledge, the first formal proof of ballot privacy for the scheme by Cramer et al. Thirdly, we provide the first open-source implementation of Helios with a fully distributed key generation setup.

References

1. International association for cryptologic research. Elections page at http://www. iacr.org/elections/.
2. https://github.com/benadida/helios-server/issues/35.
3. Masayuki Abe and Serge Fehr. Adaptively secure Feldman VSS and applications to universally-composable threshold cryptography. In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in Computer Science, pages 317--334. Springer, 2004.
4. Ben Adida, Olivier de Marneffe, Oliver Pereira, and Jean-Jacques Quisquater. Electing a university president using open-audit voting: Analysis of real-world use of Helios. In Proceedings of the 2009 conference on Electronic voting technology/workshop on trustworthy elections, 2009.
5. Myrto Arapinis, Véronique Cortier, Steve Kremer, and Mark Ryan. Practical everlasting privacy. In David A. Basin and John C. Mitchell, editors, POST, volume 7796 of Lecture Notes in Computer Science, pages 21--40. Springer, 2013.
6. Josh Benaloh. Ballot casting assurance via voter-initiated poll station auditing. In Proceedings of the Second Usenix/ACCURATE Electronic Voting Technology Workshop, 2007.
7. David Bernhard, Véronique Cortier, Olivier Pereira, Ben Smyth, and Bogdan Warinschi. Adapting Helios for provable ballot secrecy. In Springer, editor, Proceedings of the 16th European Symposium on Research in Computer Security (ESORICS'11), volume 6879 of Lecture Notes in Computer Science, 2011.
8. David Bernhard, Véronique Cortier, Olivier Pereira, and Bogdan Warinschi. Measuring vote privacy, revisited. In 19th ACM Conference on Computer and Communications Security (CCS'12), Raleigh, USA, October 2012. ACM.
9. David Bernhard, Olivier Pereira, and Bogdan Warinschi. How not to prove yourself: Pitfalls of the Fiat-Shamir heuristic and applications to helios. In X. Wang and K. Sako, editors, ASIACRYPT, volume 7658 of Lecture Notes in Computer Science, pages 626--643. Springer, 2012.
10. David Bernhard, Olivier Pereira, and Bogdan Warinschi. On necessary and sufficient conditions for private ballot submission. Cryptology ePrint Archive, Report 2012/236, 2012. http://eprint.iacr.org/.
11. David Bernhard and Ben Smyth. Ballot privacy and ballot independence coincide. In Springer, editor, Proceedings of the 18th European Symposium on Research in Computer Security (ESORICS'13), Lecture Notes in Computer Science, 2013.
12. Dan Boneh, Xavier Boyen, and Shai Halevi. Chosen ciphertext secure public key threshold encryption without random oracles. In David Pointcheval, editor, CT-RSA, volume 3860 of Lecture Notes in Computer Science, pages 226--243. Springer, 2006.
13. Colin Boyd, editor. Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9--13, 2001, Proceedings, volume 2248 of Lecture Notes in Computer Science. Springer, 2001.
14. Michael R. Clarkson, Stephen Chong, and Andrew C. Myers. Civitas: Toward a secure voting system. In Proc. IEEE Symposium on Security and Privacy, pages 354--368, 2008.
15. Véronique Cortier and Ben Smyth. Attacking and fixing Helios: An analysis of ballot secrecy. In CSF, pages 297--311. IEEE Computer Society, 2011.
16. Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, CRYPTO, volume 839 of Lecture Notes in Computer Science, pages 174--187. Springer, 1994.
17. Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Walter Fumy, editor, EUROCRYPT, volume 1233 of Lecture Notes in Computer Science, pages 103--118. Springer, 1997.
18. Edouard Cuvelier, Olivier Pereira, and Thomas Peters. Election verifiability or ballot privacy: Do we need to choose? In Springer, editor, Proceedings of the 18th European Symposium on Research in Computer Security (ESORICS'13), Lecture Notes in Computer Science, 2013.
19. Adam M. Davis, Dmitri Chmelev, and Michael R. Clarkson. Civitas: Implementation of a threshold cryptosystem. Computing and information science technical report, Cornell University, 2008.
20. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO 1986, volume 263 of Lecture Notes in Computer Science, pages 186--194. Springer, 1987.
21. Pierre-Alain Fouque and David Pointcheval. Threshold cryptosystems secure against chosen-ciphertext attacks. In BoydciteDBLP:conf/asiacrypt/2001, pages 351--368.
22. Atsushi Fujioka, Tatsuaki Okamoto, and Kazuo Ohta. A practical secret voting scheme for large scale elections. In Jennifer Seberry and Yuliang Zheng, editors, AUSCRYPT, volume 718 of Lecture Notes in Computer Science, pages 244--251. Springer, 1992.
23. Ryan W. Gardner, Sujata Garera, and Aviel D. Rubin. Coercion resistant end-to-end voting. In Roger Dingledine and Philippe Golle, editors, Financial Cryptography, volume 5628 of Lecture Notes in Computer Science, pages 344--361. Springer, 2009.
24. Rosario Gennaro. Achieving independence efficiently and securely. In James H. Anderson, editor, PODC, pages 130--136. ACM, 1995.
25. Rosario Gennaro. An optimally efficient multi-authority election scheme. SCN 1996 - Security in Communication Networks Workshop, 1996. http://www.di.unisa.it/SCN96/papers/Gennaro.ps.
26. Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. In Jacques Stern, editor, EUROCRYPT, volume 1592 of Lecture Notes in Computer Science, pages 295--310. Springer, 1999.
27. Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure applications of Pedersen's distributed key generation protocol. In Marc Joye, editor, CT-RSA, volume 2612 of Lecture Notes in Computer Science, pages 373--390. Springer, 2003.
28. Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. J. Cryptology, 20(1):51--83, 2007.
29. Stéphane Glondu. Open source helios with fully distributed key generation. https://github.com/glondu/helios-server.
30. Jens Groth. Evaluating security of voting schemes in the universal composability framework. In Markus Jakobsson, Moti Yung, and Jianying Zhou, editors, ACNS, volume 3089 of Lecture Notes in Computer Science, pages 46--60. Springer, 2004.
31. Ari Juels, Dario Catalano, and Markus Jakobsson. Coercion-resistant electronic elections. In Vijay Atluri, Sabrina De Capitani di Vimercati, and Roger Dingledine, editors, WPES, pages 61--70. ACM, 2005.
32. Ari Juels, Dario Catalano, and Markus Jakobsson. Coercion-resistant electronic elections. In Towards Trustworthy Elections, pages 37--63, 2010.
33. Ralf Küsters, Tomasz Truderung, and Andreas Vogt. A game-based definition of coercion-resistance and its applications. In CSF, pages 122--136. IEEE Computer Society, 2010.
34. Ralf Küsters, Tomasz Truderung, and Andreas Vogt. Verifiability, privacy, and coercion-resistance: New insights from a case study. In IEEE Symposium on Security and Privacy, pages 538--553. IEEE Computer Society, 2011.
35. Benoıt Libert and Moti Yung. Non-interactive cca-secure threshold cryptosystems with adaptive security: New framework and constructions. In Ronald Cramer, editor, TCC, volume 7194 of Lecture Notes in Computer Science, pages 75--93. Springer, 2012.
36. Anna Lysyanskaya and Chris Peikert. Adaptive security in the threshold setting: From cryptosystems to signature schemes. In BoydciteDBLP:conf/asiacrypt/2001, pages 331--350.
37. Tal Moran and Moni Naor. Receipt-free universally-verifiable voting with everlasting privacy. In Cynthia Dwork, editor, CRYPTO, volume 4117 of Lecture Notes in Computer Science, pages 373--392. Springer, 2006.
38. Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO, pages 129--140, 1991.
39. Victor Shoup and Rosario Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. J. Cryptology, 15(2):75--96, 2002.
40. Yiannis Tsiounis and Moti Yung. On the security of ElGamal based encryption. In Hideki Imai and Yuliang Zheng, editors, Public Key Cryptography, volume 1431 of Lecture Notes in Computer Science, pages 117--134. Springer, 1998.
41. Douglas Wikström. Universally composable DKG with linear number of exponentiations. In Carlo Blundo and Stelvio Cimato, editors, SCN, volume 3352 of Lecture Notes in Computer Science, pages 263--277. Springer, 2004.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption