BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/796
DTSTAMP:20230914T125938Z
SUMMARY:Communication Complexity and Characterization Results in Secure Com
 putation
DESCRIPTION:Speaker: Deepesh  Data\n\nAbstract: \nInformation theoretically
  secure multi-party computation (MPC) has been a central primitive of mod
 ern cryptography\, in which mutually distrusting parties collaborate to co
 mpute a function of their private data without revealing any additional in
 formation about their data to the other parties. It is known that informa
 tion theoretically secure MPC is possible among $n$ parties against the c
 ollusion of less than $n/2$ parties in the honest-but-curious model\; the
  threshold is $n/3$ in the malicious model.\n\nDespite the huge success i
 n many frontiers of cryptography\, many basic questions in the study of s
 ecure MPC have seen a little progress. Two of these questions are the subj
 ect of this thesis: communication and randomness complexity of secure MPC\
 ; and characterization of which functions are securely computable. We stud
 y these questions in two and three party settings against the corruption o
 f a single party in the honest-but-curious model. In the three party setti
 ng\, we develop new information theoretic tools to obtain tight lower boun
 ds on communication and randomness complexity of secure MPC. We derive low
 er bounds for both the perfect security case (i.e.\, zero-error and no lea
 kage of information) and asymptotic security (where the probability of err
 or and information leakage vanish as block-length goes to infinity)\; and 
 they are shown to be tight for several interesting functions.\n\nIn the tw
 o party setting\, we consider secure computation of randomized functions.
  When both the parties (Alice and Bob) are required to produce outputs\, 
 even the characterization of which randomized functions are securely compu
 table is not known\; however\, the deterministic counterpart of this prob
 lem was resolved by Kushilevitz (FOCS 1989) around three decades ago. We 
 make some progress in this long standing open problem and give a couple of
  characterizations: for randomized functions that have up to ternary outpu
 t alphabet\, and for randomized functions that are securely computable by 
 up to two-round protocols. The problem becomes easier when only one party 
 is required to produce the output. We study this problem further in four c
 ases: (i) when privacy is required against both the parties\; (ii) when pr
 ivacy is required only against Alice\; (iii) when privacy is required only
  against Bob\; and (iv) when there is no privacy requirement. For all the 
 four cases we obtain optimal rate expressions in both perfect and asymptot
 ic security settings.\n
URL:https://www.tcs.tifr.res.in/web/events/796
DTSTART;TZID=Asia/Kolkata:20170731T160000
DTEND;TZID=Asia/Kolkata:20170731T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR