Welcome to the resource topic for 2013/671
Title:
Robust Pseudorandom Generators
Authors: Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, 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.
ePrint: https://eprint.iacr.org/2013/671
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .