DIMACS Discrete Math--Theory of Computing Seminar

Speaker: Yuval Ishai
Affiliation: DIMACS, Rutgers University and AT&T Labs Research, Florham Park
Title : Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation Date: Tuesday, September 12
Time: 4:30-5:30
Place: CORE Building, Room 431, Busch Campus


Motivated by questions about secure multi-party computation, we introduce and study a new natural representation of functions by polynomials, which we term "randomizing polynomials". Standard low-degree polynomials over a finite field are easy to compute with a small number of communication rounds in virtually any setting for secure computation. However, most Boolean functions cannot be evaluated by a polynomial whose degree is smaller than their input size. To get around this barrier, we relax the requirement of evaluating f to a weaker requirement of "randomizing" f: mapping the inputs of f along with independent random inputs into a vector of outputs, whose distribution depends only on the value of f. We show that degree-3 polynomials are sufficient to randomize any function, relating the efficiency of such a randomization to its branching program size, and that 3 is the minimal randomization degree of most functions.

As an application, the secure evaluation of an arbitrary function can be reduced to the secure evaluation of degree-3 polynomials. A corollary of our reduction is that two (respectively, three) communication rounds are sufficient for k parties to compute any Boolean function f of their inputs, with perfect information-theoretic privacy against collusions of at most one third (resp., one half) of the parties, and communication complexity which is at most quadratic in the branching program size of f (with a small probability of one-sided error).

The talk is based on a joint work with Eyal Kushilevitz, and will not assume previous background on the problem of secure computation.

DIMACS home page
Contacting the Center
Document last modified on August 22, 2000.