Robust pseudorandom generators

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let G : {0,1}n → {0,1}m be a pseudorandom generator. We say that a circuit implementation of G is (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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Number of pages13
EditionPART 1
StatePublished - 2013
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Robust pseudorandom generators'. Together they form a unique fingerprint.

Cite this