**Robust Pseudorandom Generators**

*Yuval Ishai and Eyal Kushilevitz and Xin Li and Rafail Ostrovsky and Manoj Prabhakaran and 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.

**Category / Keywords: **foundations / pseudorandom generators, leakage resilience, secure computation, randomness complexity

**Original Publication**** (with major differences): **ICALP 2013

**Date: **received 18 Oct 2013

**Contact author: **yuvali at cs technion ac il

**Available format(s): **PDF | BibTeX Citation

**Version: **20131024:083731 (All versions of this report)

**Short URL: **ia.cr/2013/671

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]