Each bidder selects a bid which is represented
in some fixed base c as
(where
). This base c representation of the bid is then encoded with d
ordered sets of
secret-sharing polynomials, each of which has degree
. Each set of polynomials encodes one
of the digits in a unary style as follows: Let
be the value of the digit to be represented by a particular set. The
first z polynomials are chosen such that their free coefficients
are uniformly randomly selected from
. The
remaining c-z polynomials are chosen with their free coefficients
set to 0. We refer to the
polynomial of the set which encodes the
digit of the
bidder as
. We refer to the
evaluation of this polynomial at the point controlled by the
auctioneer as
.
The bidders will use asymmetric keys to provide accountability and to enable the winner to claim her good. In the normal case, these keys will be the bidders' published public keys. (In the case where a bidder wishes to remain anonymous, a pseudonymous key can be used instead. Issues raised by anonymous bidders are addressed in section 4.6.4.)
Let be the string
The bid submission messages are of the form
Note that we are ignoring lower level details such as message
identifiers. and
represent signature and encryption with
an asymmetric key pair, and h is a crytographically secure hash
function. The submission is verified to be a valid polynomial
using the interactive protocol mentioned in section 3.