In the case of computing , such a chance will introduce an
error into the result of the bidding only if it occurs for the l
that are relevant to the selection of
(i.e.,
or
).
Also,
will never be non-zero for any bidder other than the
winner, so this error will be possible only for the winning bidder.
The non-zero
are uniformly random (from
). They are also independent of
for
, and thus are independent of the
and
(which are functions of the
with
). Therefore, the
value
is uniformly random (from
). So the sum of
and
(for any particular k and l) can equal zero with
probability at most
.
Since the non-zero are uniform and
independent, the
, if non-zero, will also be uniform and
independent of any
which is non-zero (for
). In other words, the only dependency is contained in the property
of being non-zero.
In the case of the , an error in the result of the
bidding will be caused only for the one relevant l value
.
The chance of incorrectly generating a
with value 0 at 0 is
at most
. To see this consider the values of
as
we compute it over increasing subsets of the bidders. Note the change
in
when we include the final bidder whose bid is as high
as the test value (i.e. for whom
).
We can bound these sources of error by from the
and
for the
, totalling
. We must choose p large enough that
is
negligible. Since
, where V is the number of bidding
points, its value in any implementation would be small (certainly
less than 40). Making a tradeoff between speed and possibility of error,
p should be in the range of 64-128 bits.