Search

We investigate the complexity of Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping p : F^n-> F^m, where F is a finite field, approximate the output entropy H(p(U_n)), where U_n is the uniform distribution on F^n and H may be any of several entropy measures. We show: Approximating the Shannon entropy of degree 3 polynomials p : F_2^n->F_2^m over F_2 to within an additive constant (or even n^{.9}) is complete for SZKPL, the class of problems having statistical zero-knowledge proofs where the honest verifier and its simulator are computable in logarithmic space. (SZKPL contains most of the natural problems known to be in the full class SZKP.) For prime fields F\neq F_2 and homogeneous quadratic polynomials p : F^n->F^m, there is a probabilistic polynomial-time algorithm that distinguishes the case that p(U_n) has entropy smaller than k from the case that p(U_n) has min-entropy (or even Renyi entropy) greater than (2+o(1))k. For degree d polynomials p : F_2^n->F_2^m, there is a polynomial-time algorithm that distinguishes the case that p(U_n) has max-entropy smaller than k (where the max-entropy of a random variable is the logarithm of its support size) from the case that p(U_n) has max-entropy at least (1+o(1))k^d (for fixed d and large k)., Engineering and Applied Sciences

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., Engineering and Applied Sciences