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.
展开▼
机译：我们从任何单向函数中给出了伪随机生成器的新构造。该构造获得了更好的参数，并且比Hastad，Impagliazzo，Levin和Luby的开创性工作中给出的构造更简单[SIAM J. Comput。，28（1999），pp。1364.1396]。我们构造的关键是下一块伪熵的新概念，其灵感来自不可访问的熵的概念。最近在[I. Haitner，O。Reingold，S。Vadhan和H. Wee，第41届ACM计算理论年度研讨会论文集（STOC），2009年，第611页。620]。与以前的构造相比，另一个优势是我们的伪随机数生成器可并行化，并且以非自适应方式调用单向函数。使用[B. Applebaum，Y. Ishai和E. Kushilevitz，SIAM J. Comput。，36（2006），pp.845.888]，这意味着基于NC1中单向函数的存在，NC0中存在伪随机生成器。
展开▼
