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