Abstract
We study ballot independence for election schemes:
-
We formally define ballot independence as a cryptographic game and prove that ballot secrecy implies ballot independence.
-
We introduce a notion of controlled malleability and show that it is sufficient for ballot independence. We also show that non-malleable ballots are sufficient, but not necessary, for ballot independence.
-
We prove that ballot independence is sufficient for ballot secrecy under practical assumptions.
Our results show that ballot independence is necessary in election schemes satisfying ballot secrecy. Furthermore, our sufficient conditions enable simpler proofs of ballot secrecy.
The full version of this paper is available as an IACR Cryptology ePrint [1].
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Smyth, B., Bernhard, D.: Ballot secrecy and ballot independence coincide. Cryptology ePrint Archive, Report 2013/235 (2013)
Delaune, S., Kremer, S., Ryan, M.: Coercion-Resistance and Receipt-Freeness in Electronic Voting. In: CSFW 2006: 19th Computer Security Foundations Workshop, pp. 28–42. IEEE Computer Society (2006)
Backes, M., Hriţcu, C., Maffei, M.: Automated Verification of Remote Electronic Voting Protocols in the Applied Pi-calculus. In: CSF 2008: 21st Computer Security Foundations Symposium, pp. 195–209. IEEE Computer Society (2008)
Cortier, V., Smyth, B.: Attacking and fixing Helios: An analysis of ballot secrecy. Journal of Computer Security 21(1), 89–148 (2013)
Delaune, S., Kremer, S., Ryan, M.D.: Verifying privacy-type properties of electronic voting protocols. Journal of Computer Security 17(4), 435–487 (2009)
Bernhard, D., Cortier, V., Pereira, O., Smyth, B., Warinschi, B.: Adapting Helios for provable ballot privacy. In: Atluri, V., Diaz, C. (eds.) ESORICS 2011. LNCS, vol. 6879, pp. 335–354. Springer, Heidelberg (2011)
Bernhard, D., Pereira, O., Warinschi, B.: On Necessary and Sufficient Conditions for Private Ballot Submission. Cryptology ePrint Archive, Report 2012/236 (version 20120430:154117b) (2012)
Bernhard, D., Pereira, O., Warinschi, B.: How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 626–643. Springer, Heidelberg (2012)
Gennaro, R.: Achieving independence efficiently and securely. In: PODC 1995: 14th Principles of Distributed Computing Symposium, pp. 130–136. ACM Press (1995)
Smyth, B., Cortier, V.: A note on replay attacks that violate privacy in electronic voting schemes. Technical Report RR-7643, INRIA (June 2011) http://hal.inria.fr/inria-00599182/
Cortier, V., Smyth, B.: Attacking and fixing Helios: An analysis of ballot secrecy. In: CSF 2011: 24th Computer Security Foundations Symposium, pp. 297–311. IEEE Computer Society (2011)
Schneier, B.: Hacking the Papal Election (2013), https://www.schneier.com/blog/archives/2013/02/hacking_the_pap.html
Bulens, P., Giry, D., Pereira, O.: Running Mixnet-Based Elections with Helios. In: EVT/WOTE 2011: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections. USENIX Association (2011)
Adida, B.: Helios: Web-based Open-Audit Voting. In: USENIX Security 2008: 17th USENIX Security Symposium, pp. 335–348. USENIX Association (2008)
Adida, B., Marneffe, O., Pereira, O., Quisquater, J.: Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios. In: EVT/WOTE 2009: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections. USENIX Association (2009)
Desmedt, Y., Chaidos, P.: Applying Divertibility to Blind Ballot Copying in the Helios Internet Voting System. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 433–450. Springer, Heidelberg (2012)
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults. In: FOCS 1985: 26th Foundations of Computer Science Symposium, pp. 383–395. IEEE Computer Society (1985)
Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. In: STOC 1991: 23rd Theory of Computing Symposium, pp. 542–552. ACM Press (1991)
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations Among Notions of Security for Public-Key Encryption Schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable Cryptography. Journal on Computing 30(2), 391–437 (2000)
Bellare, M., Sahai, A.: Non-malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 519–536. Springer, Heidelberg (1999)
Chase, M., Kohlweiss, M., Lysyanskaya, A., Meiklejohn, S.: Malleable Proof Systems and Applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 281–300. Springer, Heidelberg (2012)
Smyth, B., Cortier, V.: Does Helios ensure ballot secrecy? Cryptology ePrint Archive, Report 2010/625 (version 20101217:132825) (2010)
Chaidos, P.: Private email communication (March/April 2013)
Benaloh, J., Yung, M.: Distributing the Power of a Government to Enhance the Privacy of Voters. In: PODC 1986: 5th Principles of Distributed Computing Symposium, pp. 52–62. ACM Press (1986)
Hevia, A., Kiwi, M.: Electronic Jury Voting Protocols. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 415–429. Springer, Heidelberg (2002)
Hevia, A., Kiwi, M.A.: Electronic jury voting protocols. Theoretical Computer Science 321(1), 73–94 (2004)
Desmedt, Y., Kurosawa, K.: Electronic Voting: Starting Over? In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 329–343. Springer, Heidelberg (2005)
Pedersen, T.P.: A Threshold Cryptosystem without a Trusted Party. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 522–526. Springer, Heidelberg (1991)
Chaum, D., Pedersen, T.P.: Wallet Databases with Observers. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 89–105. Springer, Heidelberg (1993)
Chaum, D., Evertse, J.-H., van de Graaf, J., Peralta, R.: Demonstrating Possession of a Discrete Logarithm Without Revealing It. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 200–212. Springer, Heidelberg (1987)
Chaum, D., Evertse, J.-H., van de Graaf, J.: An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 127–141. Springer, Heidelberg (1988)
Schnorr, C.-P.: Efficient Identification and Signatures for Smart Cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)
Naor, M., Yung, M.: Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In: STOC 1990: 22nd Theory of Computing Symposium, pp. 427–437. ACM Press (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smyth, B., Bernhard, D. (2013). Ballot Secrecy and Ballot Independence Coincide. In: Crampton, J., Jajodia, S., Mayes, K. (eds) Computer Security – ESORICS 2013. ESORICS 2013. Lecture Notes in Computer Science, vol 8134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40203-6_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-40203-6_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40202-9
Online ISBN: 978-3-642-40203-6
eBook Packages: Computer ScienceComputer Science (R0)