On the Communication Complexity of Secure Computation

In Secure multiparty computation (MPC), mutually distrustful parties each having a private input, perform a joint computation without revealing their inputs to each other. Information theoretically secure multi-party computation has been a central primitive of modern cryptography. However, relatively little is known about the communication complexity of this primitive.

In this talk, first I will give some background in secure MPC and information theory. We consider the problem where three parties are involved, two of them (Alice and Bob) have inputs and third one (Charlie) wants to compute the output. We insist that Charlie does not learn anything about the other parties' inputs from the protocol other than his output and whatever it reveals about the inputs. Also, Alice and Bob do not learn anything about the other parties' input/output from the protocol. We develop information theoretic tools to prove lower bounds on the communication complexity of secure computation in our setting and obtain tight bounds for secure computation protocols for various interesting functions. In particular, we show that for certain functions, there are “communication-ideal” protocols, which achieve the minimum communication simultaneously on all links in the network.