TY - GEN

T1 - Robust pseudorandom generators

AU - Ishai, Yuval

AU - Kushilevitz, Eyal

AU - Li, Xin

AU - Ostrovsky, Rafail

AU - Prabhakaran, Manoj

AU - Sahai, Amit

AU - Zuckerman, David

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84880251510&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880251510&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_49

DO - 10.1007/978-3-642-39206-1_49

M3 - Conference contribution

AN - SCOPUS:84880251510

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 576

EP - 588

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -