Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

DSpace/Manakin Repository

Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Citable link to this page

 

 
Title: Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions
Author: Vadhan, Salil P.; Zheng, Colin Jia

Note: Order does not necessarily reflect citation order of authors.

Citation: Vadhan, Salil, and Colin Jia Zheng. 2012. Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions. In Proceedings of the 44th Symposium on Theory of Computing (STOC '12, New York, NY, USA, May 19 - 22, 2012), ed. ACM Special Interest Group on Automata and Computability Theory, 817-836. New York: ACM Press.
Full Text & Related Files:
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(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., 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}(n3), compared to O(n4) in the construction of Haitner et al.
Published Version: doi:10.1145/2213977.2214051
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12724017
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters