International Association
for Cryptologic Research

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 {\\em residual

information} --- i.e., the gap between mutual information and

G\\\'acs-K\\\"orner common information, a new {\\em information inequality} for

3-party protocols, and the idea of {\\em 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 {\\em 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 \\cite{FeigeKiNa94}, 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.