BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1111
DTSTAMP:20230914T125951Z
SUMMARY:Secure Multiparty Computation with Limited Connectivity
DESCRIPTION:Speaker: Varun Narayanan\n\nAbstract: \nInformation theoretical
 ly secure multiparty computation (MPC) is a central primitive in modern cr
 yptography.\nIt enables mutually distrusting parties to collaboratively pe
 rform computations on their combined data by ensuring that each party's da
 ta is kept private from the others.\nThis is achieved by designing communi
 cation protocols which allow the parties to collectively simulate an incor
 ruptible trusted party\, who privately receives inputs from the parties\, 
 computes the pre-agreed functionality\, and delivers the outputs to the ap
 propriate parties privately.\nThe subject of this dissertation is MPC when
  there is limited connectivity in the communication network available to t
 he participants.\nOur motivations and the progress we made in addressing t
 hem follows:\n- In many practical scenarios\, the parties may only have ac
 cess to a communication network with limited connectivity\, in that\, not 
 every pair of parties can communicate privately and reliably with each oth
 er.\nWe characterize the conditions under which a pair of parties can comp
 ute any functionality with information theoretic security in an incomplete
  network of reliable\, private links.\nSeparate characterizations are obta
 ined for honest-but-curious and malicious modes of corruption with securit
 y against general adversary structures.\n- Many cryptographic tasks can be
  modelled as secure 2-party computation (2PC) using only one-directional c
 ommunication.\nGarg et al. (Crypto 15) initiated the study of non-interact
 ive 2PC over noisy channels with one-way communication\, namely when only 
 one party speaks.\nA major question left open by that work was the complet
 eness of finite channels in this model of secure computation.\nWe show tha
 t bit-ROT (i.e.\, Randomized Oblivious Transfer) channel\, which erases on
 e of the two input bits uniformly at random\, can compute any functionalit
 y with inverse polynomial security error (in the number of channel uses) i
 n this model against a computationally unbounded adversary.\nFurther\, ass
 uming ideal obfuscation\, realizable using tamper-proof hardware tokens\, 
 naturally occurring channels such as binary symmetric channel (BSC) and bi
 nary erasure channel (BEC) are complete in this sense with inverse polynom
 ial security error against a computationally bounded adversary.\nTo comple
 ment this\, we show that no channel with finite alphabet is complete in th
 is model with negligible security error even against a computationally bou
 nded adversary.\nFinally\, we characterize the channels that enable zero-k
 nowledge proofs in this model\; the previous result work had presented con
 struction of zero-knowledge proofs using BEC/BSC channels.\n- Studying sec
 ure computation with limited interaction tends to reveal new frontiers to 
 approach the problem of complexity of several information theoretic primit
 ives: a notoriously hard problem in cryptography.\nWe introduce a new prim
 itive in information-theoretic cryptography\, namely zero-communication re
 ductions (ZCR)\, with varying levels of security\, and relate it with seve
 ral other important primitives.\nUsing these connections\, we obtain new u
 pper bounds and lower bounds for complexity of several cryptographic primi
 tives.\n- MPC provides a meaningful and robust definition of security that
  can be used for modelling security guarantees for existing models in netw
 ork information theory.\nIndex coding is a well studied problem\, in which
  a server wants to efficiently broadcast n messages intended for n users\,
  each with access to a subset of these messages as side information.\nWe i
 ntroduce a notion of privacy in index coding\, where the receivers do not 
 learn anything more than the message they want from the server and those t
 hey have as side information\, and study various aspects of its transmissi
 on rate and secret consumption rate.\n
URL:https://www.tcs.tifr.res.in/web/events/1111
DTSTART;TZID=Asia/Kolkata:20210118T110000
DTEND;TZID=Asia/Kolkata:20210118T120000
END:VEVENT
END:VCALENDAR