BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/735
DTSTAMP:20230914T125936Z
SUMMARY:Secure Computation of Two-Party Asymmetric Randomized Functions
DESCRIPTION:Speaker: Deepesh Data\n\nAbstract: \nCharacterization of secur
ely computable two-party functions is one of the most fundamental problem
in cryptography. For deterministic functions\, a characterisation has been
known since late 80's\; but finding such a characterisation for {\\em ran
domised} functions in general remains elusive since then. In this work we
consider a special case\, where only one party computes the output. The pr
oblem is specified by a pair $(p_{XY}\,p_{Z|XY})$\, where $p_{XY}$ is the
input distribution from which inputs $x$ and $y$ of Alice and Bob\, respec
tively\, are drawn from\, and $p_{Z|XY}$ is the distribution according to
which Bob produces his output $z$. Any protocol for securely computing $(
p_{XY}\,p_{Z|XY})$ must satisfy two properties: (i) computation should be
correct\, and (ii) at the end of the protocol\, Alice does not learn anyth
ing about Bob's input and output\, and Bob does not learn anything about A
lice's input.\n\nWe consider two scenarios: (i) Perfectly secure computati
on -- where Alice and Bob get a single pair of inputs and Bob produces the
output securely\, and (ii) Asymptotically secure computation -- where Ali
ce and Bob get blocks of inputs $(x_1\,x_2\, ... \,x_n)$ and $(y_1\,y_2\,
... \,y_n)$\, respectively\, and Bob produces $(\\hat{z}_1\,\\hat{z}_2\, .
.. \,\\hat{z}_n)$ as his output. Asymptotic correctness means that the $L_
1$-distance between the ideal output distribution and the actual output di
stribution goes to zero as block-length $n$ tends to infinity\; and asympt
otic privacy means that the information leakage goes to zero as $n$ tends
to infinity. In perfect security setting we give a characterization of sec
urely computable {\\em randomized} functions and prove matching lower and
upper bounds on communication complexity for such functions. We prove that
the same characterization holds in asymptotic security setting as well an
d prove matching lower and upper bounds on communication complexity for su
ch functions.\n
URL:https://www.tcs.tifr.res.in/web/events/735
DTSTART;TZID=Asia/Kolkata:20161223T160000
DTEND;TZID=Asia/Kolkata:20161223T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR