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)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ICALP 2013
Keywords
pseudorandom generatorsleakage resiliencesecure computationrandomness complexity
Contact author(s)
yuvali @ cs technion ac il
History
2017-12-18: revised
2013-10-24: received
See all versions
Short URL
https://ia.cr/2013/671
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/671,
      author = {Yuval Ishai and Eyal Kushilevitz and Xin Li and Rafail Ostrovsky and Manoj Prabhakaran and Amit Sahai and David Zuckerman},
      title = {Robust Pseudorandom Generators},
      howpublished = {Cryptology ePrint Archive, Paper 2013/671},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/671}},
      url = {https://eprint.iacr.org/2013/671}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.