Computationally private randomizing polynomials and their applications (Q2458940)

In the paper a variant of the notion of \textit{randomized encoding} of a function is studied. Namely, \textit{computationally private} randomized encodings are introduced and used to investigate whether every polynomial-time computable function can be encoded by an \(NC^0\) function. As a main result it is shown how to construct a computationally private encoding in \(NC^0\) for every polynomial-time computable function, assuming the existence of `easy'- cryptographic pseudorandom generator (one that stretches its seed by just one bit) in uniform \(\bigoplus L/poly\). Using this construction, the authors are able to get some other interesting results. They show that the existence of various cryptographic primitives in \(NC^0\) follows from the EPRG assumption (i.e. an `easy'-cryptographic pseudorandom generator exists in uniform \(\bigoplus L/poly\)). Other application of the technique led to new parallel reductions between cryptographic primitives and new constant-round protocols for multiparty computations.