Abstract:

One-way functions (i.e., polynomial-time computable functions
that are hard to invert on the average case) are the cornerstone
of modern cryptography. The hardness condition on the task of
inverting a one-way function is an *average-case* complexity
condition; this clearly implies a *worst-case* hardness
condition. A puzzling question of fundamental nature is whether
the necessary worst-case condition is also a sufficient one. In
particular: Can one-way functions be based on NP-hardness?
Namely, is there a reduction from a (worst case) NP-complete
problem to the task of (average case) inverting a
polynomial-time computable function?

We prove two results on the impossibility of basing one-way
functions on NP-hardness. Both results hold under the (widely
believed) complexity assumption that coNP is not contained in
AM:

1. One-way functions cannot be based on NP-hardness via
*non-adaptive* reductions (unless coNP is contained in AM).

2. Size-computable one-way functions cannot be based on
NP-hardness via *any* (possibly *adaptive*) reduction (unless
coNP is contained in AM); where we call f *size-computable* if
given y the number of pre-image $|f^{-1}(y)|$ is efficiently
computable. Moreover, size-verifiable one-way functions also
cannot be based on NP-hardness via any reduction (unless coNP is
contained in AM); where we call f *size-verifiable* if given y
it is possible to verify an approximate number of pre-image
$|f^{-1}(y)|$ (via an AM protocol).

Our results improve on previously known negative results of
[Feigenbaum-Fortnow, Bogdanov-Trevisan] 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, two new AM protocols
emerge for proving *upper bounds* on the sizes of NP sets.
Whereas the known *lower* bound protocol on set sizes by
[Goldwasser-Sipser] works for any NP set, the known *upper*
bound protocol on set sizes by [Fortnow, Aiello-Hastad] works
only in a settings where the verifier knows a random secret
element (unknown to the prover) in the NP set. The new protocols
we develop here, each work under different requirements than
that of [Fortnow, Aiello-Hastad], enlarging the settings in
which it is possible to prove upper bounds on NP set size.


Joint work with Oded Goldreich, Shafi Goldwasser and Dana
Moshkovitz