Advertisement
Published in:
2011 | OriginalPaper | Chapter
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators
Authors : Eric Miles, Emanuele Viola
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the complexity of black-box constructions of linear-stretch pseudorandom generators starting from a 1-bit stretch oracle generator
G
. We show that there is no construction which makes non-adaptive queries to
G
and then just outputs bits of the answers. The result extends to constructions that both work in the non-uniform setting and are only black-box in the primitive
G
(not the proof of correctness), in the sense that any such construction implies NP/poly
$\ne$
P/poly. We then argue that not much more can be obtained using our techniques: via a modification of an argument of Reingold, Trevisan, and Vadhan (TCC ’04), we prove in the non-uniform setting that there is a construction which only treats the primitive
G
as black-box, has polynomial stretch, makes non-adaptive queries to the oracle
G
, and outputs an affine function (i.e., parity or its complement) of the oracle query answers.