Robust Pseudorandom Generators

摘要

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