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:
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.