Paper 2013/671

Robust Pseudorandom Generators

Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, and David Zuckerman

Abstract

Let $G:\bits^n\to\bits^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is {\em $(k,q)$-robust} if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ the remaining outputs are pseudorandom. We initiate the study of robust PRGs, presenting explicit and non-explicit constructions in which $k$ is close to $n$, $q$ is constant, and $m>>n$. These include unconditional constructions of robust $r$-wise independent PRGs and small-bias PRGs, as well as conditional constructions of robust cryptographic PRGs. In addition to their general usefulness as a more resilient form of PRGs, our study of robust PRGs is motivated by cryptographic applications in which an adversary has a local view of a large source of secret randomness. We apply robust $r$-wise independent PRGs towards reducing the randomness complexity of private circuits and protocols for secure multiparty computation, as well as improving the ``black-box complexity'' of constant-round secure two-party computation.

Note: Minor revision, including: - Fixed inaccuracy in parameters of non-explicit construction (Theorems 3,4) - Fixed error in refreshing gadget (Claim 31)