Efficient Private Bidding and Auctions with an Oblivious Third Party

We describe a novel and efficient protocol for the following problem: A wants to buy some good from B if the price is less than a. B would like to sell, but only for more than b, and neither of them wants to reveal the secret bounds. Will the deal take place? Our solution uses an oblivious third party T who learns no information about a or b, not even whether a>b. The protocol needs only a single round of interaction, ensures fairness, and is not based on general circuit evaluation techniques. It uses a novel construction, which combines homomorphic encryption with the Phi-hiding assumption and which may be of independent interest. Applications include bargaining between two parties and secure and efficient auctions in the absence of a fully trusted auction service.
Keywords:
Bidding, Auctions, Homomorphic cryptosystems, Phi-Hiding assumption, Private information retrieval, Multiparty computation.