EFFICIENCY IMPROVEMENTS IN CONSTRUCTING PSEUDORANDOM GENERATORS FROM ONE-WAY FUNCTIONS

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 Hastad, Impagliazzo, Levin, and Luby [SIAM J. Comput., 28 (1999), pp. 1364-1396]. 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 [I. Haitner, O. Reingold, S. Vadhan, and H. Wee, Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 611-620]. An additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a nonadaptive manner. Using [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845-888], this implies the existence of pseudorandom generators in NC0 based on the existence of one-way functions in NC1.