M.Sc Student | Dubrov Bella |
---|---|

Subject | On the Randomness Complexity of Efficient Sampling |

Department | Department of Computer Science |

Supervisor | Professor Yuval Ishai |

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.