On the (Im)Possibility of Basing One-Way Functions on NP-Hardness
Speaker: Adi Akavi , CSAIL, MIT
Date: February 10 2006
Time: 10:30AM to 12:00PM
Location: 32-G449 (Patil/Kiva)
Contact: Be Blackburn, 3-6098, imbe@mit.edu
We consider the question of whether it is possible to base the existence of
one-way functions on NP-hardness. That is we study the possibility of
reductions from a worst-case NP-hard decision problem to the task of
inverting a polynomial time computable function. We prove two negative
results:
1. For any polynomial time computable function f: the existence of a
randomized *non-adaptive* reduction of worst case NP problems to
the task of average-case inverting f implies that
coNP\subseteq\AM. It is widely believed that coNP is not
contained in AM. Thus, this result may be regarded as showing that
such reductions cannot exist (unless coNP\subseteq\AM).
This result improves previous negative results that placed coNP in
{\em non-uniform} AM.
2. For any polynomial time computable function f for which it is possible
to efficiently compute pre-image sizes (\ie, |f^{-1}(y)| for a given y):
the existence of a randomized reduction of worst case NP problems to the
task of inverting f implies that coNP\subseteq\AM. Moreover, this is
also true for functions for which it is possible to verify (via and AM
protocol) the approximate size of pre-image sizes (\ie, |f^{-1}(y)| for a
given y). These results holds for *any reduction*, including *adaptive*
ones.
The previously known negative results regarding worst-case to
average-case reductions were confined to *non-adaptive* reductions.
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 [Aiello-Hastad] works in a setting 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 [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.
See other events that are part of Cryptography and Information Security Seminar Seminars 2005/2006
See other events happening in February 2006
