Check out the new USENIX Web site.

next up previous
Next: Bid resolution Up: Bid submission Previous: Bid submission

Incorrect bids

  The selection method for the polynomials tex2html_wrap_inline1072 requires their values at 0 to be either 0 or a uniformly random selection from tex2html_wrap_inline1074 . This property is needed to ensure a low probability of error. Since p is prime, the property may be enforced by multiplying each tex2html_wrap_inline1078 by an independent scalar value uniformly selected from tex2html_wrap_inline1080 . Since this is multiplication by scalar values, the degree of the polynomials is not altered. Including this step does not eliminate the need for an honest bidder to select her polynomials randomly as described, since a non-random selection could leak information about the bids.

If c>2, then the method of representing bids allows a bidder to submit a bid which does not correspond to a single value. This is due to the unary-style representation of the individual digits. We are unaware of any advantage that could be derived from using such malformed bids, but they could be easily prevented (if desired) as follows. After all bids are received, the auctioneers select a random number tex2html_wrap_inline1084 . The tex2html_wrap_inline1086 should then be recomputed in order of descending l by

displaymath1090

For the base case, l=c-1, the polynomial tex2html_wrap_inline1094 remains unchanged. Since r is a scalar rather than polynomial, all these computations can be performed without any communication (other than agreeing upon r).



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