Coercion-resistant electronic elections

ABSTRACT

We introduce a model for electronic election schemes that involves a more powerful adversary than previous work. In particular, we allow the adversary to demand of coerced voters that they vote in a particular manner, abstain from voting, or even disclose their secret keys. We define a scheme to be coercion-resistant if it is infeasible for the adversary to determine if a coerced voter complies with the demands.A first contribution of this paper is to describe and characterize a new and strengthened adversary for coercion in elections. (In doing so, we additionally present what we believe to be the first formal security definitions for electronic elections of any type.) A second contribution is to demonstrate a protocol that is secure against this adversary. While it is clear that a strengthening of attack models is of theoretical relevance, it is important to note that our results lie close to practicality. This is true both in that we model real-life threats (such as vote-buying and vote-canceling), and in that our proposed protocol combines a fair degree of efficiency with an unusual lack of structural complexity. Furthermore, previous schemes have required use of an untappable channel throughout. Ours only carries the much more practical requirement of an anonymous channel during the casting of ballots, and an untappable channel during registration (potentially using postal mail).This extended abstract is a heavily truncated version of the full paper available at http://eprint.iacr.org/2002/165.

REFERENCES

• 1: Proxyvote.com: Shareholder election website, 2005. URL: www.proxyvote.com.
• 2: Vote-auction, 2005. URL: www.vote-auction.net.
• 3: Olivier Baudron , Pierre-Alain Fouque , David Pointcheval , Jacques Stern , Guillaume Poupard, Practical multi-candidate election system, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.274-283, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384044]
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195407]
• 6: Manuel Blum , Alfredo De Santis , Silvio Micali , Giuseppe Persiano, Noninteractive zero-knowledge, SIAM Journal on Computing, v.20 n.6, p.1084-1118, Dec. 1991 [doi>10.1137/0220068]
• 7: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 8: Dan Boneh , Philippe Golle, Almost entirely correct mixing with applications to voting, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586121]
• 9: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 10: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 11: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 12: Ran Canetti , Cynthia Dwork , Moni Naor , Rafail Ostrovsky, Deniable Encryption, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.90-104, August 17-21, 1997
• 13: Ran Canetti , Rosario Gennaro , Stanislaw Jarecki , Hugo Krawczyk , Tal Rabin, Adaptive Security for Threshold Cryptosystems, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.98-115, August 15-19, 1999
• 14: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 15: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 16: R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In W. Fumy, editor, EUROCRYPT '97, pages 103--118. Springer-Verlag, 1997. LNCS no. 1233.
• 17: Ronald Cramer , Victor Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.13-25, August 23-27, 1998
• 18: M. Cross. Public domain. The Guardian: Guardian Unlimited Online, 10 June 2004.
• 19: J. Fowler. Switzerland tests virtual democracy in national referendum. Technology Review, 26 September 2004.
• 20: Atsushi Fujioka , Tatsuaki Okamoto , Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.244-251, December 13-16, 1992
• 21: J. Furukawa. Efficient, verifiable shuffle decryption and its requirement of unlinkability. In B. et al., editor, PKC '04, pages 319--332. Springer-Verlag, 2004. LNCS no. 2947.
• 22: Jun Furukawa , Kazue Sako, An Efficient Scheme for Proving a Shuffle, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.368-387, August 19-23, 2001
• 23: T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469--472, 1985.
• 24: R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. The (in)security of distributed key generation in dlog-based cryptosystems. In J. Stern, editor, EUROCRYPT '99, pages 295--310. Springer-Verlag, 1999. LNCS no. 1592.
• 25: M. Hirt and K. Sako. Efficient receipt-free voting based on homomorphic encryption. In B. Preneel, editor, EUROCRYPT '00, pages 539--556, 2000. LNCS no. 1807.
• 26: Markus Jakobsson , Ari Juels, Mix and Match: Secure Function Evaluation via Ciphertexts, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.162-177, December 03-07, 2000
• 27: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 28: M. Jakobsson, K. Sako, and R. Impagliazzo. Designated verifier proofs and their applications. In U. Maurer, editor, EUROCRYPT '96, pages 143--154. Springer-Verlag, 1996. LNCS no. 1070.
• 29: A. Juels and J. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Proceedings of the 1999 ISOC Network and Distributed System Security Symposium, pages 151--165, 1999.
• 30: Aggelos Kiayias , Moti Yung, Self-tallying Elections and Perfect Ballot Secrecy, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.141-158, February 12-14, 2002
• 31: Philip D. MacKenzie , Thomas Shrimpton , Markus Jakobsson, Threshold Password-Authenticated Key Exchange, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.385-400, August 18-22, 2002
• 32: Emmanouil Magkos , Mike Burmester , Vassilios Chrissikopoulos, Receipt-Freeness in Large-Scale Elections without Untappable Channels, Proceedings of the IFIP Conference on Towards The E-Society: E-Commerce, E-Business, E-Government, p.683-694, October 03-05, 2001
• 33: Markus Michels , Patrick Horster, Some Remarks on a Receipt-Free and Universally Verifiable Mix-Type Voting Scheme, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.125-132, November 03-07, 1996
• 34: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 35: Valtteri Niemi , Ari Renvall, How to Prevent Buying of Votes in Computer Elections, Proceedings of the 4th International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.164-170, November 28-December 01, 1994
• 36: T. Okamoto. An electronic voting scheme. In N. T. et al., editor, IFIP World Congress, pages 21--30, 1996.
• 37: Tatsuaki Okamoto, Receipt-Free Electronic Voting Schemes for Large Scale Elections, Proceedings of the 5th International Workshop on Security Protocols, p.25-35, April 07-09, 1997
• 38: S. Parker. Shaking voter apathy up with IT. The Guardian, 11 Dec. 2001.
• 39: K. Sako and J. Kilian. Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth. In L. Guillou and J.-J. Quisquater, editors, EUROCRYPT '95, pages 393--403. Springer-Verlag, 1995. LNCS no. 921.
• 40: Berry Schoenmakers, A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.148-164, August 15-19, 1999
• 41: B. Schoenmakers, 2000. Personal communication.
• 42: Yiannis Tsiounis , Moti Yung, On the Security of ElGamal Based Encryption, Proceedings of the First International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.117-134, February 05-06, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
coercion-resistance, electronic voting, mix networks, receipt-freeness