Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-143 | 18th December 2017 10:01

Robust Pseudorandom Generators

RSS-Feed




Revision #1
Authors: Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman
Accepted on: 18th December 2017 10:01
Downloads: 758
Keywords: 


Abstract:

Let $G:\{0,1\}^n\to\{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.



Changes to previous version:

Minor revision, including:
- Fixed inaccuracy in parameters of non-explicit construction (Theorems 3,4)
- Fixed error in refreshing gadget (Claim 31)


Paper:

TR13-143 | 19th October 2013 06:12

Robust Pseudorandom Generators


Abstract:

Let $G:\{0,1\}^n\to\{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.



ISSN 1433-8092 | Imprint