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
Abstract:
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.
Previous
DIMACS home page