# Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

 Title: Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions Author: Vadhan, Salil P.; Zheng, Colin Jia Note: Order does not necessarily reflect citation order of authors. Citation: Vadhan, Salil, and Colin Jia Zheng. 2012. Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions. In Proceedings of the 44th Symposium on Theory of Computing (STOC '12, New York, NY, USA, May 19 - 22, 2012), ed. ACM Special Interest Group on Automata and Computability Theory, 817-836. New York: ACM Press. Full Text & Related Files: PRG-NBPE.pdf (430.9Kb; PDF) Abstract: We provide a characterization of pseudoentropy in terms of hardness of sampling: Let (X,B) be jointly distributed random variables such that B takes values in a polynomial-sized set. We show that B is computationally indistinguishable from a random variable of higher Shannon entropy given X if and only if there is no probabilistic polynomial-time S such that (X,S(X)) has small KL divergence from (X,B). This can be viewed as an analogue of the Impagliazzo Hardcore Theorem (FOCS '95) for Shannon entropy (rather than min-entropy). Using this characterization, we show that if f is a one-way function, then (f(Un),Un) has "next-bit pseudoentropy" at least n+log n, establishing a conjecture of Haitner, Reingold, and Vadhan (STOC '10). Plugging this into the construction of Haitner et al., this yields a simpler construction of pseudorandom generators from one-way functions. In particular, the construction only performs hashing once, and only needs the hash functions that are randomness extractors (e.g. universal hash functions) rather than needing them to support "local list-decoding" (as in the Goldreich--Levin hardcore predicate, STOC '89). With an additional idea, we also show how to improve the seed length of the pseudorandom generator to ~{O}(n3), compared to O(n4) in the construction of Haitner et al. Published Version: doi:10.1145/2213977.2214051 Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12724017 Downloads of this work: