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 (
).
: Computation of polynomials for example auction