Cryptology ePrint Archive: Report 2013/671

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