TY - JOUR
T1 - On the existence of unconditionally privacy-preserving auction protocols
AU - Brandt, Felix
AU - Sandholm, Tuomas
PY - 2008/5/1
Y1 - 2008/5/1
N2 - We investigate whether it is possible to preserve privacy in sealed-bid auctions to a maximal extent. In particular, this paper focuses on unconditional full privacy, i.e., privacy that relies neither on trusted third parties (like auctioneers), nor on computational intractability assumptions (like the hardness of factoring). These constraints imply a scenario in which bidders exchange messages according to some predefined protocol in order to jointly determine the auction outcome without revealing any additional information. It turns out that the first-price sealed-bid auction can be emulated by an unconditionally fully private protocol. However, the protocol's round complexity is exponential in the bid size, and there is no more efficient protocol. On the other hand, we prove the impossibility of privately emulating the second-price sealed-bid auction for more than two bidders. This impossibility holds even when relaxing various privacy constraints such as allowing the revelation of all but one losing bid (while maintaining anonymity) or allowing the revelation of the second highest bidder's identity.
AB - We investigate whether it is possible to preserve privacy in sealed-bid auctions to a maximal extent. In particular, this paper focuses on unconditional full privacy, i.e., privacy that relies neither on trusted third parties (like auctioneers), nor on computational intractability assumptions (like the hardness of factoring). These constraints imply a scenario in which bidders exchange messages according to some predefined protocol in order to jointly determine the auction outcome without revealing any additional information. It turns out that the first-price sealed-bid auction can be emulated by an unconditionally fully private protocol. However, the protocol's round complexity is exponential in the bid size, and there is no more efficient protocol. On the other hand, we prove the impossibility of privately emulating the second-price sealed-bid auction for more than two bidders. This impossibility holds even when relaxing various privacy constraints such as allowing the revelation of all but one losing bid (while maintaining anonymity) or allowing the revelation of the second highest bidder's identity.
KW - Auctions
KW - Multiparty computation
UR - http://www.scopus.com/inward/record.url?scp=40049106703&partnerID=8YFLogxK
U2 - 10.1145/1330332.1330338
DO - 10.1145/1330332.1330338
M3 - Article
AN - SCOPUS:40049106703
SN - 1094-9224
VL - 11
JO - ACM Transactions on Information and System Security
JF - ACM Transactions on Information and System Security
IS - 2
M1 - 6
ER -