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 $\left\lfloor{(n-1)/2}\right\rfloor$-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$. Using this relation, we show, for example, that $n$-argument addition is  $\left\lfloor{(n-1)/2}\right\rfloor$-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, $\left\lfloor{(n-1)/2}\right\rfloor$-private but not $\left\lceil{n/2}\right\rceil $-private, or not $1$-private.
Introduction
A set of n - 3 computationally unbounded parties, each holding an input x i taken from
a domain D, wishes to cooperate in distributively computing the value
predetermined function f . These parties are honest, namely they all follow their prescribed
protocol. They communicate over a complete point-to-point communication network, where
eavesdropping is not possible. A function f is called t-private if there is a communication
protocol for computing f , so that no coalition of at most t participants gets any additional
information from the execution of the protocol. Ben-Or, Goldwasser, and Wigderson [5], and
An early version of this paper appeared in Proc. of 31th FOCS, 1990, pp. 335-344. Research supported by
US-Israel Binational Science Foundation grant 88-00282.
y Department of Computer Science, Technion, Haifa 32000, Israel. e-mail: benny@cs.technion.ac.il . Part of
this research was done while visiting the Computer Science Department in the University of Toronto.
z Department of Computer Science, Tufts University, Medford, MA 02155. e-mail: gereb@cs.tufts.edu .
x Department of Computer Science, Technion, Haifa 32000, Israel. e-mail: eyalk@cs.technion.ac.il .
Chaum, Crepeau, and Damgard [8], have shown that if the domain D of f is finite, then f
is like addition, are even n-private over finite domains
[6], while certain functions, like Boolean OR, are not dn=2e-private 1 [5]. However, functions
of interest are typically defined not over finite domains, but rather over all strings, over the
integers, or more generally over some countable domain. To apply the protocol of [5, 8], one
has to (implicitly or explicitly) assume an upper bound on inputs size. If the bound does not
hold then the protocol, which depends not only on f , but also on the size of the domain, has to
be adjusted. This adjustment amounts to revealing additional information on the magnitude
of the inputs.
The question we deal with in this work is private computations of functions defined over
countable domains. In other words, is there a private protocol for computing f which can be
applied to all inputs, regardless of their sizes. Before going any further, we remark that the
1)=2c-private protocol of [5, 8] cannot be used in the infinite domain. Its first step is
to apply a secret-sharing scheme to every input. Secret sharing schemes strongly rely on the
finiteness of the domain, and indeed do not exist over countable domains [7, 11].
We show that the privacy of f is closely related to the communication complexity of f ,
as defined by Yao [17], namely to the number of bits that need to be communicated among n
parties in order to compute f (using any protocol, not necessarily a private one). The connection
between these two notions enables us to show that a wide class of functions are
private. This class includes, among others, maximum, minimum, addition over the non-negative
integers, and multiplication over all integers. The relations to communication complexity are
further used in our impossibility results. For example, we show that over the (negative and
non-negative) integers, addition is not even 1-private. That is, there is no protocol which
computes the sum of n integers and preserves privacy even with respect to single participants.
This contrasts with the b(n \Gamma 1)=2c-privacy of addition over the non-negative integers, and the
n-privacy of addition over any finite domain.
We give a complete characterization of private Boolean functions: A Boolean function is
1-private if and only if its communication complexity is bounded. As many Boolean functions
have unbounded communication complexity, this proves that there are Boolean functions which
are not even 1-private. Furthermore, we show that if a Boolean f is 1-private, then it is also
In [10] it was shown that if a Boolean f is dn=2e-private, then it is also
n-private. Hence there is a three level privacy hierarchy for Boolean functions: Every Boolean
function (defined over a countable domain) is either n-private, b(n \Gamma 1)=2c-private but not
dn=2e-private, or not 1-private.
The remainder of this paper is organized as follows: In section 2 we describe the model
and give the needed definitions. In section 3 we apply communication complexity arguments
to produce private protocols for various functions. Section 4 contains the impossibility results
for the functions addition and integer gcd. In section 5 we prove our characterization for the
Boolean case, and its implications. Section 6 introduces a model of non-terminating protocols
which compute f "in the limit", and demonstrate some intriguing private protocols in this
model. Finally, section 7 contains concluding remarks and open problems.
1 The study of private distributed computing was initiated in [18, 13]. The model used there is different
- the communication lines are not secure against eavesdropping, and on the other hand the participants are
computationally bounded, so cryptographic techniques can be employed.
Model and Definitions
The system consists of a synchronous network of n computationally unbounded parties
Each pair of parties is connected by a secure (no eavesdropping) and reliable communication
channel. At the beginning of an execution, each party P i has an input x
probability space is associated with the inputs). In addition, each party has a random input
r i taken from a source of randomness R i (the random inputs are independent). The parties
wish to compute the value of a function f(x 1 To this end, they exchange messages
as prescribed by a protocol F . The parties are honest, namely they follow the protocol F ,
and there are no failures of any kind. Messages are sent in rounds, where in each round every
processor sends a (non-empty) message to every other processor. The protocol specifies n
functions, one per party, which determine the messages sent by each party. The arguments to
the messages producing function of each processor are its input, its random input, the round
number, the messages it received so far, and the identity of the receiver.
The communication S sent in an execution of the protocol is the concatenation of all messages
sent in the execution, parsed according to sender, receiver, and round number. For a
subset ng we denote by S T the communication S with the exception of messages
sent between parties in -
T . The communication length of the protocol F on inputs x
is the maximum length of all communications S, sent in F on these inputs, over all random
inputs. We say that a communication string S, parsed as above, is consistent with the protocol
F , party P i and input x i if the following holds: There is a positive probability that if P i has
input x i and receives the messages in the string S that are destined to it, P i will send messages
identical to those messages in S that emanate from P i . (Notice that to be consistent with just
one party, the communication string need not be an actual string sent in some execution.)
We say that a protocol F computes the function f with "-advantage (0 for every
input last message in the protocol, is an identical message sent by party P 1
to all parties, indicating that this is the last message in the execution, and containing a value
F(~x; ~r) which satisfies
Denote by p k (~x) the probability that more than k bits are exchanged between the parties
during the execution of the protocol F with input ~x (the probability space is over the random
inputs of all parties). The protocol is terminating if for every input ~x
lim
We say that a coalition (i.e. a set of parties) T does not learn any additional information
(other than what follows from its input and the function value) from the execution of a randomized
protocol F , which computes f , if the following holds: For every two inputs ~x; ~y 2 (f0; 1g
that agree in their T entries (i.e. 8i the messages passed
between T and -
are identically distributed. That is, for every communication S,
where the probability space is over the random inputs of all parties.
We say that a protocol F for computing f is t-private if any coalition T of at most t parties
does not learn any additional information from the execution of the protocol. We say that a
function f is t-private if there exists a t-private terminating protocol that computes it with
"-advantage, for some section with some standard communication complexity definitions. Let f0; 1g -m
denote the collection of binary strings whose length is at most m. The "-advantage communication
complexity of f , when restricted to f0; 1g -m , denoted C " (f m ), is the minimum over
all n-party protocols which compute f with "-advantage over f0; 1g -m , of the worst case communication
length of the protocol, over all n-tuples of inputs that are all at most m-bit long.
(Notice that party P i has input x i . This is the "regular" definition, as in [17, 16], and should not
be confused with the one of Chandra, Furst and Lipton [9].) The "-advantage communication
complexity of a function f , denoted C " (f)(m), is defined as C " (f m ). For deterministic proto-
cols, C det (f)(m) is defined similarly. We say that f has bounded communication complexity if
there is some positive " (0 and an integer d, such that for all m, C " (f)(m) - d.
3 Functions That Can Be Privately Computed
In this section we present a sufficient condition, based on C " (f ), for 1)=2c-privacy of f .
This enables us to derive b(n \Gamma 1)=2c-private error-free protocols for a wide family of "natural"
functions. We start with a lemma:
B. If for every b 2 B the function
can be computed t-privately, using an error-free protocol, then f is t-private.
Proof: The value of f b (~x), for every b 2 B, is determined by the value of f(~x). Thus, to
compute f(~x), the parties can go over every b 2 B (say in lexicographic order) and compute
using the given t-private protocol for f b , without revealing any additional information.
The protocol terminates when for some b 2 B the value of f b (~x) is 1. From the definition of f b
this implies that b. As every function f b is computed by an error-free, t-private protocol,
it is not hard to verify that the resulting protocol is error-free and is t-private.
Theorem 2: 1. If for every b 2 B the communication
Proof: Using lemma 1 it is enough to prove that for every b 2 B, the function f b is
B. By the assumption, C " (f b ) is bounded. Extending a theorem
of Yao [17] from the two-party to the n-party case, it follows that C det (f b )(m) is at most
exponential in C " (f b )(m). In particular, if C " (f b ) is bounded, then so is C det (f b ). If for all m,
C det (f)(m) - d, this means that for every m, there is a d-bit protocol for f on
Using K-onig's lemma, this implies the existence of one deterministic protocol, F , defined over
(f0; 1g   ) n , which computes f and for every input exchanges at most d bits. (To prove this,
consider the following tree: The nodes in level m of the tree are the protocols that computes
f on
, that use at most d bits of communication. A protocol in level m+ 1 is the
son of a protocol in level m if they have the same communication on all inputs in
Since for every m there exists such a protocol, the tree is infinite. In addition, each protocol in
level m has finitely many sons - at most the number of possibilities to map the strings of length
into the set of d-bit communications. By K-onig's lemma, this implies the existence of
an infinite branch in the tree. This branch defines a protocol that computes f over (f0; 1g
and uses at most d bits of communication.)
be the set of all possible communications (in this deterministic
protocol) with last message (the output) consisting of "1". We describe an b(n \Gamma 1)=2c-private
protocol, F 0 , which computes f b . In the first step of F 0 , each party P i locally computes the set
y i as follows:
the communication S j is consistent with x i g:
Let
f
That is, f
only if there is a communication S j with "output" 1, which is consistent
with the inputs of all n participants. One can verify that f
(~x) and that f
b 's domain is
finite (every y i is a subset of f1; Thus, using the protocols of [5, 8] the value of f
can be computed 1)=2c-privately, which implies that the value of f b (~x) can be computed
1)=2c-privately. By Lemma 1 this completes the proof of the theorem.
Corollary 4: Let f : (f0; 1g   B. If for every b 2 B the set f \Gamma1 (b) is finite then f is
These results imply that many "natural" functions can be computed 1)=2c-privately.
This includes functions as addition over the positive integers, maximum, minimum, and multiplication
over the integers. Note that for the minimum and maximum, f \Gamma1 (b) is infinite
for every b. However, these two functions satisfy the condition of theorem 2 and thus are
Finally, we remark that the above protocols satisfy a stronger definition of privacy, as defined
in [10].
4 Impossibility Results
In this section we apply communication complexity arguments to prove the existence of functions
that are not even 1-private. Specifically, we show that addition over Z, the ring of integers,
is not 1-private. The same result holds for integer gcd.
Theorem 5: Let Z be defined as SUM n
There is no "-advantage protocol which computes SUM n 1-privately.
The high level structure of the proof is as following: Assume, towards a contradiction, that
there exists an "-advantage, 1-private, protocol F which computes SUM n . Privacy arguments
imply that, with high probability, the number of bits communicated by F on all inputs ~x
which satisfy SUM n We then show how to transform F into a two-argument
protocol which computes the predicate "identity" using bounded communication.
This contradicts a known lower bound.
Lemma be two constants. Suppose there is an "-advantage,
1-private protocol F for computing SUM n . Then there exists a constant d such that for every
input vector ~x with SUM n the probability that fewer than d bits are transmitted during
the execution of F is at least
Proof: We first show that for every ~x with SUM n the distribution of messages on
every link (P of the network, when the input is ~x, is the same as the distribution
of messages on this link, when the input is (0; we prove the existence of a
constant d as above for the input vector (0; Combining these two claims we get the
proof of the lemma.
Let ~x be an input vector satisfying SUM n To simplify the notations, we restrict
attention to the link Consider the following three input vectors:
~
By the assumptions, SUM n for all three vectors is 0. By 1-privacy, the distribution of messages
on the link must be the same for the two vectors ~x and ~
x 0 . Otherwise P 1 will be able to
distinguish between the two. Similarly, the distribution of messages on the link must
be equal for the two vectors ~
x 0 and ~ 0, as otherwise P 2 will be able to distinguish between them.
Thus, the distribution of messages on the link
In the second part of the proof, we use the termination condition for the input vector ~ 0.
It implies that for each link (P there exists a constant d i;j such that the probability that
more then d i;j bits are exchanged over during the execution of the protocol on ~ 0 is at
most ffi=
Let ~x be any input vector satisfying SUM n By the first part of the proof, the
probability that more then d i;j bits are exchanged over during the execution of the
protocol on ~x is also bounded by ffi=
. Thus, the probability that more than
i!j d i;j bits
are exchanged (over all
communication lines) during the execution of F on ~x is at most ffi.
This completes the proof of the lemma.
The next lemma is a known result in communication complexity. Let ID :
1g be the following function:
Lemma 7: (Yao [17]) For every constant
Proof of Theorem 5: Assume, towards a contradiction, that there exists a protocol
F which computes SUM n 1-privately with "-advantage. Let Using Lemma 6, there
exists a constant d such that for every input vector ~x satisfying SUM n the probability
that more than d bits are transmitted during the execution of F is bounded by ffi. We use
this property of F to construct a randomized protocol A to compute the ID function over
using only a constant (d number of bits. This will
be a contradiction to Lemma 7.
The protocol A works as following: On input (a; b) 2 f0; 1g m \Theta f0; 1g m , the two parties
(denoted by P  and P  ) will simulate the protocol F :
(the integer in the range binary
representation is the string a).
The parties P  and P  will simulate F until it either terminates, or d bits are transmitted. If F
terminates with final value 0, the parties output ID(a; (namely, they claim that a = b).
If F terminates with value 6= 0, or does not terminate after exchanging d bits, then the parties
output (namely, they claim that a 6= b).
Clearly, the protocol A transmits at most d+1 bits. What we now show is that A computes
the value of the ID function over f0; 1g m \Theta f0; 1g m with probability - 1+ ". If a
the constructed ~x satisfies SUM n the probability that more than d bits
are exchanged on such input is at most ffi. The other possible source of error is an incorrect
output of F . The probability that this happens is no greater than 1\Gamma ". Thus, the overall
error probability of A on (a; b) is no greater than ffi. By the choice of ffi this is equal
to 1\Gamma ". If a 6= b then ~x satisfies SUM n (~x) 6= 0. If more then d bits are transmitted, then
A outputs 0 which is the correct value of ID in this case. As the probability of error in F is
bounded by clearly this is so in case that the execution terminates with at most d
communicated bits. Thus, on such (a; b) the protocol A computes the correct value of ID(a; b)
with probability at least 1+ ". This completes the proof of the theorem.
Corollary 8: Multiplication over the rationales is not 1-private.
Proof: Addition over the integers can be reduced to multiplication in the cyclic group
by mapping the integer i to the rational number 2 i . Thus a 1-private protocol for
multiplication over the rationales would translate into a 1-private protocol for addition over the
integers, contradicting Theorem 5.
The technique relating communication complexity and privacy is applicable for various other
functions. For example:
Theorem 9: Let 2. Let N denote the set of natural numbers
and be defined as the greatest common divisor of the n arguments. There is
no "-advantage protocol which computes GCD n 1-privately.
Proof: The proof of this theorem is very similar to the proof for Theorem 5. We sketch
here the differences: the analogue of Lemma 6 will be proved for input vectors satisfying
1. In the proof of the analogous lemma we use the following triples of n-tuples:
~
denote the sequence of prime numbers. In the proof of the
theorem we will construct a protocol for ID as follows: On input (a; b) (two natural numbers
Clearly, GCD n only if a 6= b. Thus the original argument holds here as well.
5 Characterization For Boolean Functions
In this section we characterize the privacy of any Boolean function f in terms of its communication
complexity. Corollary 3 implies that any Boolean function f with bounded communication
complexity is b(n \Gamma 1)=2c-private. The main theorem in this section states the reverse implica-
tion. More precisely, a Boolean function whose communication complexity is unbounded is not
even 1-private. We set the stage for the theorem by introducing some definitions and claims.
Let A ' f0; 1g   \Theta f0; 1g   . Define a relation -A on A \Theta A by
or y . The equivalence relation jA is defined as the transitive closure of -A . Class(A)
denotes the number of equivalence classes of jA (it can be infinite). For any set S ' f0; 1g   \Theta
as the projections of S on the first and second coordinates respectively.
We now present two simple properties of the equivalence classes of the relation defined above:
1: Let A ' f0; 1g   \Theta f0; 1g   , and let K and L be two disjoint (non-empty) equivalence
classes of jA . Then,
Proof: Follows directly from the definition of the equivalence relation jA .
2: Let A ' f0; 1g   \Theta f0; 1g   , and let K and L be two disjoint (non-empty) equivalence
classes of jA . If (x;
A.
Proof: Assume, without loss of generality, that (x; y) 2 (K 1 \Theta L 2 ). This implies that there
exist y 0 such that (x; y Suppose that (x; y) 2 A. By the
definition of -A these pairs satisfy (x; y contradicting the disjointness of
the two jA equivalence classes K and L.
The next lemma states that if A and B cover f0; 1g   \Theta f0; 1g   need not be
disjoint), then either 2. Furthermore, if Class(B) - 3 then
1. Notice that it is possible to have e.g. by taking
Lemma 10: Suppose f0; 1g   \Theta f0; 1g   ' A [ B. If Class(B) - 3 then
Proof: 2 Let C; D;E be three distinct equivalence classes of jB . Let
be arbitrary elements of C; D and E respectively (see Figure 1). By claim 1, x i
for every i 3). Consider the element
Furthermore, by claim 1, they all belong to the same
equivalence class of jA . Denote this class by F .
Suppose, towards a contradiction, that jA has another equivalence class G, and let
G. By claim 1, x 4 3. Consider the element
claim 2,
A. Therefore, by claim 1 it must belong to C. By a similar
argument, must belong to D. This implies that contradicting claim 1.

Figure
Theorem 11: be 1-private. Then the communication complexity
of f is bounded.
Proof: F be a 1-private protocol which computes f with
"-advantage. We show that F can be modified to a communication protocol which computes
f with "-advantage while exchanging only a bounded number of bits between every pair of
parties (where the bound does not depend on the input).
In order to carry out this transformation, it would be desirable to be in a situation similar
to that occurring in SUM n , where every ~z 2 f \Gamma1 (0) has message distribution similar to some
fixed input ( ~ 0 for SUM n ). While this desired situation may not occur, something weaker, but
sufficient for our purposes, does: For every link (P there is a value v 2 f0; 1g and there are
at most two fixed inputs ~x(i; j); ~
so that for every ~z 2 f \Gamma1 (v), the distribution
of messages exchanged on the link (P is identical to the same distribution
either given input ~x(i; j) or given input ~
w(i; j).
n. Define the set A i;j (resp. B i;j ) by there exists an
n-tuple extending 1). Notice that
covers f0; 1g   \Theta f0; 1g   . We now relate the 1-privacy of f to the sets A i;j ; B i;j .
Suppose
(w 1-private protocol which computes
f induces identical distribution of messages exchanged between P i and P j , given the input ~x
and the input ~
w. (Similarly for
(w ).) The proof of this
claim is immediate from the definitions of the sets A i;j ; B i;j , the relations -A i;j
, -B i;j
and
, and 1-privacy.
By lemma 10, for each (i; j), at least one of the sets A i;j ; B i;j has no more than two equivalence
classes in the corresponding j equivalence relation. Without loss of generality A i;j has
at most two equivalence classes, and let fixed representatives of the two
classes. (Notice that for a different pair
can be the set with Class(\Delta) - 2.)
This proof simplifies our original proof, which appeared in the early version of this paper. It is due to
Freddy Bruckstein and Alon Orlitsky, and it appears here with their kind permission.
Let ~x(i;
w(i; denote two inputs in f \Gamma1 (0) whose projections on the i and j coordinates
yield the above representatives (take ~x(i;
there is only one equivalence class).
Let F be a 1-private protocol which computes f with "-advantage (0
runs of F on the 2 \Delta
inputs ~x(1; 2); ~
d be the minimal
integer such that the probability that P i and P j exchange more then d bits, given that the input
is either ~x(i; j) or ~
w(i; j), is less than "
(for all (i;
We modify the protocol F as follows: All parties run F until it either terminates, or some
pair attempts to exchange more than d bits. Suppose, without loss of generality, that the first
such pair is (1; 2), and further that ~x(1; 2); ~
. In this case, the pair aborts the
execution of F , and announces that the value of f is 1. (In case of conflicting announcements
in the same round, the one resulting from the minimal pair in lexicographical order is adopted
by all parties).
The modified protocol exchanges at most d \Delta
bits on all inputs. We argue that it computes
the correct answer with probability at least 1+ ". Suppose, without loss of generality, that
, the messages exchanged
between P i and P j on input ~z are distributed identically to one of the two representatives, and
thus the probability that more than d bits will be exchanged in F is bounded above by "
Thus the probability that some i; j as above will abort the execution of F and announce "1"
as the final outcome is smaller then ". Any pair
announce
"1" as the final outcome by aborting F 's execution. The other source of errors stems from
errors in F 's final outcome. The probability that this occurs is smaller than 1\Gamma ". Thus the
overall probability of error in the modified protocol is smaller than 1\Gamma "Combining Theorem 11 and Corollary 3, we get
Corollary 12: A Boolean function f : (f0; 1g   1-private if and only if it has
bounded communication complexity. If f is 1-private then it is b(n \Gamma 1)=2c-private.
Together with the characterization of dn=2e-private Boolean functions of [10], we conclude:
Theorem 13: Any Boolean function f : (f0; 1g
ffl n-private.
1)=2c-private private but not dn=2e-private.
ffl not 1-private.
6 Non-Terminating Protocols
So far, we considered protocols that are required to be private, compute the correct value (with
probability - 1+ "), and terminate (with probability 1). In this section we show that if we
abandon the termination condition (and the requirement that a distinguished "last message"
is sent), and require instead only "correctness in the limit", then private computations which
were not possible before become possible. We exemplify the model via two examples. Consider
the following non-terminating protocol for computing
For
ffl Each party P i locally computes y
ffl The parties compute n-privately, using the protocol of [6], s k such that s k j P n
k]. The value s k is the outcome of the k-th round.
It is easy to see that no coalition (of any size t - n) gets any additional information from
the execution of this protocol. After a finite number of iterations (which depends on the input
vector) the output s k stabilizes on the correct value. Thus, SUM n is n-private in the non-terminating
model.
The next example shows that we can demand even more. Consider the following non-terminating
protocol for computing GCD
For
ffl Each party P i computes y
ffl The parties compute, b(n \Gamma 1)=2c-privately, the AND of the y i 's. This bit indicates
whether k divides all the x i 's or not. The output of the k-th round is the maximal g - k
that divides all the x i 's.
The protocol computes GCD n , and it is b(n \Gamma 1)=2c-private in the non-terminating model.
In the protocol for SUM n , no participant knows when the result stabilizes. Here, however, the
gcd can never exceed x i . Thus after x i many iterations, party P i knows that he knows the final
outcome. After
all the parties know that they know the final outcome.
However, the protocol must continue, since the parties do not know whether the other parties
know that the result is already final. In other words, the privacy requirements prevent the
parties from achieving common knowledge [14] on the fact that the result is already final, and
an infinite execution is enforced.
7 Concluding Remarks
In case that a function f is not 1-private, it can still be computed by first revealing the lengths
of all participants inputs, and then using the protocols for the finite case of [8, 5]. However,
f(~x) can always be computed while revealing only smaller amount of additional information
(for a formal definition see [3, 4]) - the maximal input length, i.e.,
in two steps:
ffl Compute 1)=2c-privately the value
ffl Compute 1)=2c-privately the value of f over the finite domain of strings with length
at most m.
For functions with low circuit complexity, the second step can be performed efficiently using
the protocols described in [5, 8, 1]. The first step can be performed using the protocol described
in the proof of theorem 2 (section 3): In the '-th round, party P i sets y
the parties compute b(n \Gamma 1)=2c-privately the AND of the y i 's and
stop with output ' if the AND is 1. This step is therefore polynomial-time in the length of
the input ~x. It is possible to substantially reduce the number of iterations in this part while
preserving the polynomial complexity, by checking in the '-th round whether
Thus if the maximum is m, this fact is found in O(log m) rounds (instead of O(m) rounds).
A possible direction for extending Theorem 11 to functions with non-Boolean range might
be to generalize Lemma 10 to coloring of the two dimensional plane by more than 2 colors.
However, such generalization of the lemma is not true: There are 3 colorings of the plane (say
by colors 0,1,2), where Such example was constructed
by Nati Linial, and is included, with his kind permission, in the appendix. It remains open
whether the corresponding generalization of Theorem 11 is true.
One of the interesting questions in the area of private computations has been to investigate
the structure of the privacy hierarchy. Recently, we have resolved this question [12] for n
argument functions which are defined over finite domains. We have shown that for finite
domains, the privacy hierarchy has exactly bn=2c levels. For any dn=2e - t - 2, an n-
argument function which is t-private but not t + 1-private was constructed. The major tool
used in this proof was to partition the n inputs into two sets of appropriate sizes, and applying
the criteria for privacy of two argument functions. This approach is not useful in determining
t-privacy for t which is at most b(n \Gamma 1)=2c, because one of the two sizes will be larger than t.
Indeed, the results in [12] leave open the structure of the privacy hierarchy for functions defined
over countable domains.
The communication complexity techniques used in the present work are of very different
nature than the partition techniques which we mentioned above. They enabled us to show that
the privacy hierarchy contains a new, additional level (0-privacy). We believe that these techniques
will also play an important role in future research towards resolving the exact structure
of the privacy hierarchy over countable domains.

Acknowledgments

We are grateful to Shai Ben-David, Josh Benaloh, and Charlie Rackoff for very helpful discussions
and contributions to this work. Thanks to Freddy Bruckstein and Alon Orlitsky for
simplifying the proof of lemma 10, and to Nati Linial for his 3-coloring example. We would also
like to thank Oded Goldreich, who has the good property of commenting on early drafts fast.



--R

"Non-Cryptographic Fault-Tolerant Computing in a Constant Number of Rounds"
"Perfect Privacy for Two Party Protocols"
"Privacy, Additional Information, and Com- munication"
"Privacy, Additional Information, and Communication"
"Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation"
"Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret"
"Security Proofs for Information Protection Systems"

"Multi-Party Protocols"
"A Zero-One Law for Boolean Privacy"
"Secret Sharing over Infinite Domains"

"How to Play Any Mental Game"
"Knowledge and Common Knowledge in Distributed Envi- ronment"
"Privacy and Communication Complexity"
"Lower Bounds on Communication Complexity in Distributed Computer Net- works"
"Some Complexity Questions Related to Distributive Computing"
"Protocols for Secure Computations"
--TR

--CTR
Anna Gl , Adi Rosn, A theorem on sensitivity and applications in private computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.348-357, May 01-04, 1999, Atlanta, Georgia, United States
Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosn, Characterizing linear size circuits in terms of privacy, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.541-550, May 22-24, 1996, Philadelphia, Pennsylvania, United States
Anna Gal , Adi Rosen, Lower bounds on the amount of randomness in private computation, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Eyal Kushilevitz , Yishay Mansour, Randomness in private computations, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.181-190, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosn, Amortizing randomness in private multiparty computations, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.81-90, June 28-July 02, 1998, Puerto Vallarta, Mexico
private distributed computations;communication complexity