Decentralized voting with unconditional privacy

ABSTRACT

The aggregation of conflicting preferences is a key issue in multiagent systems. Due to its universality, voting has a central role among preference aggregation mechanisms. Voting among a set of alternatives can be used for such diverse tasks as choosing a joint plan in a multiagent system, determining a leader in a group of humans or agents, or voting among different resource or task allocations. Maintaining privacy of individuals' votes is crucial in order to guarantee freedom of choice (e.g., lack of vote coercing and reputation effects), and not facilitate strategic voting. We investigate whether unconditional full privacy can be achieved in voting, that is, privacy that relies neither on trusted third parties (or on a certain fraction of the voters being trusted), nor on computational intractability assumptions (such as the hardness of factoring). In particular, we study the existence of distributed protocols that allow voters to jointly determine the outcome of an election without revealing any information but the election outcome. We show the impossibility of reaching unconditional full privacy for a variety of the most common voting schemes ranging from simple veto voting to the single transferable vote scheme. On the positive side, we propose several distributed protocols that privately compute the outcome of common voting schemes while only revealing a limited amount of information.

REFERENCES

• 1: K. Arrow. Social choice and individual values. New Haven: Cowles Foundation, 2nd edition, 1963. 1st edition 1951.
• 2: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 3: Josh Cohen Benaloh, Secret sharing homomorphisms: keeping shares of a secret secret, Proceedings on Advances in cryptology---CRYPTO '86, p.251-260, January 1987, Santa Barbara, California, United States
• 4: Felix Brandt , Tuomas Sandholm, (Im)Possibility of Unconditionally Privacy-Preserving Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.810-817, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.1]
• 5: Felix Brandt , Tuomas Sandholm, Unconditional privacy in social choice, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
• 6: D. Chaum, Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.177-182, April 1988, Davos, Switzerland
• 7: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 8: B. Chor, M. Geréb-Graus, and E. Kushilevitz. On the structure of the privacy hierarchy. Journal of Cryptology, 7(1):53--60, 1994.
• 9: B. Chor , E. Kushilevitz, A zero-one law for Boolean privacy, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.62-72, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73013]
• 10: Vincent Conitzer , Tuomas Sandholm, Vote elicitation: complexity and strategy-proofness, Eighteenth national conference on Artificial intelligence, p.392-397, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 11: V. Conitzer and T. Sandholm. Universal voting protocol tweaks to make manipulation hard. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), pages 781--788, 2003.
• 12: Vincent Conitzer , Tuomas Sandholm, Communication complexity of common voting rules, Proceedings of the 6th ACM conference on Electronic commerce, p.78-87, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064018]
• 13: R. Cramer, R. Gennaro, and B. Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Advances in Cryptology - Proceedings of the 14th Eurocrypt Conference, volume 1233 of Lecture Notes in Computer Science (LNCS), pages 103--118. Springer, 1997.
• 14: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644--654, 1976.
• 15: Eithan Ephrati , Jeffrey S. Rosenschein, Deriving consensus in multiagent systems, Artificial Intelligence, v.87 n.1-2, p.21-74, Nov. 1996 [doi>10.1016/0004-3702(95)00105-0]
• 16: A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.
• 17: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 18: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 19: 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
• 20: D. E. Knuth and R. W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, 6(4):293--326, 1975.
• 21: E. Kushilevitz. Privacy and communication complexity. In Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), pages 416--421. IEEE Computer Society Press, 1989.
• 22: K. May. A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica, 20:680--684, 1952.
• 23: Jeffrey Shneidman , David C. Parkes, Using redundancy to improve robustness of distributed mechanism implementations, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779997]
• 24: David C. Parkes , Jeffrey Shneidman, Distributed Implementations of Vickrey-Clarke-Groves Mechanisms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.261-268, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.108]
• 25: David M. Pennock , Eric Horvitz , C. Lee Giles, Social Choice Theory and Recommender Systems: Analysis of the Axiomatic Foundations of Collaborative Filtering, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.729-734, July 30-August 03, 2000
• 26: B. Pfitzmann and M. Waidner. Unconditionally untraceable and fault-tolerant broadcast and secret ballot election. Hildesheimer Informatik-Berichte, Institut für Informatik, Universität Hildesheim, 1992.
• 27: M. A. Satterthwaite. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Security, Theory

Keywords:
multiparty computation, voting protocols