@conference {634282,
	title = {Characterizing pseudoentropy and simplifying pseudorandom generator constructions},
	booktitle = {Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC {\textquoteleft}12)},
	year = {2012},
	pages = {817-836},
	publisher = {ACM},
	organization = {ACM},
	abstract = {
	Version History:\&nbsp;Full version posted as\&nbsp;ECCC TR11-141.



	We provide a characterization of pseudoentropy in terms of hardness of sampling: Let (\(X, B\)) be jointly distributed random variables such that\&nbsp;\(B\)\&nbsp;takes values in a polynomial-sized set. We show that\&nbsp;\(B\)\&nbsp;is computationally indistinguishable from a random variable of higher Shannon entropy given\&nbsp;\(X\) if and only if there is no probabilistic polynomial-time\&nbsp;\(S\) such that \((X, S(X))\) has small KL divergence from \((X, B)\). This can be viewed as an analogue of the Impagliazzo Hard- core Theorem (FOCS {\textquoteleft}95) for Shannon entropy (rather than min-entropy).



	Using this characterization, we show that if\&nbsp;\(f\)\&nbsp;is a one-way function, then \((f(U_n), U_n)\) has {\textquotedblleft}next-bit pseudoentropy{\textquotedblright} at least\&nbsp;\(n + \log n\), establishing a conjecture of Haitner, Reingold, and Vadhan (STOC {\textquoteleft}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 {\textquotedblleft}local list-decoding{\textquotedblright} (as in the Goldreich{\textendash}Levin hardcore predicate, STOC {\textquoteleft}89).



	With an additional idea, we also show how to improve the seed length of the pseudorandom generator to\&nbsp;\(\tilde{O}(n^3)\), compared to\&nbsp;\(\tilde{O}(n^4)\) in the construction of Haitner et al.

},
	url = {http://doi.org/10.1145/2213977.2214051},
	author = {Salil Vadhan and Colin Jia Zheng}
}
