BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/16
DTSTAMP:20230914T125906Z
SUMMARY:Cryptographic Complexity
DESCRIPTION:Speaker: Manoj M. Prabhakaran\nDepartment of Computer Science\n
University of Illinois at Urbana-Champaign\nUnited States of Am\n\nAbstrac
t: \nCryptographic primitives often define controlled access to (learning
and influencing) information\, permitting some kind of access while denyin
g others. This parallels the basic questions in computational complexity r
egarding whether there exist computational tasks that are easy in some sen
se while being hard in some other sense (e.g. problems in NP\\\\\\\\P). A
s such\, it is natural to frame some questions of computational complexity
(easiness/hardness combinations) in terms cryptographic primitives. Indee
d\, Impagliazzo's multiverse\, a framework used to discuss various complex
ity assumptions\, consists of two cryptographic worlds (minicrypt and cryp
tomania)\, which are related to different cryptographic primitives (privat
e-key encryption and public-key encryption).\n\nIn a recent sequence of wo
rks\, we investigate a possibly broader landscape of complexity assumption
s that can be related to a richer collection of cryptographic primitives -
- namely\, multiparty computation (MPC) primitives. In this talk we shall
see the basic ingredients and initial results of this investigation.\n\nFi
rst\, we shall set up information-theoretic notions of complexity for 2-pa
rty computation. This complexity notion is implicitly defined using the pa
rtial order of secure reducibility. These information theoretic reductio
ns serve as a baseline for framing computational complexity assumptions of
the form that one cryptographic primitive securely reduces to another in
a computationally bounded environment. We shall discuss specific results (
and some on going research) that throw light on minicrypt and cryptomania\
, and suggest the possibility of identifying other meaningful intermediate
complexity assumptions (this is joint work with Hemanta Maji and Mike Ros
ulek).\n
URL:https://www.tcs.tifr.res.in/web/events/16
DTSTART;VALUE=DATE:20090720
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR