Reducibility and Completeness in Private Computations.
We define the notions of  reducibility and  completeness in (two-party and multiparty) private computations.  Let g be an n-argument function.  We say that a function f is  reducible to a function g if n honest-but-curious players can compute the function f n-privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these inputs).  We say that g is  complete (for private computations) if  every function f is reducible to g.In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black box available).  Namely, for n-argument boolean functions, the notions of completeness and n-privacy are  complementary.  This characterization provides a huge collection of complete functions  any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are  not complementary.
Introduction
We consider (two party and multi-party) private computations. Quite informally, given an arbitrary n-
argument function f , a t-private protocol should allow n players, each possessing an individual secret input,
to satisfy simultaneously the following two constraints: (1) (Correctness): all players learn the value of
f and (2) (Privacy): no set of at most t (faulty) players learns more about the initial inputs of other
players than is implicitly revealed by f 's output. This problem, also known as secure computation, have
been examined in the literature with two substantially different types of faulty players - malicious (i.e.
Byzantine) players and honest-but-curious players. Below we discuss some known results with respect to
each of these two types of players.
Secure computation for malicious players. Malicious players may deviate from the prescribed
protocol in an arbitrary manner, in order to violate the correctness and privacy constraints. The first
This paper is based on (but not completely covers) two conference papers; a 1991 paper by Kilian [K-91] and a 1994 paper
by Kushilevitz, Micali, and Ostrovsky [KMO-94].
y NEC Research Institute, New Jersey. E-mail: joe@research.nj.nec.com .
z Department of Computer Science, Technion. Research 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 done while the author was at Aiken
Computation Lab., Harvard University, Supported by research contracts ONR-N0001491-J-1981 and NSF-CCR-90-07677.
E-mail: eyalk@cs.technion.ac.il .
x Laboratory for Computer Science, MIT. Supported by NSF Grant CCR-9121466.
- Bell Communication Research, MCC-1C365B 445 South Street Morristown, New Jersey 07960-6438. E-mail:
rafail@bellcore.com.
honest-but-curious players malicious players
computational model [Yao-82, GMW-87]
(assuming trapdoor permutations t -
private-channels model
Figure

1: The number of faulty players, t, tolerable in each of the basic secure computation models (with
general protocols for secure computation were given in [Yao-82, Yao-86] for the two-party case, and by
[GMW-87] for the multi-party case. Other solutions were given in, e.g., [GHY-87, GV-87, BGW-88,
CCD-88, BB-89, RB-89, CKOR-97] based on various assumptions (either intractability assumptions or
physical assumptions such as the existence of private (untappable) communication channels between each
pair of players). These solutions give t-privacy for ndepending on the assumption made.
(See

Figure

1 for a summary of the main results.)
Secure computation for honest-but-curious players. Honest-but-curious players must always
follow the protocol precisely but are allowed to "gossip" afterwards. Namely, some of the players may
put together the information in their possession at the end of the execution in order to infer additional
information about the original individual inputs. It should be realized that in this honest-but-curious model
enforcing the correctness constraint is easy, but enforcing the privacy constraint is hard. The honest-but-
curious scenario is not only interesting on its own (e.g., for modeling security against outside listeners or
against passive adversary that wants to remain undetected); its importance also stems from "compiler-
type" theorems, such as the one proved by [GMW-87] 1 (with further extensions in many subsequent papers,
for example, [BGW-88, CCD-88, RB-89]). This type of theorems provide algorithms for transforming any
t-private protocol with respect to honest-but-curious players into a t 0 -private protocol with respect to
malicious players (t 0 - t). Surprisingly, much of the research efforts were devoted to the more complicated
case of malicious players, while the case of honest players is far from being well understood. In this paper
we examine the latter setting.
Information theoretic privacy. 2 The information theoretic model was first examined by [BGW-88,
CCD-88]. In particular, they prove that every function is dn=2e-private (in the setting of honest-but-
curious players; see Figure 1). The information theoretic model was then the subject of considerable work
(e.g., [CKu-89, BB-89, CGK-90, CGK-92, CFGN-96, KOR-96, HM-97, BW-98]). Particularly, [CKu-89]
characterized the boolean functions for which n-private protocols exist: an n-argument boolean function
f is n-private if and only if it can be represented as
where each f i is boolean. Namely, f is n-private if and only if it is the exclusive-or of n local functions.
An immediate corollary of this is that most boolean functions are not n-private (even with respect to
honest-but-curious players).
Our contribution. We formally define the notion of reducibility among multi-party protocol problems.
We say that f is reducible to g, if there is a protocol that allows the n players to compute the value of f
1 The reader is referred to [G-98] for a fully detailed treatment of the [Yao-82, GMW-87] results.
2 in oppose to computational-privacy
n-privately, in the information theoretic sense, just by repeatedly using a black-box (or a trusted party) for
computing g. That is, in any round of the protocol, the players secretly supply arguments to the black-box
and then the black-box publicly announces the result of operating g on these arguments. We stress that
the only means of communication among the players is by interacting with the black-box (i.e., evaluating
g). For example, it is clear that every function is reducible to itself (all players secretly give their private
inputs to the black-box and it announces the result). Naturally, we can also define the notion of
completeness. A function g is complete if every function f is reducible to g. The importance of this notion
relies on the following observation:
If g is complete, and g can be computed t-privately in some "reasonable" setting 3 (such as
the settings of [GMW-87, BGW-88] etc.), then any function f can be computed t-privately in
the same setting. Moreover, from our construction a stronger result follows: if in addition the
implementation of g is efficient then so is the implementation of f (see below).
The above observation holds since our definition of reduction requires the highest level of privacy (n), the
strongest notion of privacy (information theoretic), a simple use of g (black box), and it avoids making any
(physical or computational) assumptions. Hence the straightforward simulation, in which each invocation
of the black-box for g is replaced by an invocation of a "t-private" protocol for g, works in any "reasonable"
setting (i.e. any setting which is not too weak to prevent simulation) and yields a "t-private" protocol
for f . Previously, there was no easy way to translate protocols from one model (such as the models of
[Yao-82, GMW-87, BGW-88, CCD-88, RB-89, FKN-94]) to other models.
It can be seen that if g is complete then g itself cannot be n-private. The inverse is the less obvious
part: since the definition of completeness requires that the same function g will be used for computing all
functions f , and since the definition of reductions seems very restrictive, it may be somewhat surprising
that complete functions exist at all. Some examples of complete functions implicitly appear in the literature
(without discussing the notions of reducibility and completeness). First such results were shown in [Yao-82,
GMW-87, K-88].
In this work we prove the existence of complete functions for n-private computations. Moreover, while
previous research concentrated on finding a single complete function, our main theorem characterizes all
the boolean functions which are complete:
Main Theorem: For all n - 2, an n-argument boolean function g is complete if and only if g is not n-private.
Our result thus shows a very strong dichotomy: every boolean function g is either "simple enough" so
that it can be computed n-privately (in the information theoretic model), or it is "sufficiently expressive" so
that a black-box for it enables computing any function (not only boolean) n-privately (i.e., g is complete).
We stress that there is no restriction on g, beside being non-n-private boolean function, and that no
relation between the function g and the function f that we wish to compute is assumed. Note that using
the characterization of [CKu-89] it is easy to determine whether a given boolean function g is complete.
That is, a boolean function g is complete if and only if it cannot be represented as
each g i is boolean.
Some features of our result. To prove the completeness of a function g as above, we present an
appropriate construction with the following additional properties:
ffl We consider the most interesting scenario, where both the reduced function, f , and the function g are
n-argument functions (where n is the number of players). This enables us to organize the reduction in
rounds, where in each round each player submits a value of a single argument to g (and the value of
3 A setting consists of defining the type of communication, type of privacy, assumptions made etc.
each argument is supplied by exactly one player). 4 Thus, no player is "excluded" at any round from
the evaluation of g. Our results however remain true even if the number of arguments of g is different
from the number of arguments of f .
ffl Our construction evaluates the n-argument function g only on a constant number of n-tuples (hence,
a partial implementation of g may be sufficient).
ffl When we talk about privacy, we put no computational restrictions on the power of the players; hence
we get information-theoretic privacy. However, when we talk about protocols, we measure their
efficiency in terms of the computational complexity of f (i.e., the size of a circuit that computes f );
and in terms of a parameter k (our protocol allows error probability of 2 \Gamma\Omega\Gamma The protocol we
introduce is efficient (polynomial) in all these measures. 5 We stress, though, that the n-tuples with
which we use the function g are chosen non-uniformly (namely, they are encoded in the protocol) for
the particular choices of g and n (the size of the network). These n-tuples do not depend though
neither on the size of the inputs to the protocol nor on the function f .
Our main theorem gives a full characterization of the boolean functions g which are complete (those
that are not n-private). When non-boolean functions are considered, it turns out that the above simple
characterization is no longer true. That is, we show that there are (non-boolean) functions which are not
n-private, yet are not complete.
Overview of the proof. Our proof goes along the following lines:
1. We define the notion of embedded-OR for two-argument functions and appropriately generalize this
notion to the case of n-argument functions. We then show that if an n-argument function is not
private then it contains an embedded-OR. For the case immediately from the
characterization of [CKu-89]; the case n ? 2 requires some additional technical work.
2. We show how an embedded-OR can be used to implement an Oblivious Transfer (OT) channel/primitive. 6
(It should be emphasized that an OT channel in a multi-party setting has the additional requirement
that listeners do not get any information; we prove however that this property is already implied by
the basic properties of two-party OT). Finally, it follows from the work of [GHY-87, GV-87, K-88,
BG-89, GL-90] that n-private computation of any function f can be implemented given OT channels.
All together, our main theorem follows.
Organization of the paper. In Section 2 we specify our model and provide some necessary definitions.
In Section 3 we prove our main lemma that shows the existence of an embedded-OR in every non n-
private, boolean function; In Section 4 we use the main lemma (i.e., the existence of an embedded-OR)
to implement OT channels between players; In Section 5 we use the construction of OT channels to prove
our main theorem. Finally, Section 6 contains a discussion of the results and some open problems. For
completeness, we include in the appendix a known protocol for private computations using OT channels
(including its formal proof).
Which player submits which argument is a permutation specified by the reduction.
Evaluating g on any assignment is assumed to take a unit time. All other operations (communication, computation steps,
etc.) are measured in the regular way.
6 Oblivious transfer is a protocol for two players: a sender that holds two bit b0 and b1 and a receiver that holds a selection
bit s. At the end of the protocol the receiver gets the bit bs but has no information about the value of the other bit, while
the sender has no information about s.
Model and Definitions
Let f be an n-argument function defined over a finite domain D. Consider a collection of n - 2 synchronous,
computationally unbounded players that communicate using a black-box for g, as described
below. At the beginning of an execution, each player P i has an input x i 2 D. In addition, each player
can flip unbiased and independent random coins. We denote by r i the string of random bits flipped by P i
(sometimes we refer to the string r i as the random input of P i ). The players wish to compute the value
of a function f(x 1 To this end, they use a prescribed protocol F . In the i-th round of the
protocol, every processor P j secretly sends a message m i
j to the black-box g. 7 The protocol F specifies
which argument to the black-box is provided by which player. The black-box then publicly announces the
result of evaluating the function g on the input messages.
Formally, with each round i the protocol associates a permutation - i . The value computed by the
black-box at round i, denoted s i , is s
Each message m i
sent by P j to the
black-box in the i-th round, is determined by its input and the output of the
black-box in previous rounds We say that the protocol F computes the function f if the
last value (or the last sequence of values in the case of non-boolean f) announced by the black-box equals
the value of is a (confidence) parameter and the
probability is over the choice of r
Let F be an n-party protocol, as described above. The communication S(~x; ~r) is the concatenation
of all messages announced by the black-box, while executing F on inputs x inputs
We often consider the communication S while fixing ~x and some of the r i 's; in this case, the
communication should be thought of as a random-variable where each of the r i 's that were not fixed is
chosen according to the corresponding probability distribution. For example, if T is a set of players then
variable describing the communication when each player P i holds input x i , each
player in T holds random input r i , and the random inputs for all players in T are chosen randomly. The
definition of privacy considers the distribution of such random variables.
F be an n-party protocol which computes a function f , and let T ' ng be a
set of players (coalition). We say that coalition T does not learn any additional information from the
execution of F if the following holds: For every two input vectors ~x and ~y that agree on their T entries
(i.e. every choice of random inputs for the coalition's
parties, fr i g i2T , and for every communication S
Informally, this definition implies that for all inputs which "look the same" from the coalition's point
of view (and for which, in particular, f has the same value), the communication also "look the same" (it
is identically distributed). Therefore, by executing F , the coalition T cannot infer any information on the
inputs of T , other than what follows from the inputs of T and the value of the function.
computing f , using a black-box g, is t-private if any coalition T of at most
players does not learn any additional information from the execution of the protocol. A function f is
t-private (with respect to the black-box g) if there exists a t-private protocol that uses the black-box g and
computes f .
be an n-argument function. We say that the black-box g (alternatively, the function
g) is complete if every function f is n-private with respect to the black-box g.
7 Notice that we do not assume private point-to-point communication among players. On the other hand, we do allow
private communication between players and the black-box for computing g.
Oblivious Transfer is a protocol for two players S, the sender , and R, the receiver. It was first defined
by Rabin [R-81] and since then was studied in many works (e.g., [W-83, FMR-85, K-88, IL-89, OVY-91]).
The variant of OT protocol that we use here, which is often referred to as
originally defined in
[EGL-85]. It was shown equivalent to other notions of OT (see, for example [R-81, EGL-85, BCR-86, B-86,
C-87, K-88, CK-88]). The formalization of OT that we give is in terms of the probability distribution of
the communication transcripts between the two players:
Definition 4 Oblivious Transfer (OT): Let k be a (confidence) parameter. The sender S initially has two
bits b 0 and b 1 and the receiver R has a selection bit c. After the protocol completion the following holds:
Correctness: Receiver R gets the value of b c with probability greater than 1\Gamma2 \Gamma\Omega\Gamma where the probability
is taken over the coin-tosses of S and R. More formally, let r S , r R 2 f0; 1g poly(k) be the random tapes of
S and R respectively, and denote the communication string by comm(fb
(Again, when one (or both) of r S ; r R is unspecified then comm becomes a random variable.) Then, for
all k and for all c; b the following holds:
Pr r S ;r R
(R(c;
(R(c; r R ; comm) denotes the output of receiver R when it has a selection bit c, random input r R and
the communication in the protocol is comm.)
Sender's Privacy: Receiver R does not get any information about b 1\Gammac . (In other words, R has the
"same view" in the case where b and in the case where b 1). Formally, for all k, for all
c; b c 2 f0; 1g, for all r R and for all communication comm:
Pr r S
Receiver's Privacy: Sender S does not get any information about c. (In other words, S has the "same
view" in the case where and in the case where c = 1). Formally, for all k, for all b
for all r S and for all communication comm:
Pr r R
REMARK: We emphasize that both S and R are honest (but curious) and assumed to follow the
protocol. When OT is defined with respect to cheating players, it is usually allowed that with probability
information will leak. This however is not needed for honest players.
3 A New Characterization of n-private Boolean Functions
In this section we prove our main lemma which establishes a new combinatorial characterization of the
family of n-private boolean functions. First, we define what it means for a two-argument boolean function
to have an "embedded-OR" and use [CKu-89] to claim that any two-argument boolean function which is
not 1-private contains an embedded-OR. We then generalize the definition and the claim to multi-argument
functions in the appropriate way.
Definition 5 We say that a two-argument function h contains an embedded-OR if there exist inputs
and an output value oe such that h(x 1
Definition 6 We say that an n-argument (n - contains an embedded-OR if there exist
jg, such that the two-argument function
contains an embedded-OR.
The following facts are proven in [CKu-89] (or follow trivially from it):
1. An n-argument boolean function is dn=2e-private if and only if it can be written as f(x
2. A two-argument boolean function f is not 1-private if and only if it contains an embedded-OR.
3. If an n-argument boolean function is dn=2e-private then it is n-private.
4. An n-argument boolean function f is dn=2e-private if and only if in every partition of the indices
ng into two sets
S, each of size at most dn=2e, the two-argument boolean function f S
defined by
is 1-private.
Our main lemma extends Fact 2 above to the case of multi-argument functions.
boolean, n-argument function. The function g is
not dn=2e-private if and only if it contains an embedded-OR.
Proof: Clearly, if g contains an embedded-OR then there is a partition of the indices, as in Fact 4, such
that the corresponding two-argument function g S contains an embedded-OR (e.g., if are the indices
guaranteed by Definition 6 then include the index i in S, the index j in -
S, and partition the other
indices arbitrarily into two halves between S and -
S). Hence, g S is not 1-private and so, by Fact 4, g is not
dn=2e-private.
For the other direction, since g is not dn=2e-private then, again by Fact 4, there is a partition
S of
the indices ng such that g S is not 1-private. For simplicity of notations, we assume that n is even
and that n=2g. By Fact 2, the two-argument function g S contains an embedded-OR. Hence,
by Definition 5, there exist inputs u; v; w; z and a value oe 2 f0; 1g which form the following structure:
where u 6= v and w 6= z. To complete the proof, we will show below that it is possible to choose these
four inputs so that u i 6= v i for exactly one coordinate i and w j 6= z j for exactly one coordinate j (this will
show that g satisfies the condition of Definition 6). To this end, we will first show how based on the inputs
above we can find u 0 and v 0 which are different in exactly one coordinate. Then, based on the new u
and a similar argument, we can find w which are different in exactly one coordinate. All this process is
done in a way that maintains the OR-like structure, and therefore, by using the above values of i; j, fixing
all the other arguments in S to u 0
k and all the other arguments in -
S to w 0
k , we get that g itself
contains an embedded-OR.
ng be the set of indices on which u and v disagree (i.e., indices k such that u k 6= v k ).
Define the following sets of vectors: Tm is the set of all vectors that can be obtained from the vector u by
replacing the value u k in exactly m coordinates from L (in which v k 6= u k ) by the value v k . In particular,
fvg. In addition, we define the following two sets of vectors:
and
where w and z are the specific vectors we choose above. In particular, we have
We now claim that there must exist Namely, the vector u 0 is in X 1 , the vector v 0 is in
differ in exactly one coordinate. Suppose, towards a contradiction, that this is not true (i.e.,
no such We will show that this implies that Tm ' X 1 , for all contradicting the
fact that v which is in T jLj belongs to X 2 . The proof is by induction. It is true for contains
only u which is in X 1 . Suppose the induction hypothesis holds for m. That is, Tm ' X 1 . For each vector
x in Tm+1 , there is a vector in Tm which differs from x in exactly one coordinate. Since we assumed that
as above do not exist, this immediately implies that x is also in X 1 hence Tm+1 ' X 1 , as needed.
Therefore, we reached a contradiction which implies the existence of u That is, we found
that differ in a single index i (i.e., u 0
and such that u still form an OR-like structure:
oe
A similar argument shows the existence of w that differ in a single index j and such that the vectors
form an OR-like structure:
oe
This shows that g contains an embedded-OR (with indices required by Definition 6). 2
Constructing Embedded Oblivious Transfer
The first, very simple, observation is that given a black-box for a function g that contains an embedded-
OR, we can actually compute the OR of two bits. That is, suppose that the n players wish to compute
is a bit held by player P k and b ' is a bit held by player P ' . Let
the indices and inputs as guaranteed by Definitions 5 and 6. Then, player P k will provide the black box
with the i-th argument which is x b k
(i.e., if b then the argument provided by P k is x 0 and if b
then the argument is x 1 ) and player P ' will provide the black box with the j-th argument which is x b '
The other players will provide the fixed values a in an
arbitrary order. The black-box will answer with the value
which is oe if OR(b different than oe if OR(b Hence, we showed how to compute
Our main goal in this section is to show how, based on a black-box that can compute OR we can
implement an Oblivious Transfer (OT) protocol. We start with the two-party case
proceed to the general case which builds upon the two-party case.
4.1 The Two-Party Case
In this section we show how to implement a two-party OT protocol. We start by implementing a variant
of OT, called random OT (or ROT for short), which is different than the standard OT (i.e.,
In a
ROT protocol the sender S has a bit s to be sent. At the end of the protocol, the receiver R gets a bit
s 0 such that with probability 1=2 the bit s 0 equals s and with probability 1=2 the bit s 0 is random. The
receiver knows which of the two cases happened and the sender has no idea which is the case. We start
with a formal definition of the ROT primitive:
Definition 7 Random Oblivious Transfer (ROT): Let k be a (confidence) parameter. The sender S initially
has a single input bit s (and the receiver has no input). After the protocol completion the following
holds:
Correctness: With probability greater than outputs a pair of bits
is referred to as the indicator (otherwise R outputs fail). (As usual, the probability is taken over
the coin-tosses of S and R, i.e., r S , r R 2 f0; 1g poly(k) .) Moreover, if the output of R satisfies
(i.e.,
Pr r S ;r R
Sender's Privacy: The probability that R outputs a pair exactly 1=2. That is,
Pr r S ;r R
Receiver's Privacy: Sender S does not get any information about I. (In other words, S has the "same
view" in the case where I = 0 and in the case where I = 1). Formally, for all k, for all s 2 f0; 1g, for
all r S and for all communication comm:
Pr r R (comm(s; r
Transformations of ROT protocols to
are well-known [C-87]. 8 Our ROT protocol is
implemented as follows:
8 Assume that the sender, S, has two bits b0 ; b1 and the receiver, R, has a selection bit c. The players S and R repeat the
following for at most times: at each time S tries to send to R a pair of random bits (s1 ; s2) using two invocations
of ROT. If in both trials the receiver gets the actual bit or in both trials he gets a random bit then they try for another time.
If the receiver got exactly one of s1 and s2 he sends the sender a permutation of the indices - (i.e., either (1; 2) or (2; 1)) such
that s -(c) is known to him. The sender replies with b1 \Phi s . The receiver can now retrieve the bit bc and knows
nothing about the other bit. The sender, by observing - learns nothing about c (since he does not know from the invocation
of the ROT protocols in which invocation the receiver got the actual bit and in which he got a random bit). Thus, we get a
protocol based on the ROT protocol.
a. The sender, S, and the receiver, R, repeat the following until c (and at most
S chooses a pair (a 1 ; a 2 ) out of the two pairs f(1; 0); (0; 1)g, each with probability 1=2.
R chooses a pair (b out of the three pairs f(1; 0); (0; 1); (1; 1)g, each with probability 1=3.
S and R compute (using the black-box) c
b. If c to R. The receiver R outputs
outputs in addition, R outputs s
c. If in all m times no choices (a 1 ; a 2 ) and (b are such that c the protocol halts and R
outputs fail.
To analyze the protocol we observe the following properties of it:
1. If (b This happens in two of the six choices of (a 1 ; a 2 ) and
(b In each of the other four choices we get c Therefore,
the probability of failure in exponentially small.
2. Conditioned on the case c out of the
four remaining cases) and (b
3. In case that (b 1
In this case R outputs I = 1, as needed.
In case that (b 1 1), each of the two choices of (a 1 ; a 2 ) is equally likely and therefore a 1 and
hence also w and s 0 are random (i.e., each has the value 0 with probability 1=2 and the value 1 with
probability 1=2). In this case R outputs I = 0, as needed.
4. As argued in 3, if the protocol does not fail then R knows the "correct" value of I (since he knows
the values of b The sender, on the other hand, based on (a 1 ; a 2 ) cannot know which
of the two equally-probable events, (b happened and therefore he
sees the same view whether we are in the case I = 1 or in the case I = 0.
Properties 1 and 3 above imply the correctness of the ROT protocol while properties 2 and 4 imply the
sender's privacy and receiver's privacy (respectively). Hence, combining the above construction (including
the transformation of the ROT protocol to a
Lemma 2 An OT-channel between two players is realizable given a black-box g, for any non-2-private
function g.
4.2 The Multi-Party Case (n ?
We have shown in our main lemma (Lemma 1) that any non n-private function g contains an embedded-
OR. Thus, as explained above, we can use the black-box for g to compute the OR of two bits held by
two players P k and P ' (where the other players assist by specifying the fixed arguments given by
our main lemma). Then, based on the ability to compute OR, we showed in Section 4.1 above how any
two players can implement an OT channel between them in a way that satisfies the properties of OT (in
particular, the privacy of the sender and the receiver with respect to each other). However, there is a
subtle difficulty in implementing a private OT-channel in a multi-player system which we must address:
beside the usual properties of an OT channel (as specified by Definition 4), we should guarantee that the
information transmitted between the two owners of the channel will not be revealed to potential listeners
(i.e., the other players). If the OT channel is implemented "physically" then clearly no information
is revealed to the listeners. However, since we implement OT using a black-box to some function g, which
publicly announces each of its outcomes, we must also prove that this reveals no information to the listeners.
That is, the communication comm should be distributed in the same way, for all values of b
The following lemma shows that the security of the OT protocol with respect to listeners is, in fact,
already guaranteed by the basic properties of the OT protocol; namely, the security of the protocol with
respect to both the receiver and the sender.
Lemma 3 Consider any (two-player) OT protocol. For every possible communication comm, the probability
Pr r S ;r R
is the same for all values b 0 and b 1 for the sender and
c for the receiver. (In other words, a listener sees the same probability distribution of communications no
matter what are the inputs held by the sender and the receiver in the OT protocol.)
Proof: Consider the following 8 probabilities corresponding to all possible values of b
1. Pr r S ;r R
2. Pr r S ;r R
3. Pr r S ;r R
4. Pr r S ;r R
5. Pr r S ;r R
7. Pr r S ;r R
8. Pr r S ;r R
The receiver's privacy property implies that the terms (1) and (2) are equal, (3) and (4) are equal, (5) and
are equal, and (7) and (8) are equal. The sender's privacy property implies that the terms (1) and (3)
are equal, (5) and (7) are equal, (2) and (6) are equal, and (4) and (8) are equal. All together, we get that
all 8 probabilities are equal, as desired. 2
5 A Completeness Theorem for Multi-Party Boolean Black-Box Reduction

In this section we state the main theorem and provide its proof. It is based on a protocol that can tolerate
honest-but-curious players, assuming the existence of an OT-channel between each pair of players.
Such protocols appear in [GHY-87, GV-87, K-88, BG-89, GL-90] (these works deal also with malicious
players). That is, by these works we get the following lemma (for self-containment, both a protocol and
its proof of security appear in the appendix):
Lemma 4 Given OT channels between each pair of players, any n-argument function f can be computed
n-privately (in time polynomial in the size of a boolean circuit for f ).
We are now ready to state our main theorem:
Theorem 1 (MAIN:) Let n - 2 and let g be an n-argument boolean function. The function g is complete
if and only if it is not n-private.
Proof:
First, we show that any complete g cannot be n-private. Towards the contradiction let us assume
that there exists such a function g which is n-private and complete. This implies that all functions are
n-private (as instead of using the black-box g the players can evaluate g by using the n-private protocol for
g). This however contradicts the results of [BGW-88, CKu-89] that show the existence of functions which
are not n-private.
Next (and this is where the bulk of the work is) we show how to compute any function n-privately,
given a black-box for any g which is not n-private. Recall that there exists a protocol that can tolerate
honest-but-curious players, assuming the existence of OT-channels (Lemma 4). Also, we have shown
how a black-box, computing any non-private function, can be used to simulate OT channels (Lemma 2
and 3). Combining all together we get the result. 2
The theorem implies that "most" boolean functions are complete. That is, any boolean function which is
not of the XOR-form of [CKu-89] is complete.
6 Conclusions and Further Extensions
6.1 Non-boolean Functions
We have shown that any non-n-private boolean function g is complete. Namely, a black-box for such a
function g can be used for computing any function f n-privately. Finally, let us briefly turn our attention
to non-boolean functions. First, we emphasize that if a function g contains an embedded-OR then it is
still complete even if it is non-boolean (all the arguments go through as they are; in particular note that
Definitions 5 and 6 of embedded-OR apply for the non-boolean case as well). For the non-boolean case,
we can state the following proposition:
Proposition 2 For every n - 2 there exists a (non-boolean) n-argument function g which is not n-private,
yet such that g is not complete.
Proof: The proof for 2-argument g is as follows: there are non-private two-argument functions which do
not contain an embedded OR. Examples of such functions were shown in [Ku-89] (see Figure 2). We now
show that with no embedded-OR one cannot compute the OR function. Assume, towards a contradiction,
that there is some two-argument function f which does not have an embedded-OR, yet it could be used to
compute the OR function. Since f can be used to compute the OR function, we can use it to implement
OT (Lemma 2). Hence, there exists an implementation of OT based on some f which does not have an
embedded-OR. However, [K-91] has shown that for two-argument functions, only the ones that contain an
embedded-OR, can be used to implement OT, deriving a contradiction.
For n-argument functions, notice that if we define a function g (on n arguments) to depend only on its
first two arguments, we are back to the 2-argument case, as the resulting function is not n-private. 2
To conclude, we have shown that for boolean case, the notions of completeness and privacy are exactly
complementary , while for the non-boolean case they are not .

Figure

2: A non-private function which does not contain an embedded-OR
6.2 Additional Remarks
In this section, we briefly discuss some possible extensions and easy generalizations of our results.
The first issue that we address is the need for the protocol to specify the permutation - i that is used in
each round i (for mapping the players to the arguments for the black-box g). Note that in our construction,
we use the black-box only for computing the OR function on two arguments. For this, we need to map
some two players P k and P ' , holding these two arguments, to the special coordinates i; j, guaranteed by
the definition of embedded-OR. Therefore, without loss of generality, the sequence of permutations can
be made oblivious (i.e., independent of the function f computed) at a price of O(n 2 ) multiplicative factor
to the rounds (and time). Moreover, at a price of O(n 4 ) the sequence of permutations can even be made
independent of the non-n-private function g. Finally, note that if g is a symmetric function (which is often
the "interesting" case), then there is no need to permute the inputs to g.
Next, we recall the assumption that the number of arguments of g is the same as the number of
arguments of f (i.e., n). Again, it follows from our constructions that this is not essential to any of our
results: all that is needed is the ability for the two players that wish to compute the OR function
in a certain step, to do so by providing the two distinguished arguments and all the other (fixed)
arguments can be provided by arbitrary players (e.g., all of them by P 1 ).
In our definitions we require perfect privacy. That is, we require that the two distributions in Definition 1
are identical. One can relax this definition of privacy to require only statistical indistinguishability of
distributions or only computational indistinguishability of distributions. For these definitions we refer the
reader to the papers mentioned in the introduction. Note that if f can be computed "privately", under any
of these notions, using a black-box for g and if g can be computed t-privately, under any of these notions,
then also the function f can be computed t-privately, under the appropriate notion of privacy (i.e., the
weaker among the two).
Finally, we note that the negative result of [CKu-89] allows a probability of error; hence, even a weaker
notion of reduction that allows for errors in computing f does not change the family of complete functions.
This impossibility result (i.e., first direction of the main theorem) still holds even if we allow the players
to communicate not only using the black-box but also using other types of communication such as point-
to-point communication channels.
6.3 Open Questions
The above results can be easily extended to show that any boolean g which is complete can also be used for a
private computation of any multi-output function f (i.e., a function whose output is an n-tuple (y
where y i is the output that should be given to P i ). This is so, because Lemma 4 still holds. On the other
hand, it is an interesting question to characterize the multi-output functions g that are complete (even in
the boolean case where each output of g is in f0; 1g).
It is not clear how to extend the model and the results to the case of malicious players in its full
generality. Notice, however, that under the appropriate definition of the model, if we are given as a black-box
the two-argument OR function we can still implement private channels (see [KMO-94] for details),
and hence by [BGW-88, CCD-88] can implement any f , n=3-privately with respect to malicious players.
Suppose that we relax the notion of privacy to computational-privacy (as in [Yao-82, GMW-87]).
In such a case, any computationally n-private implementation of an (information-theoretically) non-n-
private (equivalently, complete) boolean function g implies the existence of a one-way function. This is
so, since we have shown that such an implementation of g implies an implementation of OT, which in
turn implies the existence of a one-way function by [IL-89]. However, the best known implementation of
such protocols, for a function g as above, requires trapdoor one-way permutations [GMW-87]. It is an
important question whether there exists an implementation based on a one-way function (or permutation)
for functions without trap-door. This question has only some partial answers. In particular, when one of
the players has super-polynomial power, this is possible [OVY-91]. However, if we focus on polynomial-time
players and protocols, then the result of our paper together with the work of [IR-89] implies that for
all complete functions, if we use only black-box reductions, this is as difficult as separating P from NP .
Thus, using black-box reductions, complete functions seem to be hard to implement (with computational
privacy) without a trapdoor property. Notice, however, that for non-boolean functions we have shown that
there are functions which are not n-private and not complete. It is not known even if these functions can
be implemented without using trapdoor, although the results of [IR-89] do not apply to this case.

Acknowledgments

We wish to thank Oded Goldreich for helpful discussions and very useful com-
ments. We thank Mihir Bellare for pointing out to us in 1991 that the works of Chor, Kushilevitz and
Kilian are complementary and thus imply a special case of our general result. Finally, we thank Amos
Beimel for helpful comments.



--R


Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation
Applications of Oblivious Transfer
Minimum Disclosure Proofs of Knowledge
Information Theoretic Reductions among Disclosure Problems
Multiparty Computation with Faulty Majority

Adaptively Secure Multi-Party Computation

Multiparty Unconditionally Secure Protocols

Private Computations Over the Integers
On the Structure of the Privacy Hierarchy
Equivalence between Two Flavors of Oblivious Transfer

A Randomized Protocol for Signing Contracts
A minimal model for secure computation

Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model
Secure Multi-Party Computation
How to Play any Mental Game
How to Solve any Protocol Problem - An efficiency Improvement
Fair Computation of General Functions in Presence of Immoral Majority
The Knowledge Complexity of Interactive Proof- Systems
Complete Characterization of Adversaries Tolerable in Secure Multi-Party Computation

On the Limitations of certain One-Way Permutations
Basing Cryptography on Oblivious Transfer
Completeness Theorem for Two-party Secure Computation
Privacy and Communication Complexity
Characterizing Linear Size Circuits in Terms of Privacy
Amortizing Randomness in Private Multiparty Computations
Reducibility and Completeness In Multi-Party Private Computations
A Randomness-Rounds Tradeoff in Private Computation
Fair Games Against an All-Powerful Adversary
Verifiable Secret Sharing and Multiparty Protocols with Honest Ma- jority
How to Exchange Secrets by Oblivious Transfer

Protocols for Secure Computations

--TR

--CTR
Danny Harnik , Moni Naor , Omer Reingold , Alon Rosen, Completeness in two-party secure computation: a computational view, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
reducibility;oblivious-transfer;completeness;private computation