On Basing One-Way Functions on NP-Hardness

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


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: 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


[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.