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