Check out the new USENIX Web site.

next up previous
Next: Efficiency Up: A scalable secret-bid second-price Previous: Breaking ties

A sample auction

We will give a simple example at a medium level of detail to illustrate the basic operation of the computation. We will not describe the lower level details of secure distributed computation. Let c=2 (the radix), and d=3 (the number of digits). This will allow for 8 bidding points, say tex2html_wrap_inline1408 . With base c=2, one polynomial is sufficient to represent each digit of the bid. This means that l=1 for all polynomials, so we will omit the l subscript. We will use p=7, m=3, t=1, and tex2html_wrap_inline1422 for this example. Note that these parameters are chosen strictly for simplicity of the example; they are not secure.

Suppose three bidders tex2html_wrap_inline1424 , tex2html_wrap_inline1426 , and tex2html_wrap_inline1428 have bids tex2html_wrap_inline1430 , tex2html_wrap_inline1432 , and tex2html_wrap_inline1434 respectively. In this case, the winner should be tex2html_wrap_inline1436 and the selling price should be the second highest bid, tex2html_wrap_inline1438 .

We use the symbols tex2html_wrap_inline1440 and tex2html_wrap_inline1442 to denote the values of polynomials' free coefficients. We will use the notation `` tex2html_wrap_inline1444 '' to mean that `` tex2html_wrap_inline1446 '' and `` tex2html_wrap_inline1448 '' to mean that tex2html_wrap_inline1450 .

During the bid submission step, each bidder selects the polynomials ( tex2html_wrap_inline1452 ) to encode the digits of their bids. Each bid is encoded with one polynomial per digit (since c=2). The bids are tex2html_wrap_inline1456 and similarly tex2html_wrap_inline1458 and tex2html_wrap_inline1460 .

The shared polynomials are distributed among the auctioneers, after which the auctioneers compute the result without further involvement from the bidders.

For example, the polynomials for tex2html_wrap_inline1462 could be tex2html_wrap_inline1464 , tex2html_wrap_inline1466 , and tex2html_wrap_inline1468 , and then bidder tex2html_wrap_inline1470 would share her polynomials by

Given the points of the shared polynomials, each auctioneer computes tex2html_wrap_inline1478 at tex2html_wrap_inline1480 round by tex2html_wrap_inline1482 . Table 1 shows how the polynomials are assigned through k = 1, 2, 3. The starting (i.e. k=1) values are tex2html_wrap_inline1488 . As stated in the description, the values for the tex2html_wrap_inline1490 are tex2html_wrap_inline1492 just for consistency, they are known values and are only in the useless operations of multiplication by 1 ( tex2html_wrap_inline1494 ) or addition to 0 ( tex2html_wrap_inline1496 ).

 

  table279


: Computation of polynomials for example auction



next up previous
Next: Efficiency Up: A scalable secret-bid second-price Previous: Breaking ties



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