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 (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
is very unlikely to be
zero (i.e. that
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
be the point held by the
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.