A Randomness-Rounds Tradeoff in Private Computation.
We study the role of randomness in multiparty private computations. In particular, we give several results that prove the existence of a randomness-rounds tradeoff in multiparty private computation of $\fxor$. We show that with a single random bit, $\Theta(n)$ rounds are necessary and sufficient to privately compute $\fxor$ of n input bits. With $d\ge 2$ random bits, $\Omega(\log n/ d)$ rounds are necessary, and $O(\log n/ \log d)$ are sufficient.  More generally, we show that the private computation of a boolean function f, using $d\ge 2 $ random bits, requires $\Omega(\log S(f)/ d)$ rounds, where S(f) is the sensitivity of f. Using a single random bit, $\Omega(S(f))$ rounds are necessary.
Introduction
A 1-private (or simply, private) protocol A for computing a function f is a protocol that allows
possessing an individual secret input, x i , to compute the value
of f(~x) in a way that no single player learns more about the initial inputs of other players
than what is revealed by the value of f(~x) and its own input 1 . The players are assumed to
be honest but curious. Namely, they all follow the prescribed protocol A but they could try
to get additional information by considering the messages they receive during the execution of
the protocol. Private computations in this setting were the subject of a considerable amount of
An early version of this paper appeared in Advances in Cryptology, Proceedings of Crypto '94, Y. Desmedt,
ed., Springer-Verlag, Lecture Notes in Computer Science, Vol. 839, pp. 397-410, 1994.
y Dept. of Computer Science, Technion, Haifa, Israel. e-mail: eyalk@cs.technion.ac.il;
http://www.cs.technion.ac.il/-eyalk; Work on this research was supported by the E. and J. Bishop Research
Fund, and by the Fund for the Promotion of Research at the Technion. Part of this research was performed
while the author was at Aiken Computation Laboratory, Harvard University, supported by research contracts
ONR-N0001491-J-1981 and NSF-CCR-90-07677.
z Dept. of Computer Science, Tel-Aviv University, Tel-Aviv, Israel. e-mail: adiro@math.tau.ac.il
1 In the literature a more general definition of t-privacy is given. The above definition is the case
work, e.g., [BGW88, CCD88, BB89, CK89, K89, B89, FY92, CK92, CGK90, CGK92, KMO94].
One crucial ingredient in private protocols is the use of randomness. Quantifying the amount of
randomness needed for computing functions privately is the subject of the present work.
Randomness as a resource was extensively studied in the last decade. Methods for saving
random bits range over pseudo-random generators [BM84, Y82, N90], techniques for re-cycling
random bits [IZ89, CW89], sources of weak randomness [CG88, VV85, Z91], and constructions
of different kinds of small probability spaces [NN90, AGHP90, S92, KM93, KM94, KK94] (which
sometimes even allow to eliminate the use of randomness). A different direction of research is a
quantitative study of the role of randomness in specific contexts, e.g., [RS89, KPU88, BGG90,
CG90, BGS94, BSV94]. In this work, we initiate a quantitative study of randomness in private
computations. We mainly concentrate on the specific task of computing the xor of n input bits.
However, most of our results extend to any boolean function. The task of computing xor was the
subject of previous research due to its being a basic linear operation and its relative simplicity
[FY92, CK92].
It is known as a "folklore theorem" (and is not difficult to show) that private computation of
xor cannot be carried out deterministically (for n - 3). On the other hand, with a single random
bit such a computation becomes possible: At the first round player P n chooses a random bit r
and sends to P 1 the bit x n \Phi r. Then, in round i xors its bit x i\Gamma1 with
the message it received in the previous round, and sends the result to P i . Finally, P n xors the
message it received with the random bit r. Both the correctness and privacy of this protocol are
easy to verify. The main drawback of this protocol is that it takes n rounds. Another protocol
for this task computes xor in two rounds but requires a linear number of random bits: In the
first round each player P i chooses a random bit r i . Then, player P i sends x i \Phi r i to P 1 and r i to
In the second round P 2 xors all the (random) bits it received in the first round and sends
the result to P 1 which xors all the messages it received during the protocol to get the value of
the function. Again, both the correctness and privacy of this protocol are not hard to verify.
In this work we prove that there is a tradeoff between the amount of randomness and the
number of rounds in private computations of xor. For example, we show that while with a single
random bit \Theta(n) rounds are necessary and sufficient 2 , with two random bits O(log n) rounds
suffice. 3 Namely, with a single additional random bit, the number of rounds is significantly
reduced. Additional bits give a much more "modest" saving. More precisely, we prove that with
bits O(log n= log d) rounds suffice
and\Omega\Gammad/3 n=d) rounds are required. Our upper
bound is achieved using a new method that enables us to use linear combinations of random bits
again and again (while preserving the privacy). The lower bounds are proved using combinatorial
arguments, and they are strong in the sense that they also apply to protocols that are allowed to
precisely, dn=2e rounds. This upper bound is achieved by a slight modification of the first protocol
above. Assume, for simplicity, that n is even. At the first round, player Pn sends xn \Phi r to player P 1 , and at
the same time sends r to player Pn\Gamma1 . The players then continue as in the above protocol, forwarding messages
in parallel until the two messages meet. More precisely, in round xors the message it
received with its own input and sends it to player P i and player P n\Gamma(i\Gamma1) xors the message it received with its
own input and sends it to player Pn\Gammai . In round n, player P nreceives two messages and can compute the value
of the function by xoring the two messages together with its own input.
3 All logarithms are base 2, unless otherwise indicated.
make errors, and that they actually show a lower bound on the expected number of rounds. We
also show that if protocols are restricted to certain natural types (that include, in particular, the
protocol that achieves the upper bound) we can even improve the lower bound and show that
\Theta(log n= log d) rounds are necessary and sufficient.
Our lower bound techniques apply not only to the xor function, but in fact give lower bounds
on the number of rounds for any boolean function in terms of the sensitivity of the function.
Namely, we prove that with d - 2 random bits \Omega\Gammats/ S(f)=d) rounds are necessary to privately
compute a boolean function f , whose sensitivity is S(f ). With a single random bit
rounds are necessary.
The question whether private computations in general can be carried out in constant number
of rounds was previously addressed [BB89, BFKR90]. In light of our results, a promising approach
to investigate this question may be by proving that if a constant number of rounds is sufficient
then a large number of random bits is required.
Subsequent to our work, several other works were done regarding the amount of randomness
in privacy. In particular, the amount of randomness required for computing the function xor
t-privately, for t - 2, was studied in [BDPV95, KM96]; in [KOR96] it is shown that the boolean
functions that can be computed privately with a constant number of random bits are exactly the
functions that have linear size boolean circuits.
The rest of the paper is organized as follows: In Section 2 we give some definitions. In Section
3 we give an upper bound on the number of rounds required to privately compute xor. In section
4 we give lower bounds on the number of rounds to privately compute a boolean function, in
terms of its sensitivity. We conclude in Section 5 with lower bounds on the expected number
of rounds in terms of the average sensitivity of the function being computed. The appendix
contains the improved lower bounds for restricted types of protocols.
Preliminaries
We give here a description of the protocols we consider, and define the privacy property of
protocols. More rigorous definitions of the protocols are given in Section 4.1.
1g be any boolean function. A set of n players P i (1 - i - n), each
possessing a single input bit x i (known only to it), collaborate in a protocol to compute the value
of f(~x). The protocol operates in rounds. In each round each player may toss some coins, and
then sends messages to the other players (messages are sent over private channels so that other
than the intended receiver no other player can listen to them). It then receives the messages
sent to it by the other players. In addition, each player at a certain round chooses to output the
value of the function. We assume that each player knows its serial number and the total number
of players n. We may also assume that each player P i is provided with a read-only random tape
R i from which it reads random bits (rather than toss coins).
Each player P i receives during the execution of the protocol a sequence of messages. Let c i
be a random variable of the communication string seen by player P i , and let C i be a particular
communication string seen by P i . Informally, privacy with respect to player P i means that player
anything (in particular, the inputs of the other players) from C i , except what is
implied by its input bit, and the value of the function computed. Formally,
Definition 1: (Privacy) A protocol A for computing a function f is private with respect to
player P i if for any two input vectors ~x and ~y, such that
sequence of messages C i , and for any random tape R i provided to P i ,
where the probability is over the random tapes of all other players.
3 Upper Bound
This section presents a protocol which allows n players to use d - 2 random bits for computing
xor privately. This protocol takes O(log d n) rounds. (For the case similar protocol that
uses dn=2e rounds was already described in the introduction.) All arithmetic operations in this
section are done modulo 2.
Consider the following protocol (which we call the basic protocol): First organize the n players
in a tree. The degree of the root of the tree is d + 1, and the degree of any other internal node is
d (assume for simplicity that n is such that this forms a complete tree). The computation starts
from the leaves and goes towards the root by sending messages (each of them of a single bit) as
follows: Each leaf player P i sends its input bit x i to its parent in the tree. Each internal node,
after receiving messages from its d children, sums them up (modulo 2) together with its input
bit x i and sends the result to its parent. Finally, the root player sums up the d
receives together with its input bit and the result is the output of the protocol.
While a simple induction shows the correctness of this protocol, and it clearly runs in O(log d n)
rounds, it is obvious that it does not maintain the required privacy. The second idea will be to
"mask" each of the messages sent in the basic protocol by an appropriate random bit (constructed
using the d random bits available), in a way that these masks will disappear at the end, and
we will be left with the (un-masked) output. To do so we assign the nodes of the above tree
vectors in GF [2 d ] as follows (the meaning of those vectors will become clear soon): Assign to
the root the vector 0). The children of the root will be assigned d vectors
such that the vectors in any d-size subset of them are linearly independent and the sum of all
the vectors is (for example, the d unit vectors together with the
satisfy these requirements). Finally, in a recursive way, given an internal node which is assigned
a vector v, we assign to its d children d linearly independent vectors whose sum is v (note that
in particular none of these vectors is the ~ 0 vector) 4 .
We now show how to use the vectors we assigned to the nodes, so as to get a private protocol.
We will assume that the random bits b are chosen by some external processor. We will
4 For example, such a collection of d vectors can be constructed as follows: Since v 6= ~ 0 there exists an index i
such that v 1. The first d \Gamma 1 vectors will be the . The last vector
will be
Obviously the sum of these d vectors is v and they are linearly independent.
later see that this assumption can be eliminated easily. Let v be the vector assigned to some player
which is a leaf in the tree. We will give this player a single bit r
the vector consisting of the d random bits, and the product is an inner product (modulo 2). The
players will use the basic protocol, described above, with the modification that a player in a leaf
also xors its message with the bit r v it received (the other players behave exactly as before). We
claim that for every player P i , if in the basic protocol it sends the message m when the input
vector is ~x, then in the modified protocol it sends the message m+ (v i \Delta b), where v i is the vector
assigned to this player. The proof goes by induction: It is trivially true for the leaf players. For
internal nodes the message is calculated by adding the input of the players to the sum of the
incoming messages. Using, the induction hypothesis this sum is
the message received from the k'th child in the basic protocol, and v k is the vector assigned to the
k'th child. Since the construction is such that v i , the vector assigned to P i , satisfies v
then a simple algebraic manipulation proves the induction step. In particular, since the root is
assigned the vector its output equals the output of the basic protocol. Hence, the
correctness follows.
We now prove the privacy property of the protocol. The leaf players do not receive any
message, hence there is nothing to prove. Let P j be an internal node in the tree. Denote by
d the messages it receives. We claim that for every vector
and for any input vector, we have
where the probability is over the random choice of b (note that in this protocol the
players do not make internal random choices). In other words, fix any specific input vector ~x,
then for every vector w, there exists exactly one choice of values for b , such that the
messages that P j receives, when the protocol is executed with input ~x, are the vector w. Denote
by d the vectors corresponding to the d children of P j in the tree, and let
the messages they have to send in the basic protocol given the input vector ~x. As claimed, for
every d, the message that the k-th child sends in the modified protocol can be expressed
as ~r). With this notation, for having s the following linear
system has to be satisfied: 2
are linearly independent, this system has exactly one solution, as needed.
As for the root player the same argument can be applied to any fixed d-size subset of the
receives. This gives us that given any input vector ~x, for all d-size messages
vectors ~
Now take two input vectors ~x and ~y such that x root = y root and such that
by the correctness of the protocol, given a specific d-size messages-vector, the d 1'st message
is the same for ~x and ~y. Thus the privacy property holds with respect to the root too.
Finally, note that we assumed that the random choices were made by some external processor.
However, we can let one of the leaf players randomly choose the bits b supply each
of the leaf players with the appropriate bit r v . As the leaf players only send messages in the
protocol, the special processor that selects the random bits gets no advantage.
Note that if a player is non-honest it can easily prevent the other players from computing the
correct output. However, it cannot get any additional information in the above protocol, since
the only message each player gets after sending its own message is the value of the function. We
have thus proved the following theorem:
Theorem 1: The function xor on n input bits can be computed privately using d - 2 random
bits in O(log n= log d) rounds.
4 Lower Bounds
In this section we prove several lower bounds on the number of rounds required to privately
compute a boolean function, given that the total number of random bits the players can toss
is d. The lower bound is given in terms of the sensitivity of the function. In Section 4.1 we
give some formal definitions. In Section 4.2 we introduce the notion of sensitivity and present
a lemma, central to our proofs, about sensitivity of functions. The proof of the lower bound
appears in Section 4.3.
4.1 Preliminaries
We first give a formal definition for the protocols. A protocol operates in rounds. In each round
each player P i , based on the value of its input bit x i , the values of the messages it received in
previous rounds, and the values of the coins it tossed in previous rounds, tosses a certain number
of additional coins, and sends messages to the other players. The values of these messages may
depend on all of the above, including the coins just tossed by P i . The player may also choose to
output the value of the function as calculated by itself (this is done only once by each player).
Then, each player P i receives the messages sent to it by the other players. To define the protocol
more formally, we give the following definition:
Definition 2: (View)
ffl A time-t partial view of player P i consists of its input bit x i , the messages it has received
in the first t \Gamma 1 rounds, and the coins it tossed in the first t \Gamma 1 rounds. We denote it by
ffl A time-t view of player P i consists of its input bit x i , the messages it has received in the
first rounds, and the coins it tossed in the first t rounds. We denote it by V iew t
Intuitively, the partial view of a player P i in round t determines how many coins (if at all)
toss in round t. Then, its view (which includes those newly tossed coins) determines the
messages P i will send in round t, and whether and which value it will output as the value of f .
The formal definition of a protocol is given below:
Definition 3: A protocol consists of a set of functions R k
which determine how
many coins are tossed by P i in round k, and a set of functions M k
(where M is a finite domain of possible message values), which determine the message sent by
P i to P j at round k.
To quantify the amount of randomness used by a protocol we give the following definition:
Definition 4: A d-random protocol is a protocol such that for any input assignment, the total
number of coins tossed by all players in any execution is at most d.
Note that the definition allows that in different executions different players will toss the coins.
This may depend on both the input of the players, and previous coin tosses. Next, we define the
correctness of a protocol. We usually consider protocols that are always correct; protocols that
are allowed to err will be considered in Section 5.1.
Definition 5: A protocol to compute a function f is a protocol such that for any input vector
~x and every i, player P i always correctly outputs the value of f(~x).
It is sometime convenient to assume that each player P i is provided with a random tape
R i , from which it reads random bits (rather than to assume that the player tosses random
coins). The number of random coins tossed by player P i is thus the rightmost position of this
tape that it reads. We thus denote by R i a specific random tape provided to player P i , and
by ~
the vector or the random tapes of all the players
denote the random variable for these tapes and vector of tapes). Note that if we fix ~
R, we
obtain a deterministic protocol. Furthermore, V iew t
i , for any i and t, is a function of the input
assignment ~x, and the random tapes of the players. We can thus write it as V iew t
denote by T i (~x; ~
R)) the round number in which player P i outputs its result given input assignment
~x and random tapes for the players ~
R.
Definition (Rounds Complexity) An r-round protocol to compute a function f is a protocol
to compute f such that for all i, ~x, ~
R, we have T i (~x; ~
For the purpose of our proofs, we slightly modify our view of the protocol in the following
way. Fix an arbitrary binary encoding for the messages in M . We will consider a protocol where
each player sends instead of a single message from M , a set of boolean messages that represent
the binary encoding of the message to be sent in the original protocol. These messages are sent
"in parallel" in the same round. Henceforth when we refer to messages we refer to these binary
messages. Clearly, the number of rounds remains the same.
4.2 Sensitivity of Functions
In this section we include some definitions related to functions f
finite domain. Then, we present some useful properties related to these definitions.
Definition 7: (Sensitivity)
ffl For a binary vector Y , denote by Y (i) the binary vector obtained from Y by flipping the i'th
entry.
ffl A function f is sensitive to its i-th variable on assignment Y , if f(Y ) 6= f(Y (i) ).
is the set of variables to which the function f is sensitive on assignment Y .
ffl The sensitivity of a function f , denoted S(f), is S(f) 4
ffl The average sensitivity of a function f , denoted AS(f), is the average of jS f (Y )j. That is,
Y 2f0;1g n jS f (Y )j.
ffl The set of variables on which f depends, denoted D(f), is D(f) 4
)g.
we say that f depends on its i-th variable.
The following claim gives a lower bound on the degree of error if we evaluate a function f by
means of another function g, in terms of their average sensitivities. We use this property in our
proofs.
1: Consider any two functions f; for at most
Proof: Consider the n-dimensional hypercube. An f -good edge is an edge ~y) such that
f(~y). By the definitions, the number of f-good edges is exactly 2 n AS(f). Therefore, there
are at least 2 n AS(f)\GammaAS(g)edges which are f-good but not g-good. For each such edge
either f(~x) 6= g(~x) or f(~y) 6= g(~y). Since the degree of each vertex in the hypercube is n there
must be at least 2 n \Delta AS(f)\GammaAS(g)
inputs on which f and g do not agree.
Next, we prove a lemma that bounds the growth of the sensitivity of a combination of func-
tions. This lemma plays a central role in the proofs of our lower bounds, and any improvement
on it will immediately improve our lower bounds.
Lemma 2: Let be a set of m functions
Assume j. Define the function F (Y ) 4
F assumes at
most 2 d different values (different vectors), then the sensitivity of F is at most C \Delta
5 An obvious bound is S(F m. However, for reasons that will become clear soon we are interested in
bounds which are independent of m.
Proof: Let Y be the assignment on which F has the largest sensitivity, i.e. jS f (Y )j - jS f (Y 0 )j
for any assignment Y 0 . Without loss of generality assume that F (Y Consider the
set of neighbors of Y on which F has a value different than (the cardinality of this set
is the sensitivity of F ). There are at most 2 d \Gamma 1 values of F attained on the assignments in
this set. Consider one such value q 2 f0; 1g m . There is at least one index j such that q
and since the sensitivity of f j is at most C, there can be at most C assignments Y (i) with the
value q. We get that the total number of assignments Y (i) for which F has a value other than
is at most C \Delta
4.3 Lower Bound on the Number of Rounds
In this subsection we prove the following theorem.
Theorem 3: Let A be an r-round d-random (d - 2) private protocol to compute a boolean
function f . Then, r
The first step of our proof uses the d-randomness property of the protocol to show that the
number of views a player can see on a fixed input ~x is at most 2 d (over the different random
tapes of all the players). Note that this is not obvious; although only d coins are tossed during
every execution, the identity of the players that toss these coins may depend on the outcome of
previous coin tosses.
Lemma 4: Consider a private d-random protocol to compute a boolean function f . Fix an
input ~x. Let C k
be the communication string seen by player P i up to round k on input ~x
and vector of random tapes ~r. Then, for every player P i , C k
can assume at most 2 d different
values (over the different vectors of random tapes ~r).
Proof: For each execution we can order the coin tosses (i.e., readings from the local random
tapes) according to the rounds of the protocol and within each round according to the index of
the players that toss them. The identity of the player to toss the first coin is fixed by ~x. The
identity of the player to toss any next coin is determined by ~x, and the outcome of the previous
coins. Therefore, the different executions on input ~x can be described using the following binary
tree: In each node of the tree we have a name of a player P j that tosses a coin. The two outgoing
edges from this node, labeled 0 and 1 according to the outcome of the coin, lead to two nodes
labeled P k and P ' respectively (k; ', and j need not be distinct) which is the identity of the player
to toss the next coin. If no additional coin toss occurs, the node is labeled "nil"; there are no
outgoing edges from a nil node. By the d-randomness property of the protocol, the depth of the
above tree is at most d, hence it has at most 2 d root-to-leaf paths. Every possible run of the
protocol is described by one root-to-leaf path. Such a path determines all the messages sent in
the protocol, which player tosses coins and when, and the outcome of these coins. In particular
each path determines for any P i the value of C k
k). Hence, C k
at most 2 d different values.
In the following proof we restrict our attention to a specific deterministic protocols derived
from the original protocol by fixing specific vector of random tapes ~
players. In such a deterministic protocol the views of the players are functions of only the input
assignment ~x.
Lemma 5: Consider a private d-random protocol to compute a boolean function f . Fix random
tapes ~
is the view of player P i at round k on input ~x
and vector of random tapes ~r. Then, for any P i , V iew k
R) can assume at most 2 d+2 different
values (over the values of ~y).
Proof: Partition the input assignments ~x into 4 groups according to the value of x i (0 or 1),
and the value of f(~x) (0 or 1). We argue that the number of different values the view can assume
within each such group is at most 2 d . Fix an input ~x in one of these 4 groups and consider any
other input ~y pertaining to the same group. Recall that C k
R) is the communication string
seen by player P i until round k on input ~y and when the random tapes of the players are ~
R.
If the value of C k
R) is some communication string C i , then by the privacy requirement 6 ,
communication C i must also occur by round k when the input is ~x, and the vector of random
tapes is some ~
(R
Thus, the value of C k
R) must also appear as
some vector of random tapes. However, by Lemma 4, C k
can assume at most
values (over the values of ~r). Thus, C k
R) can assume at most 2 d values over the possible
input assignments that pertain to the same group.
Now, observe that V iew k
determined by the input bit y i , the communication string
and the random tape r i . Therefore, on ~
R and on two input assignments ~y and ~y 0 of the
same group (in particular y
R) then C k
R).
Thus, V iew k
R) can assume at most 2 d different values over the input assignments that pertain
to the same group.
The following lemma gives an upper bound on the sensitivity of the view of a player at a
given round, in terms of the number of random bits and the round number. This will enable us
to give a lower bound on the number of necessary rounds.
Lemma Consider a private d-random protocol to compute a boolean function f , and consider
specific vector of random tapes ~
R, and the deterministic protocol derived by it. Then for every
player
R) (as a function of ~x only) has sensitivity of at most Q(k) 4
Proof: First note that since we fix the random tapes, the views of the players are functions
of the input assignment ~x only. We prove the lemma by induction. For the view of any
player depends only on its single input bit. Thus, the claim is obvious. For k ? 1 assume the
claim holds for any ' ! k. This implies in particular that all messages received by player P i
and included in the view under consideration have sensitivity of at most Q(k \Gamma 1). Clearly the
6 The privacy requirement is defined on the final communication string, but this clearly implies the same
requirement on any prefix of it.
input bit itself has sensitivity 1 which is at most Q(k \Gamma 1). Thus the view under consideration
is composed of bits each having sensitivity at most Q(k \Gamma 1). Moreover, by Lemma 5 the view
can assume at most 2 d+2 values. It follows from Lemma 2 that the sensitivity of the view under
consideration is at most Q(k Q(k). (Note that Lemma 2 allows us to give a
bound which does not depend on the number of messages received by P i .)
We can now give the lower bound on the number of rounds, in terms of the sensitivity of the
function and the number of random bits.
Theorem 7: Given a private d-random protocol (d - 2) to compute a boolean function f ,
consider the deterministic protocol derived from it by any given random tapes ~
R. For any player
there is at least one input assignment ~x such that T i (~x; ~
Proof: Consider a fixed but arbitrary player P i . Denote by t the largest round number in
which outputs a value, i.e.,
R)g. We claim that as long as the sensitivity of
the view of P i does not reach S(f ), there is at least one input assignment for which P i cannot
output the correct value of f . Let Y be an input assignment on which the sensitivity S(f) is
obtained. That is, the value of F (Y ) is different than the value of F on S(f) of Y 's ``neighbors''.
Hence, if the sensitivity of the view of P i is less than S(f ), then the output of P i must be wrong
on either Y or on at least one of these "neighbors" (as the sensitivity of the view is an upper
bound on the sensitivity of the output). Thus, t is such that S(V iew t
6, we get 2 (d+2)(t\Gamma1) - S(f ), i.e., t - log S(f)
1.
This proves Theorem 3; moreover, it shows not only that there is an input assignment ~x and
random tapes ~
R for which the protocol runs "for a long time", but also that for each vector of
random tapes ~
R there is such input assignment. The following corollary follows for the function
xor (using the fact that
Corollary 8: Let A be an r-round d-random private protocol (d - 2) to compute xor of n bits.
4.3.1 Lower Bound for a Single Random Bit
For the case of a single random bit (d = 1), we have the following lower bound:
Theorem 9: Let A be an r-round 1-random private protocol to compute a boolean function f .
To prove the theorem, we restrict our attention to one of the two deterministic protocols
derived from the original protocol by a fixing the value of the random bit 7 . The messages and
views in this protocol are functions of the input vector, ~x, only. Let Y be an assignment on
which S(f ), the sensitivity of f , is obtained. For a given function m, a variables x j is called
good for m on Y if both m and f are sensitive to x j on Y . We denote by Gm (Y ) the set of good
variables on Y , i.e., Gm (Y ) 4
first prove the following two lemmas:
7 We let the identity of the player that tosses this coin to possibly depend on the input ~x. However note that
if we want that the privacy and 1-randomness properties hold, this cannot be the case.
Lemma 10: Consider any player P i . Denote by m 1 a message that P i receives such that
1. Then for any other message m 2 received by P i such that jG m 2
either (a) Gm 1
or (b) jG m 1
Proof: Assume towards a contradiction, that both (a) and (b) do not hold. First, since
are two variables x k 2 Gm 1
such that k 6= i and ' 6= i. Moreover, by the assumption that (a) does not hold, we can assume
without loss of generality (as to the names of m 1 and
By the assumption that (b) does not hold, there is a variable x j (j 6= i) such that f is sensitive
to x j on Y , but both m 1 and m 2 are not sensitive to x j on Y . Now consider the following three
input assignments:
Consider V iew i on the above 3 inputs and assume, without loss of generality, that m 1 (Y
are not sensitive to x j on Y , then m 1 (Y (j)
sensitive to x k on Y , then m 1 (Y sensitive
to x ' on Y , but m 1 is not, then m 1 (Y (')
different values for Y 0 , Y 1 , and Y 2 . The function f is sensitive on Y to all of j; k and ', therefore,
is equal in all three assignments. However, in the proof of Lemma
5, it is shown that the number of values of V iew i corresponding to inputs with the same value
of f and the same value of x i is at most 2
The following lemma gives an upper bound on the sensitivity of the view of the player in
terms of the round number. We then use this lemma to give a lower bound on the number of
necessary rounds.
Lemma 11: Let t - (S(f)\Gamma1)=2 be a round number and P i be any player. Then, jG V iew t
t.
Proof: We prove the claim by induction on t. For
getting any messages, the view depends only on x i ). For assume the claim
holds for any k ! t. Denote by M the set of messages received by P i and included in the view
under consideration. Clearly G V iew t
There could be one of three
cases:
1. For any message In this case the claim clearly holds.
2. Any two messages , such that jG m 1
g. It follows that jG V iew t
by the induction hypothesis jG
t, then jG V iew t
t.
3. There are two messages , such that jG m 1
but Gm 1
g. By Lemma 10, jG m 1
and (without loss of
This contradicts the induction
hypothesis as received in some round k ! t - (S(f) \Gamma 1)=2, and therefore generated
by a view of round k. By the induction hypothesis jG
We can now give the proof of Theorem 9.
Proof of Theorem 9. Consider any player P i . Denote by t the largest round number in which
outputs a value, i.e. 0)g. As in the proof of Theorem 7, it must be that
For the function xor we have the following corollary.
Corollary 12: Let A be an r-round 1-random private protocol to compute xor of n bits. Then
5 Lower Bounds on the Expected Number of Rounds
As the protocols we consider are randomized, it is possible that for the same input ~x, different
random tapes for the players will result in executions that run for different number of rounds.
Hence, it is natural to consider not only the worst case running time but also the expected running
time. Usually, saying that a protocol has expected running time r means that for every input ~x
the expected time until all players finish the execution is bounded by r (where the expectation is
over the choices of the random tapes of the players). Here we consider a weaker definition, which
requires only the existence of a player i whose expected running time is bounded by r. As we are
proving a lower bound, this only makes our result stronger: It would mean that for every player
there is an input assignment for which the expected running time is high. Note that it is not
necessarily the case that the first player that computes the value of the function can announce
this value (and thus all players compute the value within one round). The reason is that the fact
that a certain player computes the function at a certain round may reveal some information on
the inputs, and hence such announcing may violate the privacy requirement (see [CGK90]). We
first define the expected rounds complexity of a protocol.
Definition 8: (Expected Rounds Complexity) An expected r-round protocol to compute
a function f is a protocol to compute f such that there exists a player P i such that for all ~x,
The lower bound that we prove in this section is in terms of the average sensitivity of the
computed function. In particular, we prove
an\Omega\Gamma/28 n=d) lower bound on the expected number
of rounds required by protocols that privately compute xor of n bits. We will prove the following
theorem:
Theorem 13: Let f be a boolean function and let A be an expected r-round d-random private
protocol (d - 2) to compute the function f . Then,
To prove the theorem we consider a protocol A and fix any player P i . We say that the
protocol is late on input ~x and vector of random tapes ~
1. We define
to be 1 if and only if the protocol is late on ~x and ~r. For the
purpose of our proofs in this section we define a uniform distribution on the 2 n input assignments
(this is not to say that the input are actually drawn by such distribution). Moreover, note that
the domain of vectors of random tapes is enumerable.
We first show that for any deterministic protocol derived from a private protocol to compute
f , not only there is at least one input on which the protocol is late, but that this happens for a
large fraction of the inputs.
Lemma 14: Consider a player P i and any fixed vector of random tapes ~
Then
AS(f)
Proof: Consider the views of P
given the vector of random tapes ~
R. For any round
t such that t ! log AS(f)
function g computed from such a view can have at most the same sensitivity, and thus clearly an
average sensitivity of at most
AS(f). By Claim 1, such a function g can have the correct value
for the function f for at most 2 n
AS(f)
assignments. Since we assume that A
is correct for all input assignments, it follows that at least 2 n AS(f)\Gamma
AS(f)
input assignments are
late.
We can now give a lower bound on the expected number of rounds.
Lemma 15: Consider a player P i . There is at least one input assignment ~x for which
AS(f)
log AS(f)
Proof: By Lemma 14, E ~r;~x [L(~x; ~r)] - AS(f)\Gamma
AS(f)
. Hence, there is at least one input assignment
~x for which E ~r [L(~x; ~r)] - AS(f)\Gamma
AS(f)
. For such ~x we get
AS(f)
log AS(f)
as needed.
Theorem 13 follows from the above lemma. The following corollary applies to the function
xor.
Corollary 16: Let A be an expected r-round d-random private protocol (d - 2) to compute
xor of n bits. Then, r
Proof: Follows from Theorem 13 and the fact that
5.1 Weakly Correct Protocols
In this section we consider protocols that are allowed to make a certain amount of errors. Given
a protocol A, denote by A i (~x; ~r) the output of the protocol in player P i , given input assignment
~x and vector of random tape
Definition 9: For ffi)-correct protocol to compute a function f is a protocol that
for every player P i and every input vector ~x satisfies P r ~r [A i (~x;
Note that while designing a protocol one usually wants a stronger requirement; that is, with high
probability all players compute the correct value. With the above definition, it is possible that
in every execution of the protocol at least one of the players is wrong. However, as our aim now
is to prove a lower bound this weak definition only makes our result stronger.
In the following theorem we give lower bounds on the number of rounds and on the expected
number of rounds for weakly correct protocols.
Theorem 17: Let f be a boolean function.
ffl Let A be a (1 \Gamma ffi)-correct r-round d-random private protocol (d - 2) to compute f . If
AS(f)
then r
AS(f)=d).
ffl Let A be a expected r-round d-random private protocol (d - 2) to compute
f . Then
AS(f)
Proof: We first prove the lower bound on the number of rounds, and then turn our attention
to the expected number of rounds. The correctness requirement implies that for any player P i ,
This implies that there exists a vector of random tapes ~
R
such that for at least 2 n (1 \Gamma ffi) input assignments ~x, A i (~x; ~
As in the proof of Lemma
14 (using Claim 1), it follows that before round number log AS(f)
1, the protocol can be correct
on at most 2 n
AS(f)
inputs (with random tapes ~
R). Since we require that at least
are correct, we have that at least
AS(f)
AS(f)
inputs are late. To get a lower bound on r for an r-round protocol, it is sufficient to have a single
input vector ~x such that the execution on (~x; ~
R) is "long". For this, note that if
AS(f)
then (for random tapes ~
R) the number of late inputs is greater than 0. This gives us a lower
bound of r =
\Omega\Gamma112 AS(f)=d) for any (1 \Gamma ffi)-correct r-round d-random protocol, with ffi as above.
We now turn to the lower bound on the expected number of rounds of (1 \Gamma ffi)-correct protocols.
Consider a player P i . Define a to be 1 if and only if A i (~x;
Then, the correctness requirement implies that E ~r [G(~x; ~r)] all ~x. It follows that
for any ~
R the probability that ~
ffiis at least 1 \Gamma
2ffi. 8 For any
such vector of random tapes, ~
R, consider the deterministic protocol derived from it. In such a
protocol there are at least
s
AS(f)
AS(f)
s
A
late input assignments; that is, E ~x [L(~x; ~
AS(f)
ffi). Thus
AS(f)
s
It follows that there is at least one input assignment ~x for which
AS(f)
s
which implies that
AS(f)
s
A \Delta
log AS(f)
d
as claimed.
The following gives the lower bounds for the function xor.
Corollary 18: For fixed A be a (1 \Gamma ffi)-correct d-random expected r-round private
protocol to compute xor of n bits. Then r
n=d). (Obviously the same lower bound holds
for r-round protocols.)
Proof: Follows from Theorem 17 and the fact that n. Note that the expression
) is greater than 0 for any ffi ! 1=2 (and sufficiently large n).
. Thus there is at
least one input assignment ~x such that E ~r [G(~x; which is a contradiction to the protocol being
correct.
6 Conclusion
In this paper we initiate the quantitative study of randomness in private computations. As
mentioned in the introduction, our work was already followed by additional work on this topic
[BDPV95, KM96, KOR96].
We give upper bounds and lower bounds on the number of rounds required for computing
xor privately with a given number of random bits. Alternatively, we give bounds on the number
of random bits required for computing xor privately within a given number of rounds. Our lower
bounds extend to other functions in terms of their sensitivity (and average sensitivity).
An obvious open problem is to close the gap between the upper bound and the lower bound
for computing xor using d random bits. One possible way of doing this is to improve the bound
given by Lemma 2.

Acknowledgments

We thank G'abor Tardos for improving the constant and simplifying the
proof of Lemma 2, and Demetrios Achlioptas for his help in simplifying the proof of Lemma 19.
We also thank Benny Chor for useful comments.



--R

"Simple constructions of almost k-wise independent random variables"
"Non-Cryptographic Fault-Tolerant Computing in a Constant Number of Rounds"
"Perfect Privacy for Two-Party Protocols"
"Security with Low Communication Overhead"
"Randomness in Interactive Proofs"
"Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation"
"How to Generate Cryptographically Strong Sequences Of Pseudo-Random Bits"
"On the Dealer's Randomness Required in Secret Sharing Schemes"
"Randomness in Distribution Protocols"
"On the Number of Random Bits in Totally Private Computations"
"Bounds on Tradeoffs between Randomness and Communication Complexity"
"Multiparty Unconditionally Secure Protocols"
"A Zero-One Law for Boolean Privacy"
"A Communication-Privacy Tradeoff for Modular Addition"


"Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity"
"Dispersers, Deterministic Amplification, and Weak Random Sources"
"Communication Complexity of Secure Computation"
"How to Recycle Random Bits"
"(De)randomized Construction of Small Sample Spaces in NC"
"Constructing Small Sample Spaces Satisfying Given Con- straints"
"On Construction of k-wise Independent Random Variables"
"A Time-Randomness Tradeoff for Oblivious Routing"
"Privacy and Communication Complexity"
"Randomness in Private Computations"
"Reducibility and Completeness in Multi-Party Private Computations"
"Characterizing Linear Size Circuits in Terms of Privacy"
"Small-Bias Probability Spaces: Efficient Constructions and Appli- cations"
"Pseudorandom Generator for Space Bounded Computation"
"Memory vs. Randomization in On-Line Algorithms"
"Sample Spaces Uniform on Neighborhoods"
"Random Polynomial Time is Equal to Slightly-Random Polynomial Time"
"Theory and Applications of Trapdoor Functions"
"Simulating BPP Using a General Weak Random Source"
--TR

--CTR
Balogh , Jnos A. Csirik , Yuval Ishai , Eyal Kushilevitz, Private computation using a PEZ dispenser, Theoretical Computer Science, v.306 n.1-3, p.69-84, 5 September
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
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, 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
lower bounds;randomness;private distributed computations;sensitivity