On Basing One-Way Functions on NP-Hardness

Webpage for a paper by Akavia, Goldreich, Goldwasser, and Moshkovitz

Abstract

We consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function $f$ (i.e., reductions that are supposed to establish that the latter function is one-way based on a worst-case assumption regarding the decision problem). Our main findings are the following two negative results:

If given $y$ one can efficiently compute $|f^{-1}(y)|$ then the existence of a (randomized) reduction of $NP$ to the task of average-case inverting $f$ implies that $NP\subseteq coAM$. Thus, it follows that such reductions cannot exist (unless $NP\subseteq coAM$). We stress that this result holds for any reduction, including adaptive ones. We note that the previously known negative results regarding worst-case to average-case reductions were essentially confined to non-adaptive reductions, whereas known positive results (regarding computational problems in the geometry of numbers) use adaptive reductions.
For any function $f$, the existence of a (randomized) non-adaptive reduction of $NP$ to the task of average-case inverting $f$ implies that $NP\subseteq coAM$. This result improves over the previous negative results (for this case) that placed $NP$ in non-uniform $coAM$.

Our work builds on the previous works of Feigenbaum and Fortnow (SICOMP, 1993) and Bogdanov and Trevisan (44th FOCS, 2003), while capitalizing on the additional ``computational structure'' of the search problem associated with the task of inverting polynomial-time computable functions. We believe that our results illustrate the gain of directly studying the context of one-way functions rather than inferring results for it from a the general study of worst-case to average-case reductions.

Material available on-line

The paper itself, April 2005.
A minor revision, Dec 2005.
Oded's preferred version: revised extended abstract (w.o. further details), Feb 2006.

Errata

[This refer to the version dated Feb 28 (2006), which is the basis for our STOC'06 extended abstract.]

There is a gap in the proof of our results regarding adaptive reductions, and we currently do not know whether THM 3 (as stated in Sec 2) holds. See technical details.

We note that the "warm-up" case discussed in the beginning of Sec 2.1 (i.e., $f$ having polynomially bounded preimage size) remains intact, and so all assertions made wrt adaptive reductions are valid when applied to this special case. We also note that the said gap does not effect our analysis of non-adaptove reductions (in Sec 2.2 culminating in Thm 5).

Back to either Oded Goldreich's homepage. or general list of papers.