Cryptographic Complexity and Computational Intractability
Speaker: Manoj Prabhakaran , University of Illinois, Urbana-Champaign
Date: January 15 2010
Time: 10:30AM to 12:00PM
Location: 32-G449
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL:
In this talk, I shall describe an ongoing project, and a series of
results therein, to understand cryptographic access to information in
its various flavors, and its relationship to computational
intractability.
Our first set of results relates to classifying 2-party secure
computation functionalities based on their "cryptographic complexity."
Here complexity is defined using natural notions of reduction that
capture cryptographic properties, but do not depend on computational
complexity aspects. We show several new reductions (protocols) as well
as separations, that help us identify cryptographic complexity
classes.
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 functionalities. In deriving these results, again, we
provide several 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 appear in this way.
These results are based on joint work with Hemanta Maji and Mike
Rosulek; if time permits I will mention on going works that also
involve Mohammad Mahmoody-Ghidary, Pichayoot Ouppaphan,
Vinod Prabhakaran and Amit Sahai.
See other events that are part of CIS/Microsoft Seminars 2009/2010
See other events happening in January 2010
