COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS

Randomizing polynomials allow representing a function f(x) by a low-degree randomized mapping \(\hat{f}(x, r)\) whose output distribution on an input x is a randomized encoding of f(x). It is known that any function f in uniform \(\bigoplus\)L/poly (and in particular in NC¹) can be efficiently represented by degree-3 randomizing polynomials. Such a degree-3 representation gives rise to an NC ⁰₄ representation, in which every bit of the output depends on only four bits of the input.

In this paper, we study the relaxed notion of computationally private randomizing polynomials, where the output distribution of \(\hat{f}(x, r)\) should only be computationally indistinguishable from a randomized encoding of f(x). We construct degree-3 randomizing polynomials of this type for every polynomial-time computable function, assuming the existence of a cryptographic pseudorandom generator (PRG) in uniform \(\bigoplus\)L/poly. (The latter assumption is implied by most standard intractability assumptions used in cryptography.) This result is obtained by combining a variant of Yao’s garbled circuit technique with previous “information-theoretic” constructions of randomizing polynomials.

We present several applications of computationally private randomizing polynomials in cryptography. In particular, we relax the sufficient assumptions for parallel constructions of cryptographic primitives, obtain new parallel reductions between primitives, and simplify the design of constant-round protocols for multiparty computation.

Authors and Affiliations

1. Computer Science Department Technion, Israel Institute of Technology, Haifa, 32000, Israel

   Benny Applebaum, Yuval Ishai & Eyal Kushilevitz

Corresponding author

Correspondence to Benny Applebaum.

Manuscript received 16 September 2005

Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.

Reprints and permissions