Speaker: |
Deepesh Data |

Organiser: |
Gowtham Raghunath Kurri |

Date: |
Friday, 23 Dec 2016, 16:00 to 17:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We consider two scenarios: (i) Perfectly secure computation -- where Alice and Bob get a single pair of inputs and Bob produces the output securely, and (ii) Asymptotically secure computation -- where Alice 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 distribution goes to zero as block-length $n$ tends to infinity; and asymptotic privacy means that the information leakage goes to zero as $n$ tends to infinity. In perfect security setting we give a characterization of securely 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 and prove matching lower and upper bounds on communication complexity for such functions.