^May June – 2005

In modern network settings, secure protocols are run concurrently with other arbitrary protocols. The interaction of different protocols with each other can be exploited by malicious parties to successfully attack the protocols, even if each protocol is secure when considered in isolation. To make things worse, adversarial parties may design and release "malicious" protocols whose sole purpose is to interact with secure protocols and compromise their security. In fact, it has been shown that in modern network settings like the Internet, it is easy to launch such attacks on real protocols.

In this talk, we discuss recent progress on a research project whose focus is the development of a theory for analyzing the security of protocols under these and other attack scenarios. We present definitions of security for different types of protocol composition, where many (possibly different) protocols are run concurrently in a network. We then discuss a number of positive and negative results regarding the feasibility of achieving security under these definitions. Finally, we will discuss research goals for the future.

Bio:

Yehuda completed his Ph.D. at the Weizmann Institute under the supervision of Oded Goldreich and Moni Naor. Following that, he was a PostDoc in the cryptography group at the IBM T.J.Watson Research Lab in New York. He is now currently a faculty member in the Computer Science department at Bar-Ilan University.

We prove that if NP is not in BPP, i.e., if some NP-complete language is worst-case hard, then for every probabilistic algorithm trying to decide the language, there exists some polynomially samplable distribution that is hard for it. That is, the algorithm often errs on inputs from this distribution. This is the first worst-case to average-case reduction for NP of any kind.

We stress however, that this does not mean that there exists one fixed samplable distribution that is hard for all probabilistic polynomial time algorithms, which is a pre-requisite assumption needed for OWF and cryptography (even if not a sufficient assumption). We elaborate on the difference between these two notions. Nevertheless, we do show that there is a fixed distribution on instances of NP-complete languages, that is samplable in quasi-polynomial time and is hard for all probabilistic polynomial time algorithms (unless NP is easy in the worst-case).

Our results are based on the following lemma that may be of independent interest: Given the description of an efficient (probabilistic) algorithm that fails to solve SAT in the worst-case, we can efficiently generate at most three Boolean formulas (of increasing lengths) such that the algorithm errs on at least one of them.

Joint work with Dan Gutfreund and Ronen Shaltiel.