Secure computation for combinatorial auctions and market exchanges

It was recently shown possible to solve (M+1) ^st price single item auctions without revealing absolutely any secret except for the solution. Namely, with vMB-share [2], the seller and the buyer only learn each other's identity and learn the selling price for a chosen (M+1) ^st pricing scheme. No trusted party is necessary. In this paper we show how vMB-share can be extended for the clearing of combinatorial negotiation problems with several items, buyers and sellers. We first show how the more general problem can be reduced to a virtual form, form that is relatively similar to the single item auctions, by having a virtual bidder for each candidate allocation. Then, some modifications in the cryptographic techniques of vMB-share are made such that it can offer a solution to problems in virtual form. As explained in the paper, it is expected that a secure solution hiding details that can be inferred from the running time will have an exponential computation cost. Our preliminary experimental evaluation shows that some small negotiations can nevertheless be solved with acceptable effort.