Publication: Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
Open/View Files
Date
2010
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
Hasso-Plattner-Institut fuer Softwaresystemtechnik GmbH
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Haitner, Iftach, Omer Reingold, and Salil Vadhan. 2010. Efficiency improvements in constructing pseudorandom generators from one-way functions. Electronic Colloquium on Computational Complexity TR10-089.
Research Data
Abstract
We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired by the notion of "inaccessible entropy"' recently introduced in [Haitner, Reingold, Vadhan and Wee, STOC '09]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. Using [Applebaum, Yuval and Kushilevitz, SICOMP '06], this implies the existence of pseudorandom generators in \(NC^0\) based on the existence of one-way functions in \(NC^1\) .
Description
Keywords
one-way function, pseudorandom generator, pseudoentropy
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service