t-Private and t-Secure Auctions

In most of the auction systems the values of bids are known to theauctioneer. This allows him to manipulate the outcome of the auction.Hence, one might be interested in hiding these values. Somecryptographically secure protocols for electronic auctions have beenpresented in the last decade. Our work extends these protocols inseveral ways. On the basis of garbled circuits, i.e., encryptedcircuits, we present protocols for sealed-bid auctions that fulfill thefollowing requirements: 1) protocols are information-theoreticallyt-private for \em honest but curious parties;2) the number of bits that can be learned by \em malicious adversariesis bounded by the output length of the auction; 3) the computationalrequirements for participating parties are very low: only random bitchoices and bitwise computation of the \tt XOR-function are necessary.Note that one can distinguish between the protocol that generates agarbled circuit for an auction and the protocol to evaluate the auction.In this paper we address both problems. We will present a t-privateprotocol for the construction of a garbled circuit that reaches thelower bound of 2t+1 parties, and a more randomness efficient protocolfor (t+1)^2 parties. Finally, we address the problem of bid changes inan auction.