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.