Name
Abstract | ||
|---|---|---|
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 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 mn. 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-39206-1_49 | ICALP |
Keywords | DocType | Volume |
private circuit,black-box complexity,robust cryptographic prgs,robust r-wise independent prgs,robust prgs,cryptographic application,constant-round secure two-party computation,robust pseudorandom generator,k wire,circuit implementation,small-bias prgs | Journal | 2013 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
41 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuval Ishai | 1 | 4364 | 246.22 |
| Eyal Kushilevitz | 2 | 5525 | 478.96 |
| Xin Li | 3 | 1 | 0.72 |
| Rafail Ostrovsky | 4 | 8743 | 588.15 |
| Manoj Prabhakaran | 5 | 0 | 0.34 |
| Amit Sahai | 6 | 13566 | 545.52 |
| David Zucherman | 7 | 2588 | 266.65 |