On the randomness complexity of efficient sampling

We consider the following question: Can every efficiently samplable distribution be efficiently sampled, up to a small statistical distance, using roughly as much randomness as the length of its output? Towards a study of this question we generalize the current theory of pseudorandomness and consider pseudorandom generators that fool non-boolean distinguishers (nb-PRGs). We show a link between nb-PRGs and a notion of function compression , introduced by Harnik and Naor [16]. (A compression algorithm for f should efficiently compress an input x in a way that will preserve the information needed to compute f(x).) By constructing nb-PRGs, we answer the above question affirmatively under the following types of assumptions: Cryptographic incompressibility assumptions (that are implied by, and seem weaker than, "exponential" cryptographic assumptions).

Authors

• Bella Dubrov
• Yuval Ishai

Keywords

• compression
• derandomization
• information theoretic cryptography
• pseudorandom generators
• randomness complexity
• secure computation