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 . 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 for this example. Note that these parameters are chosen strictly for simplicity of the example; they are not secure.

Suppose three bidders , , and have bids , , and respectively. In this case, the winner should be and the selling price should be the second highest bid, .

We use the symbols and to denote the values of polynomials' free coefficients. We will use the notation `` '' to mean that `` '' and `` '' to mean that .

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

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 could be , , and , and then bidder would share her polynomials by

• 
• 
• 

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

• In round 1 (k=1), there are at least 2 (exactly 2 in this case) j for which , and thus . This determines that the first digit of the selling price is 1 ( or equivalently ). Following the updating rule provided in section 4.2.3, auctioneers compute new polynomials .

• In round 2, there is only one j for which . So , and the auctioneers update polynomials accordingly. determines that the second digit of the selling price is 0, so ( ).

• Finally, in round 3, there are two j for which so the auctioneers determine that . We have , , and , so and the selling price is . Since , we have . For exactly one value we have . The winning bidder is . By combining their shares of auctioneers determine that ; bidder is the winner.

 

 

: Computation of polynomials for example auction