Check out the new USENIX Web site.

next up previous
Next: Open Problems Up: A scalable secret-bid second-price Previous: Passive attacks

Error analysis

  During the course of computation, we occasionally assume that the sum of several uniformly random and independent non-zero values in tex2html_wrap_inline1970 is also non-zero. The probability that such a sum is 0 is at most tex2html_wrap_inline1972 . Such errors may occur in the computation of the tex2html_wrap_inline1974 or tex2html_wrap_inline1976 .

In the case of computing tex2html_wrap_inline1978 , 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 tex2html_wrap_inline1982 (i.e., tex2html_wrap_inline1984 or tex2html_wrap_inline1986 ). Also, tex2html_wrap_inline1988 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 tex2html_wrap_inline1990 are uniformly random (from tex2html_wrap_inline1992 ). They are also independent of tex2html_wrap_inline1994 for tex2html_wrap_inline1996 , and thus are independent of the tex2html_wrap_inline1998 and tex2html_wrap_inline2000 (which are functions of the tex2html_wrap_inline2002 with tex2html_wrap_inline2004 ). Therefore, the value tex2html_wrap_inline2006 is uniformly random (from tex2html_wrap_inline2008 ). So the sum of tex2html_wrap_inline2010 and tex2html_wrap_inline2012 (for any particular k and l) can equal zero with probability at most tex2html_wrap_inline2018 .

Since the non-zero tex2html_wrap_inline2020 are uniform and independent, the tex2html_wrap_inline2022 , if non-zero, will also be uniform and independent of any tex2html_wrap_inline2024 which is non-zero (for tex2html_wrap_inline2026 ). In other words, the only dependency is contained in the property of being non-zero.

In the case of the tex2html_wrap_inline2028 , an error in the result of the bidding will be caused only for the one relevant l value tex2html_wrap_inline2032 . The chance of incorrectly generating a tex2html_wrap_inline2034 with value 0 at 0 is at most tex2html_wrap_inline2036 . To see this consider the values of tex2html_wrap_inline2038 as we compute it over increasing subsets of the bidders. Note the change in tex2html_wrap_inline2040 when we include the final bidder whose bid is as high as the test value (i.e. for whom tex2html_wrap_inline2042 ).

We can bound these sources of error by tex2html_wrap_inline2044 from the tex2html_wrap_inline2046 and tex2html_wrap_inline2048 for the tex2html_wrap_inline2050 , totalling tex2html_wrap_inline2052 . We must choose p large enough that tex2html_wrap_inline2056 is negligible. Since tex2html_wrap_inline2058 , 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.



next up previous
Next: Open Problems Up: A scalable secret-bid second-price Previous: Passive attacks



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