On Basing OneWay Functions on NPHardness
Webpage for a paper by Akavia, Goldreich, Goldwasser, and Moshkovitz
Abstract
We consider the possibility of basing oneway functions on
NPHardness; that is, we study possible reductions from a
worstcase decision problem to the task of averagecase inverting
a polynomialtime computable function $f$ (i.e., reductions that
are supposed to establish that the latter function is oneway
based on a worstcase 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
averagecase 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 worstcase to averagecase reductions were
essentially confined to nonadaptive 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)
nonadaptive reduction of $NP$ to the task of averagecase
inverting $f$ implies that $NP\subseteq coAM$.
This result improves over the previous negative results
(for this case) that placed $NP$ in nonuniform $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 polynomialtime computable functions. We
believe that our results illustrate the gain of directly studying
the context of oneway functions rather than inferring results for
it from a the general study of worstcase to averagecase
reductions.
Material available online
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 "warmup" 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 nonadaptove reductions (in Sec 2.2 culminating in Thm 5).
Back to
either Oded Goldreich's homepage.
or general list of papers.