REPORTS > DETAIL:

### Revision(s):

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

#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revision #3
Authors: Salil Vadhan, Colin Jia Zheng
Accepted on: 16th July 2013 01:40
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
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

Revision #1
Authors: Salil Vadhan, Colin Jia Zheng
Accepted on: 2nd November 2011 09:01
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.

### Paper:

TR11-141 | 2nd November 2011 07:31

#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

TR11-141
Authors: Salil Vadhan, Colin Jia Zheng
Publication: 2nd November 2011 07:34
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.

ISSN 1433-8092 | Imprint