Characterizing pseudoentropy
Salil Vadhan, Colin Jia Zheng · 2012
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 no polynomial-time algorithm can distinguish B from some 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). As an application of this characterization, we show that if f is a one-way function (f is easy to compute but hard to invert), 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., we obtain a simpler construction of pseudorandom generators from one-way functions.