ECCC-Report TR13-143https://eccc.weizmann.ac.il/report/2013/143Comments and Revisions published for TR13-143en-usMon, 18 Dec 2017 10:01:07 +0200
Revision 1
| Robust Pseudorandom Generators |
Yuval Ishai,
Eyal Kushilevitz,
Xin Li,
Rafail Ostrovsky,
Manoj Prabhakaran,
Amit Sahai,
David Zuckerman
https://eccc.weizmann.ac.il/report/2013/143#revision1Let $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.
Mon, 18 Dec 2017 10:01:07 +0200https://eccc.weizmann.ac.il/report/2013/143#revision1
Paper TR13-143
| Robust Pseudorandom Generators |
Yuval Ishai,
Eyal Kushilevitz,
Xin Li,
Rafail Ostrovsky,
Manoj Prabhakaran,
Amit Sahai,
David Zuckerman
https://eccc.weizmann.ac.il/report/2013/143Let $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.
Sat, 19 Oct 2013 06:14:13 +0300https://eccc.weizmann.ac.il/report/2013/143