ICS 2010

Welcome to ICS2010
Innovations in Computer Science  ICS 2010, Tsinghua University, Beijing, China, January 57, 2010. Proceedings, 301309,
9787302217527
Tsinghua University Press
In this paper we study the possibility of proving the existence of oneway functions based on average case hardness. It is wellknown that if there exists a polynomialtime sampler that outputs instancesolution pairs such that the distribution on the instances is hard on average, then oneway 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 instancesolution 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 oneway permutations), then for every polynomial $\lambda$, there exists a search problem $R$ and a polynomialtime 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 instancesolution 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 instancesolution pairs cannot succeed. Preview:

Copyright 20092010, Institute for Computer Science, Tsinghua University, All Rights Reserved.