Next: Bid resolution
Up: Bid submission
Previous: Bid submission
The selection method for the polynomials requires their
values at 0 to be either 0 or a uniformly random selection from
. This property is needed to ensure a low
probability of error. Since p is prime, the property may be enforced
by multiplying each by an independent scalar value uniformly
selected from . 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 . The should then be recomputed in order
of descending l by
For the base case, l=c-1, the polynomial 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