One-way functions are the cornerstone of modern cryptography. Informally speaking, one-way functions are functions that are easy to compute but are hard to invert (on the average case). There are several candidate functions, such as RSA or discrete-log, that are believed to be one-way, nonetheless, to date, no function was proved to be one-way. A puzzling question of fundamental nature is what are the minimal assumptions required for proving that a function is one-way. A necessary condition is that P does not equal NP (or more precisely, BPP does not equal NP, namely, that there is a problem in NP that cannot be solved by any probabilistic polynomial time algorithm). We ask whether this is also a sufficient condition. Namely, we ask whether there can be an efficient reduction from NP (that is, from the task of deciding an NP-complete language on the worst case) to a one-way function (that is, to the task of inverting a one way function on the average case).

We proved two results on the impossibility of reducing NP to a one-way function; both results hold under the (widely believed) complexity assumption that coNP is not contained in AM. 1. There cannot be a reduction not even an adaptive reduction from NP to a ”size verifiable” one-way function; where we call f size-verifiable if, given y, the number of pre-image |f−1(y)| is efficiently computable, or, more generally, efficiently verifiable via an AM protocol. 2. There cannot be a non-adaptive reduction from NP to any one-way function (be it size-verifiable or not). Our results improve on previously known negative results of [Feigenbaum-Fortnow,BogdanovTrevisan] by (i) handling adaptive reductions (whereas previous works were essentially confined to non-adaptive reductions), and by (ii) relying on a seemingly weaker complexity assumption. In the course of proving the above results, we designed a new constant round interactive protocol for proving upper bounds on the sizes of NP sets. We believe this protocol may be of independent interest. (Joint work with Oded Goldreich, Shafi Goldwasser and Dana Moshkovitz)