2002 · 99 citations · 16 references
ComputingComputer ScienceMathematicsAlgorithmsAuction TheoryGame TheoryCombinatorial AuctionsCryptographic AlgorithmsDynamic AuctionsDynamic ProgrammingHomomorphic EncryptionMulti-agent SystemsCombinatorial Dynamic AuctionsFully Homomorphic EncryptionMulti-party Homomorphic ComputationPartially Homomorphic Encryption
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.
16
Adi Shamir · Communications of the ACM · 1979 · 13.5K citations · Full text
How to generate and exchange secrets
Andrew Chi-Chih Yao · 1986 · 3.7K citations
Oded Goldreich, Silvio Micali, Avi Wigderson · 1987 · 3.5K citations