A secure voter-resolved approval voting protocol over internet

ABSTRACT

Electronic online voting has become one of the most popular activities over Internet recently, since it can be performed in a way that is more convenient, faster and cheaper. Security and privacy are always regarded as crucial factors in electronic voting system design. Extensive studies have been made on the electronic voting in the last twenty years, and many schemes have been proposed, in which both the security as well as the effectiveness have been improved. However, most available secure vote schemes mainly focused on the simple "one-man-one-vote" plurality protocol. In this paper, we address the security issues in Approval voting protocol, another important social decision protocol, in which voters can vote for, or approval of, as many candidates as they wish in multi-candidate elections. By employing several cryptographic primitives, such as, homomorphic encryption, mix network, etc., we propose a voter-resolved secure Approval voting scheme over Internet which guarantees the complete privacy protection of the voters as well as the universal verifiability. The "voter-resolved" means that we do not assume the existence of any trusted or semi-trusted authorities in our scheme, instead, we employ the homomorphic ElGamal encryption and distribute the private key among the all voters to achieve complete privacy protection of voters. In such a way, all voters jointly compute the outcome of the election without revealing any further information of voters' individual preferences. An analysis of the protocol against the security requirements shows that the proposed protocol achieves complete privacy protection, public verifiability, weak robustness, in addition to others addressed by other protocols in the available literature.

REFERENCES

• 1: Brams, Steven J. and Peter C. Fishburn. 1983. Approval Voting. Birkhauser-Boston.
• 2: K. J. Arrow, Social Choice and Individual Values, 2nd edition. New York: Wiley. 1963.
• 3: Brams, Steven J. and Peter C. Fishburn. 1978. "Approval Voting." American Political Science Review. 72:113--134.
• 4: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, 1987
• 5: 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
• 6: R. Cramer, M. Franklin, B. Schoenmakers, and M. Yung, "Multi-authority secret ballot elections with linear work", In Advances in Cryptology-Eurocrypt'96, Vol. 1070, LNCS, Springer-Verlag, pp. 72--83, 1996.
• 7: R. Cramer, R. Gennaro, and B. Schoenmakers, "A secure an optimally efficient multi-authority election schemes", In Advances in Cryptology-Eurocrypt'97, Vol 1233, LNCS, Springer-Verlag, pp. 103--118, 1997.
• 8: B. Pfitzmann, "Breaking an efficient anonymous channel", In Advances in Cryptology-Eurocrypt'94, Vol. 950, LNCS, Springer-Verlag, pp. 332--340, 1994.
• 9: K. Sako and j. Kilian, "Receipt-free mix-type voting scheme - a practical solution to the implementation of a voting booth", In Advances in Cryptology-Eurocrypt'95, Vol. 921, LNCS, Springer-Verlag, pp. 393--403, 1995.
• 10: 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
• 11: 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.
• 12: M. Jakobsson, "A practical mix", In Advances in Cryptology-Eurocrypt'98, LNCS Vol. 1403, Springer-Verlag, pp.449--461, 1998.
• 13: M. Stadler, "Publicly verifiable secret sharing", In Advances in Cryptology-Eurocrypt'96, Vol. 1070, LNCS, Springer-Verlag, pp. 190--199, 1996.
• 14: 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.
• 15: 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
• 16: 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
• 17: 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.
• 18: Schnorr, C. P.: Efficient signature generation by smart cards. Journal of Cryptology, 4, pp 161--174, 1991.
• 19: 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
• 20: Masayuki Abe, Mix-Networks on Permutation Networks, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.258-273, November 14-18, 1999
• 21: 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
• 22: 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]
• 23: B. Lee, and K. Kim, "Receipt-free electronic voting through collaboration of voter and honest verifier", Proceeding of JW-ISC2000, pp. 101--108, Jan. 25-- 26, 2000, Okinawa, Japan.
• 24: Steven J. Brams, "Approval Voting and the Good Society", in Policical Economy of the Good Society, Newsletter 3, No. 1, 1993, pp. 10--14.
• 25: Chaum, D., "Blind signatures for untraceable payments", Advances in Cryptology-CRYPTO'82 Proceedings, pp199--203, Plenum Press, 1983.
• 26: M. Stadler, "Publicly verifiable secret sharing", In Advances in Cryptology-Eurocrypt'96, Vol. 1070, LNCS, Springer-Verlag, pp. 190--199, 1996.
• 27: 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
• 28: Changjie Wang , Ho-fung Leung, A secure and private clarke tax voting protocol without trusted authorities, Proceedings of the 6th international conference on Electronic commerce, October 25-27, 2004, Delft, The Netherlands [doi>10.1145/1052220.1052290]
• 29: F. Brandt. "Fully private auctions in a constant number of rounds", In Proceedings of the 7th Annual Conference on Financial Cryptography (FC), Springer-Verlag LNCS 2742, pP 223--238, 2003.
• 30: F. Brandt. "A verifiable, bidder-resolved auction protocol", In Proceedings of the 5th AAMAS Workshop on Deception, Fraud and Trust in Agent Societies (Special Track on Privacy and Protection with Multi-Agent Systems), pages 18--25, 2002.

INDEX TERMS

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

General Terms:
Economics, Security, Theory, Verification

Keywords:
ElGamal encryption, approval voting, electronic voting, privacy protection, security, universal verification, voter-resolved