Check out the new USENIX Web site.

next up previous
Next: Accountability Up: Efficiency Previous: Example costs

Asymptotic efficiency

This protocol we describe uses tex2html_wrap_inline1906 communication for each auctioneer. Information theory tells us that the bids must be tex2html_wrap_inline1908 in size. So, if we guarantee that t or fewer auctioneers can obtain no information about the bids, each bidder must distribute tex2html_wrap_inline1912 information to the auctioneers (which is tex2html_wrap_inline1914 per auctioneer). The verifiable secret sharing methods actually require an extra factor of tex2html_wrap_inline1916 above the theoretical minimums for non-verifiable secret sharing. So, in total, just distributing the bids requires tex2html_wrap_inline1918 communication for each auctioneer.

There are two major constant factors hidden by the notation which lie at the heart of high communication costs. The first is the large field we have chosen; the second is the constant associated with multiplying two polynomials. The choice of a large field was made to reduce the number of rounds of communicaiton required in phase 2, and alternative are being explored. The constant associated with multiplication is a more fundamental result of the distributed computation techniques used and the high fault-tolerance (3t<m) allowed.



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