Check out the new USENIX Web site.

next up previous
Next: Incorrect bids Up: A scalable secret-bid second-price Previous: A scalable secret-bid second-price

Bid submission

Each bidder selects a bid tex2html_wrap_inline1024 which is represented in some fixed base c as tex2html_wrap_inline1028 (where tex2html_wrap_inline1030 ). This base c representation of the bid is then encoded with d ordered sets of tex2html_wrap_inline1036 secret-sharing polynomials, each of which has degree tex2html_wrap_inline1038 . Each set of polynomials encodes one of the digits in a unary style as follows: Let tex2html_wrap_inline1040 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 tex2html_wrap_inline1044 . The remaining c-z polynomials are chosen with their free coefficients set to 0. We refer to the tex2html_wrap_inline1048 polynomial of the set which encodes the tex2html_wrap_inline1050 digit of the tex2html_wrap_inline1052 bidder as tex2html_wrap_inline1054 . We refer to the evaluation of this polynomial at the point controlled by the tex2html_wrap_inline1056 auctioneer as tex2html_wrap_inline1058 .

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 tex2html_wrap_inline1060 be the string

displaymath1062

The bid submission messages are of the form

displaymath1064

Note that we are ignoring lower level details such as message identifiers. tex2html_wrap_inline1066 and tex2html_wrap_inline1068 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.





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