Communication protocols for secure distributed computation of binary functions

A common task in parallel processing is the distributed computation of a fu nction by a number of processors, each of which possesses partial informati on relevant to the value of that function. In this paper we develop communi cation protocols which allow for such computation to take place while maint aining 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 prot ocol which minimizes the number of bits exchanged over the secret channel, while maintaining epsilon-uncertainty about the value of the function for t he eavesdropper. We show that all binary functions can be kept epsilon-secr et using a constant number of bits independent of the size of their domain. We then generalize our results to N processors communicating over a networ k of arbitrary topology. (C) 2000 Academic Press.