In brief, the costs are non-trivial, and this protocol would not be appropriate for very low value (measured in cents) or extremely time-sensitive (results needed in seconds) auctions. However, most real-world auctions do not fall into these categories. Although the costs are not competitive with auctions which do not preserve privacy, such as [7], we believe that the complete privacy of the bids (and, if desired, the bidders)--even after the auction is completed--could well justify the higher implementation costs in many situations.
A major factor in the cost of the protocol is the fault tolerance. We describe the costs for 3t<m, but if we were to accept slightly lower fault tolerance, the low-level implementation would be greatly simplified, resulting in a substantial savings in communication costs. For example, changing m from 4 to 5 (and making the improvements that this would allow) would reduce the volume of communication per auctioneer by nearly a factor of 10 in the examples in section 4.5.2.
Communication costs will be the dominant concern for the protocol
described, and will consist largely of messages containing many points
drawn from the field 
. To simplify the analysis, we will
consider the costs in the case where there are no attempts to cheat;
the cost to detect and correct cheating depends heavily on the number
of attempted cheaters. Any cheating attempt (by at most t
auctioneers) will be immediately detected and corrected, so cheating
attempts by the auctioneers are unlikely to be frequent. Additionally,
we will not consider some small messages (mostly involving optional
counter-signatures on the bid submissions) which do not contribute
substantially to the total bandwidth used.
The following efficiency analysis assumes that the protocol uses the absolute secret verification as described in [2, 1]. Each polynomial is distributed by sending two degree-t polynomials to each recipient. Each recipient then shares 1 point with each other recipient to verify the secret. As with much of the communication in the protocol, many points can be verified in parallel.
The multiplication and degree-reduction of a pair of polynomials can
be compressesd into two rounds of communication (in addition to some
preparation which may occur prior to the protocol and which is
described below). In the first phase, each auctioneer verifiably
distributes shares for a total of t+3 polynomials: polynomials
encoding his shares of the two polynomials to be multiplied, a
polynomial encoding his share of the result of the multiplication, and
t other polynomials which enable confirmation that the product was
correctly computed on that share. In the second phase, all the check
points are exchanged among the auctioneers, ensuring that the secrets
from the first phase are valid. Also, a different set of check values
is broadcast by each auctioneer (4t points each). These points ensure
that a consistent (across all auctioneers) set of shares was used to
compute the product polynomial. Given the honest majority, this
ensures correct computation and enables correction of any errors (i.e.
attempts to cheat). These two rounds combined require the
communication of 
for each ordered pair of
auctioneers, and an additional 4t points of broadcast per
auctioneer. The product of many pairs of polynomials may be computed
in parallel.
The preparation for multiplication, as referred to above, is that the auctioneers must generate a random degree-t shared polynomial to be used for each multiplication. These polynomials can be generated in large batches prior to a run (or many runs) of the protocol. The process is simply for each auctioneer to generate and verifiably share one such polynomial, the sum of all m shared polynomials is one suitable random polynomial (even if t auctioneers are corrupt).