Private Computations over the Integers

The subject of this work is the possibility of private distributed computations of n-argument functions defined over the integers. A function f is t-private if there exists a protocol for computing f, so that no coalition of at most t participants can infer any additional information from the execution of the protocol. It is known that over finite domains every function can be computed (n - 1)/2-privately. Some functions, like addition, are even n-private. We prove that this result cannot be extended to infinite domains. The possibility of privately computing f is shown to be closely related to the communication complexity of f. By using this relation, we show, for example, that n-argument addition is (n - 1)/2-private over the nonnegative integers, but not even 1-private over all the integers. Finally, a complete characterization of t-private Boolean functions over countable domains is given. A Boolean function is 1-private if and only if its communication complexity is bounded. This characterization enables us to prove that every Boolean function falls into one of the following three categories: It is either n-private, (n - 1)/2-private but not n/2-private, or not 1-private.