Randomizing polynomials: A new representation with applications to round-efficient secure computation

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. We get around this barrier by relaxing the requirement of evaluatingf into 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 f , relating the efficiency of such a randomization to the branching program size of f . On the other hand, by characterizing the exact class of Boolean functio...