A simple auction method

First, we will briefly describe a simple first-price auction protocol with private bids which captures some of the flavor of the more complex version to follow. We assume that all bids are drawn from some ordered set , and that there are n bidders and m auctioneers. We also fix a sufficiently large (64-128 bit) prime number p. All arithmetic will be computed modulo p. Each bidder composes her bid by creating V lists of m integers modulo p. The rule for creating these sets is that:

• If the bidder is willing to pay for the object, then the list of numbers is chosen randomly with uniform distribution subject to the constraint that the sum (modulo p) of all numbers must be non-zero.
• If the bidder is unwilling to pay for the object, then the list of numbers is chosen randomly with uniform distribution subject to the constraint that the sum (modulo p) of all numbers must be zero.

Each auctioneer is sent V numbers by each bidder; the auctioneer is sent the number from each list. The submissions are signed by the bidders, and signed receipts are issued by the auctioneers. The signature by the bidder should be a signature on a hash of hashes of each of the individual values in the list so that the signature can be used to prove a bid at one particular value without revealing the bids at any other values. Strange or non-random bidding behaviors are possible (e.g. being willing to pay but not for i<j). Such inconsistencies could be easily eliminated by methods similar to those outlined in section 4.1.1.

To determine the winning bid, the auctioneers compute, for each , the sum of the m (one from each bidder) numbers received for that . To determine whether a particular is above or below the winning bid, the auctioneers commit to and reveal their sums for that , and then compute a sum of all these values (which is equal to the sum of all numbers from all bidders for ). The sum of all values for a particular is non-zero (with high probability) exactly when at least one bidder is willing to pay . The auctioneers find the highest l for which some bidder is willing to pay , possibly in several stages with a branching search for the highest bid. Once the highest bid is known, the auctioneers can then use the signatures on the bid submissions to prove which bidder is the winner by reassembling all bids for that winning .

This auction has some weaknesses. Most significantly, a coalition of an auctioneer and the highest bidder might uncover some information about the second highest bid. This information would be leaked by the fact that, for all l lower than the highest bid but higher than the second highest bid, the total of all bids would be simply the bid of the highest bidder. The obvious way to avoid revealing these intermediate sums would be to reveal sums one at a time from down and would require a number of rounds linear in the number of bidding points, which is likely to be unacceptably slow. Another weakness is that the work required (both computation and communication) scales linearly with the number of bidding points. For high value auctions, the desirable number of bidding points might be quite large.

We will give an auction in which the work scales only logarithmically with the number of bidding points, which provides complete privacy, and which allows for second-price auctions. It is worth noting that these alterations need not be combined; any subset may be implemented and computation costs will vary accordingly.