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