Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions

ABSTRACT

This paper presents a secure dynamic programming protocol that utilizes homomorphic encryption. By using this method, multiple agents can solve a combinatorial optimization problem among them without leaking their private information. More specifically, in this method, multiple servers cooperatively perform dynamic programming procedures for solving a combinatorial optimization problem by using the private information sent from agents as inputs. Although the severs can compute the optimal solution correctly, the inputs are kept secret even from the servers.Such a secure protocol is important when a fully trusted agent is not available, e.g., an auctioneer cannot be fully trusted in a combinatorial auction. By utilizing the proposed protocol, multiple auction servers can solve the winner determination problem, while the information of bids that are not part of the optimal solution is kept secret even from the auction servers. We discuss the application of this protocol to various types of combinatorial auctions, i.e., multi-unit auctions, linear-good auctions, and general combinatorial auctions.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 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: T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory, IT-31(4):469--472, 1985.
• 4: Matthew K. Franklin , Michael K. Reiter, The Design and Implementation of a Secure Auction Service, IEEE Transactions on Software Engineering, v.22 n.5, p.302-312, May 1996 [doi>10.1109/32.502223 ]
• 5: Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
• 6: 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]
• 7: Hiroaki Kikuchi, (M+1)st-Price Auction Protocol, Proceedings of the 5th International Conference on Financial Cryptography, p.351-363, February 19-22, 2002
• 8: Tomomi Matsui , Takahiro Watanabe, Sealed Bid Mulit-object Auctions with Necessary Bundles and Its Application to Spectrum Auctions, Proceedings of the 4th Pacific Rim International Workshop on Multi-Agents, Intelligent Agents: Specification, Modeling, and Applications, p.78-92, July 28-29, 2001
• 9: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 10: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. Proceedings of EUROCRYPT '99, pages 223--238, 1999.
• 11: T. Pedersen. A threshold cryptosystem without a trusted party. Proceedings of EUROCRYPT '91, pages 522--526, 1991. Lecture Notes in Computer Science 547.
• 12: E. Rasmusen. Games and Information. Blackwell, 1994.
• 13: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998
• 14: Yuko Sakurai , Makoto Yokoo , Koji Kamei, An efficient approximate algorithm for winner determination in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.30-37, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352875]
• 15: Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
• 16: T. Sandholm, S. Suri, A. Gilpin, and D. Levine. CABOB: A fast combinatorial algorithm for optimal combinatorial auctions. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-2001), pages 1102--1108, 2001.
• 17: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 18: M. Stadler. Publicly verifiable secret sharing. Proceedings of EUROCRYPT '96, pages 190--199, 1996. Lecture Notes in Computer Science 1070.
• 19: K. Suzuki and M. Abe. M+1-st price auction using homomorphic encryption. Technical Report ISEC 2001-11, IEICE, 2001.
• 20: K. Suzuki and M. Yokoo. Secure combinatorial auctions by dynamic programming with polynomial secret sharing. In Sixth International Financial Cryptography Conference (FC-02), 2002.
• 21: Moshe Tennenholtz, Some Tractable Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.98-103, July 30-August 03, 2000
• 22: Stan Van Hoesel , Rudolf Müller, Optimization in electronic markets: examples in combinatorial auctions, Netnomics, v.3 n.1, p.23-33, June 2001 [doi>10.1023/A:1009940607600 ]
• 23: H. R. Varian. Economic mechanism design for computerized agents. In Proceedings of the First Usenix Workshop on Electronic Commerce, 1995.
• 24: A. C. Yao. How to generate and exchange secrets. In Proceedings of IEEE Symposium on Foundations of Computer Science, pages 162--167, 1986.
• 25: Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids., Artificial Intelligence, v.130 n.2, p.167-181, 08/01/2001 [doi>10.1016/S0004-3702(01)00077-7 ]

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

Keywords:
auction, dynamic programming, electronic commerce, privacy, public key encryption, security and agents