Seminars

View all Seminars  |  Download ICal for this event

Towards Communication Optimal Broadcast

Series: Department Seminar

Speaker: Anirudh Chandramouli

Date/Time: Mar 11 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor:

Abstract:
Broadcast is a fundamental building block used in secure computation protocols and enables a designated party (a sender) to equivocally transmit a message to n parties of which up to t may be maliciously faulty (including the sender). In the regime of t < n/3, it is possible to realize broadcast over point-to-point (ideally private) channels with perfect security (zero probability of error). Broadly, two classes of such broadcast protocols have been shown in the literature: succinct protocols with high latency (O(n) rounds); and communication-intensive protocols with expected low latency (expected O(1) rounds). We consider the construction of broadcast protocols in both settings and improve on the state of the art. Specifically, for the broadcast of L bits, we show A protocol with total communication O(nL + n^2 log n) bits that runs in O(n) rounds. Our protocol achieves 40% better communication than the state of the art and runs in fewer rounds. Furthermore, our protocol is an asymptotic factor of log n from the optimal. A protocol with total communication O(nL) + expected O(n^3 log^2 n) bits that runs in expected O(1) rounds. Our protocol asymptotically improves on the state of the art by a factor of n/log n and is an asymptotic factor of n log^2 n away from the optimal.

Speaker Bio:
Anirudh Chandramouli received his bachelors and masters degree in computer science from the International Institute of Information Technology, Bangalore. His masters thesis was under the guidance of Prof. Ashish Choudhury and Prof. Arpita Patra, IISc Bangalore. He is currently a PhD candidate at Bar Ilan University, Israel under the guidance of Prof. Gilad Asharov. 

Host Faculty: Prof. Arpita Patra