A secure and private clarke tax voting protocol without trusted authorities

ABSTRACT

Electronic voting has become one of the most popular activities over the Internet. Security and privacy are always regarded as crucial factors in electronic voting system design. Various secure voting schemes have been proposed in the past several years to ensure the safe operation of electronic voting and most of them have focused on the common "one man, one vote" plurality voting. In this paper, we study on the security and privacy issues in the Clarke tax voting protocol, another important social choice protocol. This protocol is important in electronic voting, especially software agent based voting, because a voter's dominant strategy is truth-telling, and consequently the overhead for counterspeculation is minimized. For the very same reason, it is essential to achieve the security and the privacy protection of voters so that voters' preferences need not be made known to the public, should this protocol be practical and popular. In this paper, we first present several cryptographic building blocks, including ElGamal cryptosystem, player-resolved distributed ElGamal decryption, proof of knowledge of 1-of-k plaintext and player-resolved mix network. Then we propose a secure Clarke tax voting protocol making use of these techniques. In the proposed protocol, we achieve privacy protection, universal verifiability as well as other security requirements, such as secrecy, eligibility, completeness, etc. One important feature of the proposed protocol is that the full privacy protection of voters is guaranteed, which means that all information in voting are kept secret even in the presence of any collusion of participants involved in the voting. The only information known publicly is the final voting result, i.e., the winning candidate and the tax for each voter.

REFERENCES

• 1: Clarke, E. H. "Multipart pricing of public goods", Public Choice 11, pp. 17--33, 1971.
• 2: Clarke, E. H. "Multipart Pricing of public goods: An example", Public Price for Public Products, Urban Inst., Washington, 1972.
• 3: 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
• 4: R. Cramer, R. Gennaro, and B. Schoenmakers, "A secure and optimally efficient multi-authority election schemes", In Advance in cryptology - Eurocrypt'97, Vol 1233, LNCS, Springer-Verlag, pp. 103--118, 1997.
• 5: Ephrati, Eithan and Rosenschein, Jeffery S. "Voting and multi-agent consensus", Technical report, Computer Science Department, Hebrew University, Jerusalem, Israel, 1991.
• 6: Chaum, D., "Blind signatures for untraceable payments", Advances in Cryptology-CRYPTO'82 Proceedings, pp. 199--203, Plenum Press, 1983.
• 7: M. Abe, "Universally verifiable mix-net with verification work independent of the number of mix-servers", In Advances in Cryptology-Eurocrypt'98, Vol. 1403, LNCS, Springer-Verlag, pp. 437--447, 1998.
• 8: M. Stadler, "Publicly verifiable secret sharing", In Advances in Cryptology-Eurocrypt'96, Vol. 1070, LNCS, Springer-Verlag, pp. 190--199, 1996.
• 9: E. Fujisaki and T. Okamoto, "A practical and provably secure scheme for publicly verifiable secret sharing and its application", In Advances in Cryptology-Eurocrypt'98, Vol 1403, LNCS, Springer-Verlag, pp. 32--46, 1998.
• 10: 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
• 11: R. Crammer, M. Franklin, B. Schoenmakers and M. Yung, "Multi-authority secret ballot elections with linear work", In advance in cryptology-Eurocrypt'96, Vol.1070, LNCS, Springer-Verlag, pp.72--83, 1996.
• 12: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 13: Kazue Sako , Joe Kilian, Secure Voting Using Partially Compatible Homomorphisms, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.411-424, August 21-25, 1994
• 14: Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of CRYPTO 84 on Advances in cryptology, p.10-18, August 1985, Santa Barbara, California, United States
• 15: Wang, C. J. and Leung, H. F., "Secure Double Auction Protocols with Full Privacy Protection". In: Proceedings of the 6th Annual International Conference on Information Security and Cryptography, LNCS, Springer-Verlag, 2003.
• 16: Schnorr, C. P.: Efficient signature generation by smart cards. Journal of Cryptology, 4, pp 161--174, 1991.
• 17: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 18: 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
• 19: 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]
• 20: 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
• 21: Park, C., Itoh, K. and Kurosawa, K. "All/nothing election scheme and anonymous channel", EUROCRYPT'93, Vol. 921, LNCS, Springer-Verlag, 1993.
• 22: Sako, K, and Kilian, J. "Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth.", EUROCRYPT'95, Vol. 921, LNCS, Spinger-Verlag, 1993.
• 23: Jakobsson Markus , Juels Ari, Millimix: Mixing in Small Batches, Certer for Discrete Mathematics & Theoretical Computer Science, 1999
• 24: 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
• 25: Groves, T., "Incentives in Teams", Econometrica, 41:617--631, 1973.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Economics, Security, Theory

Keywords:
Clarke tax voting protocol, ElGamal encryption, electronic voting, mix network, privacy protection, security, universal verification