In work with Akavia, Goldreich and Moshkovitz, Prof. Goldwasser considers the possibility of basing one-way functions on NP-Hardness; that is, studying 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). The main findings are the following two negative results:

1. 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 coAM$. Thus, it follows that such reductions cannot exist (unless NP coAM$).
   
   The result extends to functions for which the preimage size is efficiently verifiable via an AM protocol. For example, this includes regular functions with efficiently recognizable range.
   
   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.
   
2. 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 coAM.
   
   This result improves over the previous negative results (for this case) that placed NP in non-uniform coAM.

This work builds on the previous works of Feigenbaum and Fortnow (SIAM Journal on Computing, 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 the general study of worst-case to average-case reductions.

References

[1] A. Bogdanov and L. Trevisan. On worst-case to average-case reductions for NP problems. In Proc. 44th IEEE Symposium on Foundations of Computer Science, pages 308--317, 2003.

[2] J. Feigenbaum and L. Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing, 22:994--1005, 1993. Extended Abstract appe