TR#:  MSC200606 
Class:  MSC 
Title:  On the Randomness Complexity of Efficient Sampling 
Authors:  Bella Dubrov 
Supervisors:  Yuval Ishai 
MSC200606.pdf  
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 nonboolean distinguishers (nbPRGs). We show a link between nbPRGs 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 nbPRGs, 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. NisanWigderson style (averagecase) incompressibility assumptions for polynomialtime computable functions. 3. No assumptions are needed for answering our question affirmatively in the case of constantdepth samplers. To complement the above, we extend an idea of Harnik and Naor and establish the following winwin situation. If the answer to our main question is “no”, then it is possible to construct a (weak variant of) collisionresistant hash function from any oneway permutation. The latter would be considered a surprising result, as a blackbox construction of this type was ruled out by Simon. Finally, we present an application of nbPRGs to informationtheoretic cryptography. Specifically, under any of the above assumptions, efficient protocols for informationtheoretic secure multiparty computation never need to use (much) more randomness than communication.

Copyright  The 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 (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/2006/MSC/MSC200606), rather than to the URL of the PDF or PS 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