Check out the new USENIX Web site.

next up previous
Next: Bid submission Up: Electronic Auctions with Private Previous: Secure distributed computation

A scalable secret-bid second-price auction

We describe a second-price sealed-bid auction protocol which has the potential to be t-private and t-resilient, and which is efficient enough for use in large auctions. All polynomials used during the protocol are secret sharing polynomials from tex2html_wrap_inline1000 (the set of polynomials over the field of integers less than a prime p). The prime p should be chosen to support the assumption that the sum of several random non-zero elements from tex2html_wrap_inline1006 is very unlikely to be zero (i.e. that tex2html_wrap_inline1008 is very small). They are stored in a point-value representation, with each of the m auctioneers (who are indexed by i) holding the value at one point. Let tex2html_wrap_inline1014 be the point held by the tex2html_wrap_inline1016 auctioneer. These polynomials are manipulated by means of their evaluations at these m points.

Each of the n bidders (indexed by j) computes a set of secret sharing polynomials whose secrets encode her bid. The bidders distribute the shares of these polynomials among the auctioneers. The auctioneers then perform a multi-round computation to determine the selling price. The winning bidder is then determined by combining certain information from the auctioneers.





Doug Tygar
Wed Jul 22 10:16:16 EDT 1998