Name
Title | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/544741.544770 | AAMAS |
Keywords | Field | DocType |
homomorphic encryption,combinatorial optimization problem,optimal solution,linear-good auction,proposed protocol,secure protocol,secure multi-agent dynamic programming,auction server,combinatorial auction,private information,general combinatorial auction,secure dynamic programming protocol,dynamic programming,public key encryption,electronic commerce,security protocol,privacy | Homomorphic encryption,Dynamic programming,Computer science,Combinatorial auction,Server,Theoretical computer science,Common value auction,Private information retrieval,Public-key cryptography,Auction algorithm,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-480-0 | 46 | 1.95 |
References | Authors | |
16 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Makoto Yokoo | 1 | 3632 | 421.99 |
| Koutarou Suzuki | 2 | 518 | 29.57 |