ECCC-Report TR11-141https://eccc.weizmann.ac.il/report/2011/141Comments and Revisions published for TR11-141en-usTue, 16 Jul 2013 01:40:52 +0300
Revision 3
| Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2011/141#revision3We 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.Tue, 16 Jul 2013 01:40:52 +0300https://eccc.weizmann.ac.il/report/2011/141#revision3
Revision 2
| Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2011/141#revision2We 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.Tue, 16 Jul 2013 01:36:07 +0300https://eccc.weizmann.ac.il/report/2011/141#revision2
Revision 1
| Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2011/141#revision1We 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.Wed, 02 Nov 2011 09:01:24 +0200https://eccc.weizmann.ac.il/report/2011/141#revision1
Paper TR11-141
| Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2011/141We 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.Wed, 02 Nov 2011 07:34:09 +0200https://eccc.weizmann.ac.il/report/2011/141