Secure Auctions with Rational Parties

Abstract

Sealed bid auctions are used to allocate a resource among a set of interested parties. Traditionally, auctions need the presence of a trusted auctioneer to whom the bidders provide their private bid values. Existence of such a trusted party is not an assumption easily realized in practice. Generic secure computation protocols can be used to remove a trusted party. However, generic techniques result in inefficient protocols and typically do not provide fairness -- that is, a corrupt party can learn the output and abort the protocol, thereby preventing other parties from learning the output. In our work, we construct concretely efficient and provably secure protocol for First Price Auctions (FPA) in the rational setting. Bidders in these auctions are modelled as self-interested agents who care more about maximizing their utility than about learning information about the bids of other parties. Our protocol guarantees privacy, public verifiability, and fairness. We introduce a novel way to handle collusion by suitably disincentivizing the bidders from forming collusion. We also put forth a new solution concept that we call Privacy Preserving Computational Dominant Strategy Equilibrium that captures parties' privacy and monetary concerns in the game theoretic context and show that our protocol realizes this. We believe this notion to be of independent interest, which can be used in a general rational security setting. Subsequently, we improve these auction protocols such that they use 50\% less communication and run 2X faster. In order to realize this, we introduce a new cryptographic primitive called Uni-OT, which is our main technical tool in constructing the auction protocols. At a high level, Uni-OT is a two-party functionality with the sender having a single message and the receiver getting the message only if its choice bit is 0; and the sender is oblivious to whether the receiver chose to obtain the message or not. We provide generic constructions of Uni-OT. We believe that Uni-OT will have applications in building efficient secure computation protocols.