Check out the new USENIX Web site.

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

Costs for protocol phases

Given this verification model above, a bid submission consists of m messages (one to each auctioneer) from the bidder, each of size tex2html_wrap_inline1822 points. The auctioneers then verify the submission by an all-to-all communication with messages of size tex2html_wrap_inline1824 points.

Determining a digit of the selling price causes two occasions for degree reduction: the first when computing the tex2html_wrap_inline1826 in phase 1, the second when computing the summands of tex2html_wrap_inline1828 in phase 2. This is a total of tex2html_wrap_inline1830 multiplications over 4 communication rounds. There is one additional communication round where each auctioneer broadcasts c-1 points to reveal the tex2html_wrap_inline1834 shares.



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