Check out the new USENIX Web site.

next up previous
Next: A scalable secret-bid second-price Up: Electronic Auctions with Private Previous: A simple auction method

Secure distributed computation

  This section provides an overview of the methods used as the computational basis for the protocol, which come from Ben-Or, Goldwasser, and Wigderson[2]. For further details or proofs, we refer the reader to this work and its extension by Beaver[1]. Information is distributed among the agents (the auctioneers in our case) by means of polynomials over a finite field as introduced by Shamir[12], but with verifiability as in [2, 4]. These polynomials are stored in a point-value representation, where each of the m agents has a specific point tex2html_wrap_inline898 in the field at which he knows the value of all shared polynomials. The value of a polynomial at a specific point is known as a share. The initial polynomials will have some fixed degree-t. Since higher-order coefficients for these polynomials will be randomly selected from a set including zero, it might be more precise to say ``degree bound t'', but this distinction is never relevant to our results and we will freely ignore it.

Individual pieces of data are represented as points in the finite field and encoded in a shared polynomial as the free coefficient of that polynomial (which is the same as the evaluation of the polynomial at the point 0). All other coefficients are chosen from the field uniformly at random. Over a finite field (e.g. tex2html_wrap_inline904 for prime p), any set of t known values of a degree-t polynomial (chosen as described) gives information-theoretically zero information about the polynomial's value at any other point. This property that any t shares of a secret yield no information about the secret's value is known as t-privacy. There is a (simple and short) interactive protocol which ensures that the set of shares held by correct agents represents a degree-t polynomial.

The data used in the computation needs to be not only private, but tamper-proof as well. This property is supported by a special selection of the evaluation points. The tex2html_wrap_inline918 are chosen to be the set of powers of a primitive tex2html_wrap_inline920 root of unity (say tex2html_wrap_inline922 ). That tex2html_wrap_inline924 is a primitive tex2html_wrap_inline926 root means tex2html_wrap_inline928 and for tex2html_wrap_inline930 , tex2html_wrap_inline932 . Obviously we must choose a finite field which has such a primitive tex2html_wrap_inline934 root, but this is not difficult (m is small). Given this choice of tex2html_wrap_inline938 , the shares of the polynomial are an error correcting code. Up to tex2html_wrap_inline940 shares may be missing or incorrect and recovery of the free coefficient will still be possible. The resistance to up to t false values is known as t-resilience.

The basic computational operations are the addition or multiplication of two polynomials. The value of a sum or product of two polynomials at a point is the sum or product of the values of the two polynomials at that point. So, these operations are done pointwise, with each agent simply computing the addition or multiplication of the values at the point held. For addition (or multiplication by a scalar), this process is complete, privacy is not interfered with, and no other work needs to be performed. Extra work is required for multiplication.

The difficulty with multiplication is that the degree of the product of two polynomials is the sum of their degrees. The number of points needed to specify a degree-t polynomial is t+1, while to specify the product of two degree-t polynomials requires 2t+1 points. Repeated multiplications will continue to increase the degree of the shared polynomials. Since the polynomials are shared among a fixed number of agents, the degree of the polynomial will rapidly exceed the ability of the agents to represent it. Repeated multiplication requires some means of reducing the degree of a polynomial without changing or revealing information about its free coefficient. A related difficulty is that the product of two polynomials does not have the randomness property which we required to enforce privacy. Many polynomials of degree 2t can not be expressed as the product of two degree-t polynomials (e.g. irreducible polynomials).

These two difficulties are solved together by a stage of communication between the agents which produces a degree-t polynomial whose free coefficient is the same as the free coefficient of the product of 2 shared degree-t polynomials and whose remaining coefficients are uniformly random.

The key observation (which we state without proof) is as follows. If we interpret the m shares of a polynomial as a vector, there is a constant tex2html_wrap_inline964 matrix (based on the the tex2html_wrap_inline966 ) which transforms the shares of any degree-2t polynomial into shares of a degree-t polynomial while leaving the t+1 lowest-order coefficients unchanged. Each agent can compute a vector of values (call it tex2html_wrap_inline974 ) by multiplying its share of the polynomial by a vector of constants (corresponding to row i of the matrix). Now tex2html_wrap_inline978 is the vector of shares of the transformed polynomial. In order to mask non-uniformity of the coefficients of the product of polynomials, a random degree-t polynomials is generated and added to the vector components before they are shared. The agents sum all received values to compute their shares of the new polynomial, which has the claimed properties.

In this method as described, multiplication can violate our t-resilience because false behavior on the part of one of the agents can lead to erroneous values at many others through the communication of the degree reduction. A further level of complication is required to ensure that the method described is in fact carried out correctly, but we will not go into that level of detail here (as before we refer the reader to [2, 1]). Intuitively, exchanges among the agents are used to prove that the agents follow the prescribed rules in conducting the transfer of information during the degree reduction phases. In order to simultaneously maintain t-resilience and t-privacy, we must be able to tolerate up to t incorrect shares at the beginning of a degree reduction (when the degree of the polynomials will be 2t. So, we restrict t by tex2html_wrap_inline994 .



next up previous
Next: A scalable secret-bid second-price Up: Electronic Auctions with Private Previous: A simple auction method



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