Rafail Ostrovsky - Publications

Robust Pseudorandom Generators.

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

Let G:{0,1}ⁿ→{o,1}^mbe a pseudorandom generator. We say that a circuit implementation of G is (k,q)-robust is for every set S of at most K wires anywhere in the circuit, there is a set T of at, q|S| outputs, Such that conditioned on the values of S and T the remaning 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-Bisa 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 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.

The views expressed are thise of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. government.

comment: ICALP (1) 2013: 576-588

Fetch PDF file of the paper