Technical Report MSC-2006-06

Title: On the Randomness Complexity of Efficient Sampling
Authors: Bella Dubrov
Supervisors: Yuval Ishai
Abstract: 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. (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:

1. Cryptographic incompressibility assumptions (that are implied by, and seem weaker than, “exponential” cryptographic assumptions). 2. Nisan-Wigderson style (average-case) incompressibility assumptions for polynomial-time computable functions. 3. No assumptions are needed for answering our question affirmatively in the case of constant-depth samplers.

To complement the above, we extend an idea of Harnik and Naor and establish the following win-win situation. If the answer to our main question is “no”, then it is possible to construct a (weak variant of) collision-resistant hash function from any one-way permutation. The latter would be considered a surprising result, as a black-box construction of this type was ruled out by Simon.

Finally, we present an application of nb-PRGs to information-theoretic cryptography. Specifically, under any of the above assumptions, efficient protocols for information-theoretic secure multiparty computation never need to use (much) more randomness than communication.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion