Technical Report CS0554

Title: Privacy and Communication Complexity
Authors: Eya1 Kushilevitz
Abstract: Each of two parties P1 and P 2 holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x,y). That is, P1 should not learn any additiorlal infonnation about y (in the infonnation theoretic sense) other than what follows from its input x and the function value, f(x,y), and similarly, P2 shou1d not learn any additional infonnation about x.

In this paper we consider two basic questions in the theory of private computations: 1) Which functions can be privately computed? 2) What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)?

A complete combinatorial characterization df privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1<=g(n)<=2*2^n there are functions that can be privately computed with g(n) -rounds of cpmmunication, but not with g (n)-1 -rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the commpnication costs of non-private protocols. Interestingly, randomization does not help neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion