SCIENCE@home

COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS

Benny Applebaum,Y. Ishai,E. Kushilevitz

Published 2005 in Cybersecurity and Cyberforensics Conference

ABSTRACT

Abstract.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 NC1) can be efficiently represented by degree-3 randomizing polynomials. Such a degree-3 representation gives rise to an NC40 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-40 of 40 references · Page 1 of 1

CITED BY

Showing 1-100 of 156 citing papers · Page 1 of 2

12
Next