# CSAIL Event Calendar: Previous Series

 On the (Im)Possibility of Basing One-Way Functions on NP-HardnessSpeaker: Adi Akavi , CSAIL, MITDate: 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/2006See other events happening in February 2006