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
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
Contacting the Center
Document last modified on August 22, 2000.