__
TR09-143 | 22nd December 2009 16:52
__

#### On the Construction of One-Way Functions from Average Case Hardness

TR09-143
Authors:

Noam Livne
Publication: 23rd December 2009 10:26

Downloads: 2642

Keywords:

**Abstract:**
In this paper we study the possibility of proving the existence of

one-way functions based on average case hardness. It is well-known

that if there exists a polynomial-time sampler that outputs

instance-solution pairs such that the distribution on the instances

is hard on average, then one-way functions exist. We study the

possibility of constructing such a sampler based on the assumption

that there exists a sampler that outputs only instances, where the

distribution on the instances is hard on the average. Namely, we

study the possibility of "modifying" an ordinary sampler $S$ that

outputs (only) hard instances of some search problem $R$, to a

sampler that outputs instance-solution pairs of the same search

problem $R$. We show that under some restriction, not every sampler

can be so modified. That is, we show that if some hard problem with

certain properties exists (which, in particular is implied by the

existence of one-way permutations), then for every polynomial

$\lambda$, there exists a search problem $R$ and a polynomial-time

sampler $S$ such that (1) $R$ is hard under the distribution induced

by $S$, and (2) there is no sampler $S^*$ with randomness complexity

bounded by $\lambda$, that outputs instance-solution pairs of $R$,

where the distribution on the instances of $S^*$ is closely related

to that of $S$ (i.e., dominates it). A possible interpretation of

our result is that a generic approach for transforming samplers of

instances to samplers of instance-solution pairs cannot succeed.