Title :
Characterizing pseudoentropy
Author :
Vadhan, S. ; Zheng, C.J.
Author_Institution :
Sch. of Eng. & Appl. Sci., Harvard Univ., Cambridge, MA, USA
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 no polynomial-time algorithm can distinguish B from some 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). As an application of this characterization, we show that if f is a one-way function (f is easy to compute but hard to invert), 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., we obtain a simpler construction of pseudorandom generators from one-way functions.
Keywords :
computational complexity; entropy; random number generation; sampling methods; set theory; Haitner-Reingold-Vadhan conjecture; Shannon entropy; next-bit pseudoentropy; one-way function; polynomial-sized set; polynomial-time algorithm; pseudoentropy characterization; pseudorandom generator; random variable; sampling hardness; Complexity theory; Cryptography; Entropy; Generators; Polynomials; Probabilistic logic; Random variables;
Conference_Titel :
Information Theory Workshop (ITW), 2012 IEEE
Conference_Location :
Lausanne
Print_ISBN :
978-1-4673-0224-1
Electronic_ISBN :
978-1-4673-0222-7
DOI :
10.1109/ITW.2012.6404635
