ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR11-141 | 16th July 2013 01:40

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

RSS-Feed




Revision #3
Authors: Salil Vadhan, Colin Jia Zheng
Accepted on: 16th July 2013 01:40
Downloads: 203
Keywords: 


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(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.


Revision #2 to TR11-141 | 16th July 2013 01:36

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions





Revision #2
Authors: Salil Vadhan, Colin Jia Zheng
Accepted on: 16th July 2013 01:36
Downloads: 109
Keywords: 


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(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.


Revision #1 to TR11-141 | 2nd November 2011 09:01

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions


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(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.


Paper:

TR11-141 | 2nd November 2011 07:31

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions


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(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.



ISSN 1433-8092 | Imprint