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.