caa a22 4500 467909717 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20060601xx s 000 0 eng 10.1007/s00037-006-0211-8 doi (NATIONALLICENCE)springer-10.1007/s00037-006-0211-8 COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONS [Elektronische Daten] [Benny Applebaum, Yuval Ishai, Eyal Kushilevitz] 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 NC 4 0 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. Birkhäuser Verlag, Basel, 2006 Cryptography nationallicence constant depth circuits nationallicence NC0 nationallicence parallel construction nationallicence randomizing polynomials nationallicence garbled circuit nationallicence 94A60 nationallicence 68P25 nationallicence 68Q15 nationallicence Applebaum Benny Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut Ishai Yuval Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut Kushilevitz Eyal Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/2(2006-06-01), 115-162 1016-3328 15:2<115 2006 15 37 https://doi.org/10.1007/s00037-006-0211-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-006-0211-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Applebaum Benny Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Ishai Yuval Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut NATIONALLICENCE 700 1- Kushilevitz Eyal Computer Science Department Technion, Israel Institute of Technology, 32000, Haifa, Israel aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhauser.ch 15/2(2006-06-01), 115-162 1016-3328 15:2<115 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer