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(U_n),U_n)$ 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(n^3)$, compared to $O(n^4)$ in the construction of Haitner et al.

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(U_n),U_n)$ 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(n^3)$, compared to $O(n^4)$ in the construction of Haitner et al.

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(U_n),U_n)$ 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(n^3)$, compared to $O(n^4)$ in the construction of Haitner et al.

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(U_n),U_n)$ 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(n^3)$, compared to $O(n^4)$ in the construction of Haitner et al.