Communication Protocols for Secure Distributed Computation of Binary Functions

A common task in parallel processing is the distributed computation of a function by a number of processors, each of which possesses partial information relevant to the value of that function. In this paper we develop communication protocols which allow for such computation to take place while maintaining the value of the function secret to an eavesdropper. Of interest is the communication complexity of such protocols. We begin by considering two processors and two channels, one secret and one public, and present a protocol which minimizes the number of bits exchanged over the secret channel, while maintaining -uncertainty about the value of the function for the eavesdropper. We show that all binary functions can be kept -secret using a constant number of bits independent of the size of their domain. We then generalize our results to N processors communicating over a network of arbitrary topology.