Check out the new USENIX Web site.

next up previous
Next: Auctioneer accountability Up: Accountability Previous: Deposits

Bidder accountability

  The signature on the bid submission enables the auctioneers to prove the validity of a bid even if the majority of the auctioneers are not trusted. In the non-anonymous case, a well-known public key for the bidder should be used. In the anonymous case, the asymmetric key should be registered with some escrow agency or cryptographically linked to a deposit. Whatever key is used, the meaning of ``bidder'' in the following discussion is simply the entity which can generate signatures with the correct key. In all cases, the auctioneers must be able to prove that the bidder (by means of her asymmetric key) placed a bid at least as high as the selling price.

The simplest means of resolving a dispute is for the auctioneers to send all components to a trusted authority. The accuracy of the components can be verified by the signatures, and then the precise bid can be determined. The drawback of this method of resolution is that the authority will learn the exact value of the bid. However, for the auctioneers to inaccurately determine a winner, there must be a coalition of auctioneers large enough to determine the bid themselves, each member of which is corrupt or faulty. So the bid may already be known to the corrupt auctioneers.

Another method for resolving such a dispute is to perform a greatly simplified version of the auction. This simplified auction may be performed as a check by the auctioneers, to ensure that the winner was not selected incorrectly. Additionally, the shares possessed by the auctioneers (signed by the bidder) may be transferred to some other distributed authority, which will perform the check to resolve disputes. This simplified auction is performed with 3 bids: the disputed ``winning'' bid and two known bids tex2html_wrap_inline1922 and tex2html_wrap_inline1924 (where tex2html_wrap_inline1926 is the selling price determined by the disputed auction). If this auction returns a selling price of tex2html_wrap_inline1928 , then the auction was correct; if it returns a selling price of tex2html_wrap_inline1930 , it was incorrect. The result of the auction is always tex2html_wrap_inline1932 or tex2html_wrap_inline1934 and thus reveals no information other than whether the questioned bid is less than tex2html_wrap_inline1936 .



next up previous
Next: Auctioneer accountability Up: Accountability Previous: Deposits



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