Paper 2019/1332

SEAL: Sealed-Bid Auction Without Auctioneers

Samiran Bag and Feng Hao and Siamak F. Shahandashti and Indranil G. Ray

Abstract

We propose the first auctioneer-free sealed-bid auction protocol with a linear computation and communication complexity $O(c)$, $c$ being the bit length of the bid price. Our protocol, called Self-Enforcing Auction Lot (SEAL), operates in a decentralized setting, where bidders jointly compute the maximum bid while preserving the privacy of losing bids. In our protocol, we do not require any secret channels between participants. All operations are publicly verifiable; everyone including third-party observers is able to verify the integrity of the auction outcome. Upon learning the highest bid, the winner comes forward with a proof to prove that she is the real winner. Based on the proof, everyone is able to check if there is only one winner or there is a tie. While our main protocol works with the first-price sealed-bid, it can be easily extended to support the second-price sealed-bid (also known as the Vickrey auction), revealing only the winner and the second highest bid, while keeping the highest bid and all other bids secret. To the best of our knowledge, this work establishes to date the best computation and communication complexity for sealed-bid auction schemes without involving any auctioneer.

Note: Update definition 2 to make it more explicit.