Abstract:
=======
In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party) computations. Different kinds of cryptographic computations involve different constraints on how information is accessed, captured as "multi-party functionalities." Our goal is to qualitatively -- and when possible, quantitatively -- characterize the "cryptographic complexity" (defined using appropriate notions of reductions) of these different modes of accessing information. Also, we explore the relationship between such cryptographic complexity and computational intractability.

Our first set of results considers cryptographic complexity with no reference to computational complexity aspects. We identify several cryptographic complexity classes, with the help of new reductions (protocols, protocol compilers) as well as new separations (impossibility results), revealing a rich structure in the universe of multi-party functionalities. We also develop an information-theoretic measure to quantify the cryptographic content of correlated random variables distributed between two parties.

Our second set of results explores the connection between computational intractability and cryptographic complexity. Our results suggest that there are only a few distinct intractability assumptions that are necessary and sufficient for all the infinitely many reductions among multi-party functionalities. In deriving these results, again, we provide new protocols as well as separation results. Significantly, this approach of defining the universe of intractability requirements in terms of cryptographic functionalities (rather than using specific assumptions formulated for proving the security of specific constructions) gives a possibly finite set of computational complexity assumptions to study, corresponding to a finite set of worlds between "Minicrypt" and "Cryptomania." The main open problem we pose is to identify the set of all intractability assumptions that arise in this way.

These results are based on a series of works primarily with Hemanta Maji and Mike Rosulek, and also Yuval Ishai, Pichayoot Ouppaphan, Vinod Prabhakaran and Amit Sahai.
 
Short Bio:
========
 
Manoj Prabhakaran is an assistant professor at the Department of Computer Science at the University of Illinois, Urbana-Champaign. His primary research interest is in theoretical cryptography. Manoj received his Ph.D. in computer science from Princeton University in 2005, and a bachelor's degree in computer science and engineering from the Indian Institute of Technology, Bombay, in 2000.