Check out the new USENIX Web site.

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

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 tex2html_wrap_inline830 , 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:

Each auctioneer is sent V numbers by each bidder; the tex2html_wrap_inline860 auctioneer is sent the tex2html_wrap_inline862 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 tex2html_wrap_inline864 but not tex2html_wrap_inline866 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 tex2html_wrap_inline870 , the sum of the m (one from each bidder) numbers received for that tex2html_wrap_inline874 . To determine whether a particular tex2html_wrap_inline876 is above or below the winning bid, the auctioneers commit to and reveal their sums for that tex2html_wrap_inline878 , and then compute a sum of all these values (which is equal to the sum of all numbers from all bidders for tex2html_wrap_inline880 ). The sum of all values for a particular tex2html_wrap_inline882 is non-zero (with high probability) exactly when at least one bidder is willing to pay tex2html_wrap_inline884 . The auctioneers find the highest l for which some bidder is willing to pay tex2html_wrap_inline888 , 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 tex2html_wrap_inline890 .

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



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



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