Manoj M. Prabhakaran "The Communication Complexity of Secure Computation"

Thursday, July 10, 2014 - 11:00am to 12:00pm
Manoj M. Prabhakaran
University of Illinois
Information theoretically secure multi-party computation(MPC) is a
central primitive of modern cryptography. However, relatively little
is known about the communication complexity of this primitive. In this
work, we develop powerful information theoretic tools to prove lower
bounds on the communication complexity of MPC. We restrict ourselves
to a concrete setting involving 3-parties, in order to bring out the
power of these tools without introducing too many complications. Our
techniques include the use of a data processing inequality for
residual information — i.e., the gap between mutual information and
Gács-Körner common information, a new information inequality for
3-party protocols, and the idea of "distribution switching" by which
lower bounds computed under certain worst-case scenarios can be shown
to apply for the general case. 
Using these techniques we obtain tight bounds on communication
complexity by MPC protocols for various interesting functions. In
particular, we show concrete functions that have “communication-ideal”
protocols, which achieve the minimum communication simultaneously on
all links in the network. Also, we obtain the first explicit example
of a function that incurs a higher communication cost than the input
length in the secure computation model of Feige, Kilian and Naor, who
had shown that such functions exist. We also show that our
communication bounds imply tight lower bounds on the amount of
randomness required by MPC protocols for many interesting functions.