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. 
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 
are chosen to be
the set of powers of a primitive 
root of unity (say
). That 
is a primitive 
root means
and for 
, 
. Obviously we
must choose a finite field which has such a primitive 
root,
but this is not difficult (m is small). Given this choice of
, the shares of the polynomial are an error correcting code.
Up to 
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 
matrix (based on the the 
) 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 
) by multiplying its share of the polynomial by a vector
of constants (corresponding to row i of the matrix). Now 
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 
.