Our approach builds on a long tradition of secret function computations. Researchers have developed a number of techniques for securely computing arbitrary functions--some major examples are [2, 8, 3]. This means that given a set of participants, each with an input, we can compute (with a polynomial slowdown) any function of the inputs; and moreover, we can do so with a protocol that leaks no information to any participant. The only information that a participant will know about the the input of other particpants is information derivable from his own input and the final result.
Unfortunately, the general techniques for secure computation are impractical for general use. They do, in fact, run in polynomial time, but with a big explosion of states. Thus, the development of private protocols for specific problems must be done by hand. We have developed and tuned our protocol to run quickly -- and we believe that it is practical for real use. We plan to build a prototype system embedding this algorithm to prove its practicality.
In the remaining sections, we first consider a simple private sealed-bid auction; that is, we show how to compute the max function privately. Then, we describe a fully private and secure second-price auction protocol which is the result of several improvements on the original.
The essence of the second-price protocol is a series of computations
which securely determine whether or not there are at least two bids
greater than or equal to a specific value. This test is performed by
determining if there is some partition of the set 
of n
bidders into 
and 
such that there is a bid at least
as high as the test value on each side of the partition. We need not
actually consider all possible partitions; we can select a small
number ( 
) of partitions which will suffice. We iterate this
series of computations in a search for the value of the second highest
bid.