Common Information, Information Inequalities for Networks and Some Applications to Secure Function Computation

The goal of secure function computation is for mutually distrusting users in a network to collaborate without relying on a trusted server in computing a function of their data in such a way they end up learning no more information about each other's data than they can infer from their own data and the function value. In other words, the users want to simulate the presence of a trusted server which could compute the function and only provide the answer to the users. While feasibility conditions for information theoretically secure computation in networks have been found to a large extent starting with the seminal work of Ben Or-Goldwasser-Wigderson and Chaum-Crépeau-Damg ¥rd in the late 80s, the question of fundamentally how much communication is needed to securely compute remains largely open.

I will describe some of our recent work on showing optimality results and lower bounds for communication requirements to securely compute. We introduce a new class of information inequalities for networks and a generalization of the notions of common information of Gács-Körner and Wyner which turn out to be of general interest in reasoning about communicating/computing in networks.
Vinod M. Prabhakaran received his Ph.D. in 2007 from the University of California, Berkeley. He was a Postdoctoral Researcher at the Coordinated Science Laboratory, UIUC and EPFL, Switzerland . Since 2011, he has been at the Tata Institute of Fundamental Research (TIFR), Mumbai. His research interests are in information theory and cryptography.