T h e R o u n d C o m p l e x i t y of S e c u r e P r o t o c o l s(Extended Abstract)

Donald Beaver*
Harvard University

Silvio Micali t

Phillip Rogaway t

MIT

MIT

Abstractsome components in the system fail. However, even if
one is solely interested in correctness, privacy helps toachieve it most strongly: if one wants to maliciously influence the outcome of an election, say, it is helpful toknow who plans to vote for whom. Second, secure function computation is central to protocol design, as thecorrectness and privacy of any protocol can be reduced
to it. Here, as people m a y be behind their computers,
correctness and privacy are equally important.
The first general solution for secure function evaluation was found by Yao [Ya86] for the two-party case,and by Goldreich, Micali and Wigderson [GMW87] forthe multiparty case. Many other protocols for themultiparty case have been found since. In particular, the protocols of Ben-Or, Goldwasser and Wigderson [BGW88], Chaum, Cr~peau and Damg£rd[CCD88],
and Rabin and Ben-Or [RB89], succeed in defeating theinfluence of bad players without making use of cryptography, assuming that the privacy of communication among players is guaranteed. Other general protocols with different and interesting properties include[GV87, CR87, CDG87, GHY87, Be88, BG89, Ch89].

In a network of n players, each player i having private
input zi, we show how the players can collaboratively
evaluate a function f ( z l , . . . , zn) in a way that does notcompromise the privacy of the players' inputs, and yet
requires only a constant number of rounds of interaction.
The underlying model of computation is a complete
network of private channels, with broadcast, and a majority of the players must behave honestly. Our solution
assumes the existence of a one-way function.

1

Introduction

Secure .function evaluation. Assume we have n parties, 1 , . . . , n; each p a r t y i has a private input xi known
only to him. The parties want to correctly evaluate agiven function f on their inputs, that is to computey = f ( x l , ...,z,~), while maintaining the privacy of
their own inputs. T h a t is, they do not want to reveal more than the value y implicitly reveals. Securefunction evaluation consists of distributively evaluating
a function so as to satisfy both the correctness and privacy constraints. This task is made particularly difficult
by the fact that some of the players m a y be maliciously
faulty and try to cooperate in order to disrupt the correctness and the privacy of the computation.
Secure function evaluation arises in two main settings.
First, in fault-tolerant computation. In this setting cor:ectness is the main issue: we insist that the values a
distributed system returns are correct, no matter how

The G M W p a r a d i g m . In the above multiparty protocols, the underlying notions of security are often quite
different, and so are the assumed communication models. Nonetheless, all of them follow the same paradigmof [GMW87] that we now describe.
There are three stages. In the first stage, each player

shares the bits of his private input. Sharing a bit b
entails breaking b into n "shares," bl, ..., bn, and giving
share bi to player i. For some p a r a m e t e r t, t < n/2,
we require that no t players get information about bfrom their pieces; and yet, b is recoverable, and is known
to be recoverable, given the cooperation of the n - t
good players--even if the t bad players try to obstruct
b's recovery, or try to alter the recovered value. The
value b which a player has effectively "committed to"is independent of the values that honest players may
concurrently be committing to.
After the sharing stage, a computation stage follows,in which each player, given his own shares of xl, . . . , x,~,computes his own share of f ( z t , . . . , z,~). To accomplish
this, the function f to be evaluated is represented by a

*Aiken Computation Laboratory, Harvard University, Cambridge, MA 02138. Supported in part by NSF grant CCR-870-t513.
tMIT Laboratory for Computer Science, 545 Technology~;quare, Cambridge, MA 02139. Supported by A R t grant DAAL
03-86-K-0171 and NSF grant CCR-8719689.

Permissionto copywithout fee all or part of this materialis granted provided that the copies are not made or distributed for direct commercial
advantage, the ACM copyrightnoticeand the title of the publicationandits date appear, and notice is given that copyingis by permissionof the
Associationfor ComputingMachinery.To copyotherwise, or to republish,
requires a fee and/or specific permission.
© 1990 ACM 089791-361-2/90/0005/0503

$1.50

503

M a i n T h e o r e m (Informal version.) There exists a
cryptographic protocol that allows n players, the majority of whom are honest, to evaluate any circuit securely. The protocol uses a constant number of rounds
and a polynomial amount of communication. The protocol works on a complete network (with private channels and supporting broadcast) and with any one-way
function. The protocol tolerates any polynomial-time
dynamic adversary.

Boolean circuit, C. Thus, in Stage 1, each player gets his
shares of the values along the input wires of C. In Stage2, for each gate of the circuit, the parties compute sharesof the value of the output wire from shares of the valuesof the input wires in a privacy-preserving manner. (Revealing the "incoming" shares for a gate will certainly
allow the parties to compute its "outgoing" shares, but
this will not preserve privacy. Even the output value ofa single, internal gate constitutes "additional" information that must not be revealed.) This privacy-preserving
computation, for a general gate, employs interaction. In
this way, the parties interact, working their way up thecircuit, from leaves to root, and eventually hold sharesfor the value corresponding to the output wire of C.

In other words, we prove that, with respect to securefunction evaluation, interaction is like an atom. Without interaction secure function evaluation is impossible;
but with a tiny bit of interaction, it is fully possible. A
more formal version will be given by Theorem 3, buteven now we would like to emphasize that our result
is largely independent of the underlying communication
model.

In the third and final stage, the output value of C is
recovered by the players.

T h e p r o b l e m . In view of this brief description, it
can be seen that all of these protocols for secure multiparty function evaluation run in unbounded "distributed time," that is, using an unbounded number ofrounds of communications. Even though the interaction
for each gate can be implemented in a way that requires
only a constant number of rounds, the total number ofrounds will still be linear in the depth of the underlying
circuit.
For many concrete computations, the resulting number of rounds would be prohibitive; in distributed computation, the number of rounds is generally the mostvaluable resource.
Bar-Ilan and Beaver [BB89] were the first to investigate reducing the round complexity for secure function evaluation. They exhibited a non-cryptographic
method that always saves a logarithmic factor of rounds(logarithmic in the total length of the players' inputs),
while the total amount of communication grows only bya polynomial factor. Alternatively, they show that the
number of rounds can be reduced to a constant, but at
the expense of an exponential blowup in the message
sizes. We insist that the total amount of communication be polynomially bounded. While their result showsthat the depth of a circuit is not a lower bound for thenumber of rounds necessary for securely evaluating it,
the savings is far from being substantial in a general
setting. Thus, the key question is:

T h e m o d e l o f c o m p u t a t i o n . We have stated ourmain theorem assuming a rich m o d e l - - a complete network of private channels, supporting broadcast--but
analogous results hold under more restricted models.
For example, if one increases the cryptographic assumption from a one-way function to public-key cryptography, then constant-round secure computation is possible
on a network supporting only broadcast. Similarly, fort < n/3, the broadcast channels can be dispensed withby using a constant expected time Byzantine agreement
protocol.
S e c u r i t y . To describe the security that our protocol
achieves, we must describe the type of adversary that
we are capable of defeating, and in what sense the adversary is defeated.
These are non-trivial matters. Many valuable notionsof security have been proposed and used in the literature. In this abstract, we adopt notions of security due
to Kilian, Micali, and Rogaway [KMR90].
We believe their formalization to be the "right one,"and present it in Section 2. However, we make no attempt to compare this notion with previous ones, or to
support the above claim.

A bird~s-eye v i e w of o u r s o l u t i o n
Our method can be described as finding the right way
to generalize the older two-party protocol o f Y a o [Ya86].
His result has been used within the G M W paradigm forcomputing the desired "outgoing shares" of each gatefrom its "incoming shares" by engaging in many, suitably chosen, two-party computations. This use, however, leads to an unbounded number of rounds. We,
instead, modify the construction "from the inside," generalizing it to many parties, but preserving the constantround complexity.
At a very high level, the idea is to use interaction
to construct a common "garbled circuit," along withHow many rounds are necessary to securely
evaluate a circuit while keeping the amount ofcommunication polynomial in the size of thecircuit?
O u r R e s u l t . Many of us believed that more complicated functions (i.e., those "with deeper circuits") required more rounds for secure evaluation. In this paper
we show that, using cryptography, this is not the case.
504

a set of "garbled inputs" for this circuit. Then, eachindividual player evaluates the garbled circuit, without
interacting with other players. The intermediate information that this garbled circuit produces is meaninglessto the players, but the output of the circuit is intelligible
and is guaranteed to be correct.
The circuit is scrambled in a very special way, so toallow the players to perform the brunt of the scrambling
locally, rather than use intensive interaction to simulate
this computation step-by-step. Still, the requisite local computation is not excessive: each player will invest
roughly as much time as is needed to evaluate the function f without any privacy constraints.
The common garbled circuit is constructed by joining various pieces, each piece being contributed by anindividual player. Of course, nobody is trusted to contribute a correct piece, so each player uses interaction
to prove to the "community" that he has done his work
correctly. As usual, verification is simpler than computation, and correctness of very deep circuits (evaluatedlocally by individual players) can be verified by small,
shallow circuits. These can be evaluated securely in aconstant number of rounds using the gate-by-gate approach of previous protocols. In the end, the community
can be certain that it is issuing a correct garbled circuit,which has been found with very little interaction.
We will see what this local and joint computation
looks like after we describe our goal more formally.

For f : (El) n --+ (El)n and T C { 1 , . . . , n } , fT(~)
is the function of ~ defined by fT(~) = (f(£))T, (i.e.,fT(Z) is the tagged T-coordinates of the image of £ under f ) .
The notation Ix ,--- X ; y ,-- Y ; . . . : S ( z , y , . . . ) ] denotes the distribution induced by the probabilistic algorithm 5' when its inputs are drawn by performing theindicated experiment (in the order specified).
A simulator is a probabilistic polynomial-time algorithm.

2

Model

Basic definitions
A function e : N .-, t t is negligible i f e ( k ) = k -~(D,(i.e., if e(k) vanishes faster than the inverse of any polynomial). An ensemble {Ak} is a family of probability
measures on E* for which there is a polynomial q suchthat only strings of length <_ q(k) have nonzero probability in .Ak. For ,4 taken from some ensemble and C
a Boolean circuit (with sufficiently many inputs), p.~ isthe probability that C outputs 1 on input drawn according to ,4. Ensembles {.Ak} and {Bk} are computationally indistinguishable if for any polynomial-size circuit
family C = {Ck}, the function e(k) = [ p ~ -pC~l is negligible; these ensembles are statistically indistinguishable
if e(k) = max I P r ~ [ S k ] -- Pr~[Sk]l is negligible.
SkC~"

Preliminaries

For this abstract, we restrict our definitions to finite
functions. The definitions easily extend to handle, say,function families or probabilistic functions.
The symbol n will always denote the number of players, and the symbol g, the length of each individual input and output. Thus the players are trying to securely
evaluate a function f : ( ~ e ) , __. (El)n, each player ilearning fi(£). Under these conditions, f can be represented by a Boolean circuit C. The goal of this section
is to define the notion of securely computing f .

of computation

There are a variety of models of computation underwhich secure distributed computation has been considered. To describe and develop our results, we adopt
a synchronous model of computation with both private channels and broadcast; we call this the standard
model. This is the usual model for maximally faulttolerant non-cryptographic computation, and is roughly
described below.
!
We envisage a network of processors whose computation is controlled by a common clock ticking at time
0, 1, 2 , . . . . Local computation is "instantaneous" compared to the ticking of the clock. Round i is the intervalof time between clock tick i and i + 1.
There is a read-only common input tape that initiallycontains a string 1k and is readable by all processors.
The value k is called the security parameter.
Each processor i has a private read/write work tape(initially containing the string A); a private read-only
input tape (initially containing xi); a private write-only
output tape (initially containing the string A); and some
additional communication tapes described below.
Between each pair of processors i and j there is a
private channel i ---* j for processor i to securely send
messages to processor j. T h a t is, this tape is exclusivewrite for i and exclusive-read for j.

Notation
Let Z = {0, 1), let A be the empty string, and let i k be
k written in unary. For x, y • ~*, Ixl = lY[, z ~ y is the
exclusive-or (XOR) of the these strings. If x = al • .. a,~
is a string, x[i:j] denotes the substring a l . . . a j . For x
and y strings, x o y denotes their concatenation. Whenb is a bit, b is its complement.
For T C { 1 , . . . , n } , we write T for { 1 , . . . , n } - T.
If ~ = ( x l , . . . , x , ~ ) and T C { 1 , . . . , n } , Z'T = {(i, xi) :i • T} (i.e., ~'T keeps track off the indices as well as
the values). If ~ = {xl, . . . , x n } , ~ ' = {x~, . . . , x , I} , andT C { 1 , . . . , n}, then g~- O ~ . can be regarded as an nvector, ( Y l , . . . , Y , ) , where Yi = xi i f i • T and yi = x~otherwise.
505

Each processor i also has a broadcast channel. Thisis a tape that is exclusive-write for i and readable by allprocessors j.
Proper conventions are assumed so that, at round r
and for each player i there is a well-defined message(possibly the empty message) that i is broadcasting (i.e.,
writing on its broadcasting channel) in this round; and,for each pair of players i and j , there is a unique message
that i is securely sending to j (i.e., is writing on channel
i -+ j ) in this round.

The protocol starts at round 1 arid terminates at thefirst round by which all good processors have terminated. The adversary terminates by the end of thisround, as well.
When the adversary terminates, the nonblank portionof her output tape contains some string. Fixing 7~, k,and g = (xl . . . . , x,~), adversary A defines a probability
space V I E W ~ t ( ~ ) , the space of "adversary outputs."
Without loss of generality, the adversary's output, orview, is an encoding of her history (that is, an encodingof her coin flips, what messages she received when, etc.)
When the protocol terminates, each good player has
output a certain value. We denote by O U T P U T ~ t ( ~ )the values output by the good players, tagged by thegood players' identity; that is, a point from this probability space is a tagged vector fla-

It is understood that channels are properly "labeled"
so that the recipient "knows" who is the sender of amessage.
Each processor has access to a fair coin; that is, it canenter a distinguished state from which it enters eitherof two successor states with equal probability.
A model of computation defined as above but supporting only broadcast for communication is called abroadcast model.

Security

Processor i of the network runs program Pi; the ntuple of programs 79 = (Pi,..., Pn) is called a protocol.
For each player i, i's history in the execution of a protocol consists of everything that player i has had access
to: its private and common input, all broadcast messages, all messages received along private channels to i,
and the coins that processor i has flipped.

As with zero-knowledge interactive proofs, the notion ofprivacy involves the approximability of the adversary'sview by a simulator. The question is: the view should
be approximable given what?
We now state definitions from [KMR90].
A t-bounded (~,f)-oracle behaves as follows. It accepts two types of queries, called component queries andoutput queries.
A component query is an integer i, 1 < i < n. It is answered by xi if t or fewer component queries have been
made so far, and no output query has been made so far;
it is answered by (xi, fi(~y t2 ~ ) ) if t or fewer component queries have been made so far, and the proper
output query previously made was z'~. Additional or
improper component queries are not answered)An output query is a tagged vector x'~.. It is answeredby f T ( ~ T tO ~ . ) i f T consists precisely of the component
queries made so far, and if this is the first output query.
Additional or improper output queries are not answered.
Note that we permit component queries to follow theoutput query, as long as the total number of component
queries is bounded by t.
We consider simulators S having access to a tbounded (~, f)-oracle. The output of such a simulator
is denoted OUTPUT S°'(e'l)(lk); this is a probability
space. We let QuEamS S°'(e,l)(1 k) denote the indicesi for which there was never a component query, together
with the (single) output query; a point from this probability space is written (G, ~-). Because of the possibilityof component queries following the output query, G may
be a proper subset of T.
We are now ready to define the notion of security.

The

Adversary

For simplicity, we assume a uniform adversary. In thiscase, an adversary A is a probabilistic polynomial-timealgorithm. An adversary acts on a network, corrupting
processors. A processor is called bad after it has beencorrupted by A, good if it has not yet been corrupted
by A.
When the adversary corrupts a processor, she learns
its entire internal configuration, will read all future messages sent to it, and will choose what messages it will
send in the future essentially, the adversary totally
subsumes the corrupted processor.
The adversary has the ability to corrupt processors ina dynamic fashion. At the beginning of each round, theadversary may choose to corrupt some new processors.
By doing so she learns (in particular) all the messages
sent to it in the current round. Having done this, theadversary may decide whether to corrupt another new
processor, and so on, until she decides not to corrupt
any more processors during this round. At this point
she composes all the messages from the bad prqcessors
to the good ones for the current round.-These messages(and the ones between good processors) are guaranteed
to be delivered by the end of the round.

a For t h e p u r p o s e of c o m p u t i n g s t r i n g - v a l u e d f u n c t i o n s , t h i s
c a n b e simplified: a c o m p o n e n t q u e r y i r e t u r n s x l if th er e h a v e
b e e n t or fewer c o m p o n e n t q u e r i e s so far.

A t-adversary is an adversary that corrupts at mostt processors.
506

D e f i n i t i o n 1 Fir f : ( Z t ) . ~ (Et)n. ProtocoI P tsecurely computes f if for all t-adversaries A there ex-

3

The Protocol

ists a simulator S (capable of querying a t-bounded oracle), such that

Building blocks
This subsection describes some "well known" results
which we require to describe our protocol.

• ( P r i v a c y ) for all ~ E (Et)., the k-parameterized

ensembles

the k-

Verifiable Secret Sharing. Let us informally state
the notion of verifiable secret sharing (VSS), originallyintroduced by [CGMA85]. This is a way to secretly commit to a value. A distinguished player D (the dealer)
has a private input bit b. At the end of an execution of
a VSS protocol tolerating t faults, each player i holds
his own private share bi of bit b. We require three properties to hold:[(G, fiT) ~-- QUERIES s O ' ( e ' / ) ( l k ) : fG(Z'~ U fiT)]

1. With probability > 1 - 1/2 k, there exists a uniquevalue b~ such that if the good players broadcast
their private shares, each good player will locally compute b' from the broadcasted values-regardless of the values broadcast by the bad players.

VIEW~(Z)andOUTPUTS°'(~'f)(1 k)are computationally indistinguishable; and,for all ~parameterized ensembles• (Correctness)E(Et) n,OUTPUT~(~)

and

2. If the dealer is good, b' = b.

are statistically indistinguishable.

3. If the dealer is good, the view of any t-adversary
who does not corrupt D is independent of b.

R e m a r k s . This notion of security implicitly enforces
independence--that is, the adversary's inability to influence the outcome of the protocol on the basis of values
privately held by uncorrupted players. It also implicitly enforces fairness--the adversary's inability to obtain more information than the good players do. Fairness is generally not an issue in multiparty protocols
with honest majority, but implicitly enforcing independence through the correctness constraint is novel.

We say that player D commits to bit b if VSS is executed with dealer D and private input b. At the end ofsuch an execution, b is said to be a committed bit. Moregenerally (and more informally), any bit represented byshares as above, is called a shared bit, even if its shares
do not originate from a given dealer executing VSS. We
will also speak of shared strings--meaning that each bitof the string is a shared bit.
We say that a committed value is privately revealed toplayer i if all good players send to i their private sharesof this value along the appropriate private channels; inthis way, i alone recovers the value. A committed value
is publicly'revealed if all good players broadcast theirprivate shares of the value; in this way, all the players
recover the value.

Strong Security
The above definition of security essentially says thatany adversary has its own simulator. We will actuallyachieve something stronger. Namely, that there will exist a single simulator that works for any adversary A
with which it interacts in a special fashion. The simulator creates a "virtual world" and has A act in it.
In this virtual world, A sees an indistinguishable view
from that which it would see when interacting in thereal network. Moreover, the simulator does not monitor the internal computation of A, nor does it choose
the coin flips for A to use. The simulator outputs what
~dversary A in the virtual execution outputs, and thedmulator asks component queries only for those pro:essors "corrupted" during the simulation. (Details on";he interaction between the simulator and the adversary
will appear in the final paper.)
We call this notion of security strong security. Not
only is strong security what is actually achieved by our
protocol, it is a desirable end goal in itself.

C o m p u t i n g on shared bits. [RB89] have shown thatin our model of computation, VSS is implementable ina constant number of rounds and tolerating any compurationally unbounded t-adversary, for any t < n/2. Furthermore, they (as well as [Be88]) have shown that any
Boolean circuit C with bounded fan-in and depth d canbe evaluated on shared values securely and secretly-that is, the inputs to the computation are shared bits,
and the result also is a shared bit (which will be revealed only if so wanted). This computation requires
O(d) rounds and communication complexity local computation polynomial in k and ICI (where ICI is the sizeof the circuit C).
While O(d) rounds are sufficient for securely and secretly evaluating any depth-d circuit, this does not mean507

that one cannot get by with fewer rounds. In particular, a closer look at the underlying method shows that(when the underlying field of the VSS protocol is taken
to have characteristic 2) the XOR function (on any number of bits) can be securely and secretly evaluated in aconstant number of rounds and polynomial communication.
C o l l a b o r a t i v e coin f l i p p i n g . This, in turn, allows theplayers to collaboratively obtain shared, random bits
(known to no one) in a constant number of rounds: eachplayer commits a random bit, and the XOR of thesecommittals is securely and secretly evaluated. This
shared value is the shared random bit.
P r o v i n g a s s e r t i o n s to the c o m m u n i t y . It is useful
to conceptualize as a primitive "prove a given assertion to the community." In particular, players in our
protocol will be required to prove that they have donesome local computation correctly. Even though this local computation may require deep circuits, the proof
that it has been done correctly will be fast:P r o p o s i t i o n 2 Let G : Ea .._+ Eb be a function represented by a circuit C, and let let a l , " ' , a abe shared
bits which have been previously opened to some player
i. Then player i can commit the bits of G ( a l ' - ' a a ) ,and prove to the community that the committals represent the correctly computed value o f f on or1 • .. try. The
proof reveals nothing in the information.theoretic sense
and requires only a constant number of rounds and apolynomial amount of communication (in the size of C
and in the security parameter).
To prove that ~ was evaluated correctly, player i willcommit (in addition to the function value) a "certificate" (Cl . . . . ,cb) to demonstrate his claim. The certificate consists of the Boolean values at all (internal)
wires of the circuit C that evaluates G. The community,
acting as the "verifier," checks the condition "the values specified on the circuit's wires are correct for eachgate." This is just the conjunct of constant depth predicates on committed values, and so the predicates can be
securely evaluated and publicly revealed in a constantnumber of rounds. The players compute the AND on
their o w n - - t h a t is, they accept the proof only if they
believe the circuit is locally correct everywhere.
P s e u d o r a n d o m g e n e r a t o r s . Our protocol makes useof a "perfect" pseudorandom generator. This is a deterministic polynomial-time algorithm stretching a short,truly random input string (the "seed") to a longer, pseudorandom string. It is required that the ensemble of output strings be computationally indistinguishable fromtruly random strings of the same length. This notion
is due to Blum and Micali IBM82] and Yao [Ya82b],
who showed that such generators exist under, suitablecomplexity assumptions.

Complexity assumption
The only complexity assumption used for our main theorem is the existence of a pseudorandom generator.
Recently, Impagliazzo, Levin and Luby [ILL89] andH£stad [Ha90] have shown this assumption to be equivalent to the existence of a one-way function.

The s t r u c t u r eo f our protocol

The protocol we construct has two phases. The firstphase is a non-cryptographic protocol. The only information revealed to players in the first phase of the
protocol are some random strings.
The second phase of the protocol consists of only asingle round. During this round, the players publicly
reveal information which was computed during the firstphase of the protocol. The information that is revealed
is precisely the "garbled circuit" and its "garbled input" rnentioned in the introduction. Though what isrevealed contains information which betrays the players' private inputs, the information is nonetheless unusable (given the cryptographic assumption) with respect
to polynomial-time computation. After recovering the
garbled circuit and garbled input, the players evaluate it
individually, without interaction, obtaining the desired
result.
Descriptiono f o u r protocol

O b v i o u s c h e a t i n g . As we have said, a protocol is a setof instructions to be followed by the good players. As
we also said, though, the adversary may have some players deviate from their prescribed program. The subtle
adversary will do this without exposing the corrupted
players. That is, though the corrupted players follow
different instructions, the messages they send are notobviously dictated by the adversary. Of course, an adversary may not be subtle at all, and instruct a player
to, say, send nothing when a message is expected, or toprovide to the community a clearly fallacious "proof" ofan assertion. Tilts sort of behavior can be taken care ofby proper conventions (deciding on default values, etc.).
These conventions would complicate the description of
our protocol, but without adding any particular insight.
Thus, for the sake of simplicity and for focusing on theimportant issues, we first describe the protocol whenno obvious cheating is detected, and later discuss thenecessary additions.
N o t a t i o n . We fix notation for the remainder of thepaper. We let ~ denote a pseudorandom generator thatstretches a k-bit string s to a k + 2nk bit string, and we
define F, G and H to be the first k, next nk, and last
nk bits produced by the generator, F(s) = G(s)[1 : k],G(s) = G(s)[k+ l : k + nk], and H(s) = ~ ( s ) [ k + n k + 1:
k + 2nk].

508

(a) For each input wire w of the circuit, the players securely and secretly compute the garbled
input for this wire, defined byWithout loss of generality, the circuit being evaluatedconsists solely of two-input gates. The circuit has W
wires, which are labeled 0, 1 , . . . , W - 1. To simplify
the exposition of the protocol, we will assume there is
only a single output wire, which is wire W - 1, and all
players are to learn this bit. The protocol can readily
be extended to handle the computation of functions f :(El) n --+ (El) n, and to more general scenarios.
In the description that follows, the superscript i
ranges over the players, 1 < i _< n. The subscript w
ranges over the wires, 0 < w < W - 1 .
Each wirew
has two indices associated with it, 2w and 2w + 1. The
subscript j ranges over such indices, 0 < j < 2W - 1.
Phrases in quotes are comments.
Phase

n

0

n

(b) For each gate g of the circuit, the players securely and secretly compute the gate-labels forgate g. These consist of four strings, Ag,
Bg, Cg, and Dg. These strings are defined
as follows: If gate g computes the function®, the left wire is wire a, the right wire iswire fl, and and the output wire is wire 7,
0 < a,fl, 7 < W - 1), then, writing a = 2a,b=2fl, andc=2%

In this phase, the players compute the garbled circuitand the garbled input, leaving this information as sharedvalues.
1. Each player shares his input bits. Let b,o be theshared bit associated with each input wire w of
the circuit. "Each b~ is a bit from some particular
player's xi value."Ag=ega" •@fs~ o . . . o s~~s~+ x o...ose~+xB#=

2. The players collaboratively flip (2kn + 1)W coins,which define
Cg =ifA~ ® SA=

A7[S +s o . . . o s %1 otherwiset,~ • h ~ . . . q ~ h ~g~+~e...~g~+~@(b) bits ( A 0 , . . . , A w _ t ) .

if Aa ® Az = A~otherwisehla(~ ." "(~h n e g~_[.l(~ • "'(~gbn.l_lfs~ o . . . o s~(a) 2nW length-k strings, sj, for 1 < i < n, 0 <j < 2 W - 1, and. Each player i gets seeds s}, 0 _< j < 2W - 1, privately revealed to him.

O.

where Itr]] . . . . .
]~r~] = k. "Thus the garbled input consists of one super-seed for each
input wire of the circuit. Which of the two
super-seeds associated with input wire w--thesuper-seed indexed by 2w or the super-seed indexed by 2 w + l - - i s determined by A~ and b~."I

i
"The strings %.
are called seeds, while the strings
sjZ o ... o s~ are called super-seeds. Each super-seedis associated with a bit, as follows: s ~ o . . . o s ~ isassociated with A~, while s ~ + l o . . . o s~,~+1 is associated with A~. The value Aw-1 will be publicly
revealed in Step 6."i{s~ o . . . o s ~'~ 1
S o1+ 1 0 . . . 0
So+

if A--~®A~ = A7
otherwise1n
Dg = h~+te...q~h~+
1 ~ h~+t~...~h'~+lfs~ o...os'~
if A~ ® A~ = A-r

Gist+ to...os¢~+t
PhaseotherwiseII

In this phase, the players publicly reveal the garbled circuit and the garbled input, and they evaluate it on theirown,

6. The players publicly reveal
4. The strings sji revealed to player i are used by
player i as the seeds of the pseudorandom generator ~. Thus player/locally computes f j = F(s~.),g} = G(s}), and h i = H(s}), for 0 < j < 2 W - 1.
Player i then commits each f~, gj, and h~, andproves to the community that these committals
were computed correctly. "The strings f] o . . . o f~
are called wire-labels. They will be publicly revealed in Step 6. The other values committed here
will never be revealed."(a) "tile bit associated with the output wire,"Aw_l, computed in Step 2;(b) the gate-labels f], 1 < i < n, 0 < j < 2 W - 1,
committed in Step 4;(c) the garbled input crl~o . . . o ~,n~associated witheach input wire w of the circuit, computed in
Step (5a); and(d) the gate-labels Ag, Ba, Cg, and D 9 associatedwith each gate g, computed in Step (hb).

. "The players securely and secretly compute some
simple functions on the shared values. These values
will be opened in Step 6. Namely:""Together, the strings revealed in Steps 6(a), 6(b),and 6(d) constitute the garbled circuit, while thoserevealed in Step 6(c) are the garbled input."509

7. "Each player evaluates the garbled circuit by himself, learning a super-seed for each wire. The superseed of the root determines the output of the circuit according to the value of -~w-1- To evaluate
the circuit:"
Initially, for each input wire w, you hold s~o~ o . . . os ~ = 0-~ o . . . o 0-w
n if r(0-~) = f ~ , and you holds ~ + l o ... o s~o~+1 = 0-1o~o ... o 0-'*o~otherwise.
Suppose inductively that you hold sa+ o • • • o sa+
for the left input wire of a gate g, and you holds~+q o...oS~+q for the right input wire, where a andb are even and p,q E {0, 1}. Suppose the output
wire of the gate is wire 7, 0 < 7 < W - 1. Then, for
i
i
i
"
ha+p
1 < i < n, set ga+p
= G(sa+p),= H(sSa+p),
g~+q = G(s~+q), and h/b+q = H(s~+q), and compute

0-7 = 0-~o...o0-~ (I0-~1 ="-=

I0-~1 = k) accordingtof ga+p (~" • .(~ga+p(~gb+q(~ • .. (~gb+q(~A#|

ifp=Oandq=O
1

"*

1

[ h a + p ~ " .. ~ h a + p ~ g b + q ~ . ")n(~gb+q(~Bgi f p = 0 and q = 1

0-7 = ] g al + p @ " " ~ g an+ p ~ h b1+ q ~ " "

|

ifp=l

@ h nb+q(gCaandq=O01"*
h a1 + p ~ . . . ~ h an+ p ~ h b +q ~ " .. (~hb+q~Dg

1

i f p = 1 and q = 1
21

You are now holding s~7 o . . . o s~7 = 0-7 if F(o'17) =ftT, and you are holding 8 217 + 1 0= 0" 7• • • O 8 2"*
7+1
otherwise.

22

Z3

Figure 1: The circuit C to be securely evaluated.

When you come to hold S2w
1 +p o. • • o S2w
n +p, output
p ~ A w - 1 on your private output tape.
This completes the description of the protocol.
A verysimpleexampleThe following example may be useful in understand thepreceding protocol. Suppose that there are n = 3 players, /91, P2 and P3, and each player holds a single bit,xl = 0, x2 = 1 and x3 = 1, respectively. The players wish to compute function f ( x l , x 2 , x3) = 21x2 V x3.
They know the fixed circuit C of Figure 1 which evaluates this function (including the labeling of wires andgates).
Figure 2 depicts the garbled circuit and the garbled
input collaboratively computed by the community, if(~0,,~1, ~2, ~3, ~4) = (0, 1,0,0, 1). The values of thegate-labels are shown in Figure 3.

W h a t to do w h e n cheating is d e t e c t e d
The protocol we have just given, with simple modifications to deal with ostensibly cheating players, provides
us with secure constant round computation in the standard model. We now sketch the main modifications.

If a fault is detected before the completion of Step
1, we replace the faulting player's inputs with "default"
values. This certainly incorporates scenarios such as thedefault not being the value on any "proper" input, andthe output including a list of players faulting before they
have committed their input bits.
For faults occurring after Step 1, the computation
proceeds using the input values already committed by
the offending player. There is no need to reveal a bad
players' private input in order to accomplish this. Only
the bad player's seeds need to be known by the good
players--and even these need not be known by the good
players if the fault occurs after Step 4. However, forfaults occurring before the completion of Step 4, thegood players effectively 'frill in" for the bad player. Random seeds which would otherwise be issued to the badplayer are revealed to all of the players instead. In thisway, the parties select a garbled circuit and garbled
input from the same distribution as if all players had
played honestly after the committal in Step 1.
Faults detected in Steps 5 and 6 need result in no"punitive" action whatsoever (that is, nothing of thefaulting player needs be divulged).
510

A: = g l ~ . . , eg~• g~e.--eg; • 4 o...o s~

f~of:of~

C: = g l e - . , eg~

A2A2 = g l . . . , eg;

B2

B2 = h ~ . - . @ h ~D2D2 = h l e . - - . h ;de.--eg? • 4 o...o,;g~e..-eg~ • 4 o-.-o s~• h~e.., eh; ~ 4 o...o ~;fd1 o&2 of~3

(O)

:

2

Figure 3: The gate-labels for the two gates of Figure 2.

3

fT°f7°f~If~ofgof2 (0)f~o~2of#A1
B:

C o r o l l a r y 4 Same as Theorem 3, but in the broadcast
model and assuming a secure public-key cryptosystem.
To give a second example, the result of Ben-Or and
EI-Yaniv [BE88] can be applied to give secure constantround computation in the model with only private channels.

C~Dt
f4ofaofa
f~1 o f :2 o f t3I2
3
80080080

C o r o l l a r y 5 Same as Theorem 3, but for t < n/3 andin the model with only private channels (no broadcast).

f~1 of~2 of~3
1
2
382082082: 2 385085085

0'igure 2:
The garbled circuit, garbled input,;~nd Aw-values for the circuit of Figure 1, where(Ao,Ax,A2,Aa, A4) = (0,1,0,0,1), and (bo,bl,b2)~:o,x, 1).
4

Proving

Security

A full proof of the security for our protocol is very involved and not well suited to an abstract. In this section, we formMly state our main theorem and briefly
c.iscuss the nature of a proof.
T h e o r e m 3 Assume the standard model, t < n/2,f : (~l)n ~ (~e)n a function realized by a circuit C.
Assume that a pseudorandom generator exists. Thenl.~ere is a protocol7) that strongly l-securely computes f
i:l const, rounds, where cons1; is an absolute conslanl.
Furthermore, a natural encoding of protocol 7) can befound by a fixed algorithm in time polynomial in ICI.
Local computation in 7) is poly(IC[,k) lime bounded,here p o l y is a fixed polynomial.
As mentioned in Section 1, corresponding results forol,her models of computation follow. For example, theresult of Feldman [Fe88] implies that public-key encryption can be used to establish the analogous result for thebroadcast model.

To prove Theorem 3 we must exhibit a simulator S
which satisfies the privacy and correctness constraints.
This is a very big job.
Privacy is the main issue. To achieve privacy, thesimulator S must provide the adversary A with a computationally indistinguishable view from that which it
would see when interacting in the real network. Thisis argued round-by-round, repeatedly showing how toextend the view that the simulator has created so far
for the adversary to a view that works for one moreround. The simulator must imitate broadcast messages
and messages sent along private channels to players corrupted in the simulation, and the simulator must provide to the adversary a fake "state" for processors when
they are corrupted by the adversary during the the simulation.
The proof mirrors the two phase structure of the protocol. The first phase of the protocol is argued to bestrongly t-private in the "information-theoretic sense,"
and revealing nothing. Then we show how to extend
this simulation for the one round of the second phase.
For that, we must show both how to simulate theplayers' final round of broadcasts, and also, how to simulate the players' private state for those players who arecorrupted during the adversary's final round.
The former task is the more interesting. Proceeding intuitively, to simulate the player's final round of
messages, we must insure that the garbled circuit andthe garbled input released in Step 6 is drawn from a
distribution that the simulator can approximate (up511to computational indistinguishability) given the simulator's previous history. To do this, the simulator constructed for the first phase of the protocol, observing
outgoing messages to at least ( n + 1)/2 players, "knows"
the values ~ . that the adversary has effectively committed to. Likewise, the simulator will "know" the seeds
issued to all of the players.
The simulator uses this information in constructing
a "fake" garbled circuit and garbled input which it will
(effectively) hand over to the adversary.
To construct a convincing garbled circuit and garbled input, an output oracle query of ~'~. is made, andthe simulator will learn (for a Boolean function) a bit
b. Wire-labels are selected as the image under F of
the seeds which the simulator already knows from thefirst phase of the simulation. Then, a "random path"through the garbled circuit is selected. This p a t h (together with the seeds) determines which one of the fourgate labels is to be "used" in evaluating the circuit, andwhat the garbled input is. The bit b is used to select)~w-1 so that the circuit (given the selected path) computes the bit b. All that remains unspecified are thethree "unused" gate-labels associated with each gate;
the simulator simply fills in r a n d o m strings here.
Of course, it is far from clear that this "fake" garbled
circuit and garbled input will in any sense fool the adversary. A key l e m m a to establishing this is that, for any
u7 E (~t)n, the space of "real" garbled circuits and garbled inputs for u7 is computationally indistinguishable
from the space of "fake" garbled circuits and garbled
inputs which we have just specified--and this remains
so, even if conditioned on some particular partial choiceof seeds {S~.}ieT ' 0<j<2~V-1, for IT I <_ n -- 1.

5

Open P r o b l e m s

Our cryptographic protocol for constant-round, securefunction evaluation is optimal in the sense that it isbased on the mildest possible cryptographic assumption,
the existence of a one-way function, and some positive
number of rounds is certainly required.
Let us conclude by stating what we believe to be thekey open question in this a r e a - - n a m e l y ,Is there a constant-round, non-cryptographic
protocol for secure function evaluation?

T h a t is, is there a constant-round protocol, in the standard model, t h a t allows n computationally unbounded
players to defeat a computationally unbounded adversary, while using only a polynomial amount of communication?
This problem is open even for the case of t = 1.
A partial answer to this question is now known, due to
Beaver, Feigenbaum, Kilian, and Rogaway [BFKR89]:
they show t h a t any functions on O ( ( n l o g n ) / t ) shared
bits can be t-securely evaluated in a constant numberof rounds by a network of n processors.

Acknowledgments
The various authors happily acknowledge discussions
with Mihir Bellare, Shaft Goldwasser, Stuart Haber,
Joe Kilian, Rafail Ostrovsky, Charlie Rackoff, and Moti
Yung.

References[BB89] J. Bar-llan and D. Beaver, "Non-Cryptographic
Fault Tolerant Computing in a Constant Numberof Rounds of Interaction," Proc. of the 8th PODC
(1989), 201-09.
[Be88] D. Beaver, "Secure Multiparty Protocols Tolerating
Half Faulty Processors," Harvard Technical Report
TR-19-88, and in CRYPTO-89 Proceedings.
[Be90] D. Beaver, "Security, Fault-Tolerance, and Communication Complexity for Distributed Systems," Harvard University Ph.D. Thesis, 1990.
[BFKR89] D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, "Cryptographic Applications of Locally Random Reductions," Bell Laboratories Technical Memorandum, November 1989. Also a 1990 PODC submission, "Security with Low Communication Overhead."[BG89] D. Beaver and S. Goldwasser, "Multiparty Computations with Faulty Majority," CRYPTO-89 Proceedings.
[BE88] M. Ben-Or and R. E1-Yaniv, "Interactive Consistency in Constant Expected Time," manuscript, December 1988.
[BGW88] M. Ben-Or, S. Goldwasser and A~ Wigderson,"Completeness Theorems for Non-Cryptographic
Fault-Tolerant Distributed Computation," Proc. ofthe 20th STOC (1988), 1-10.
[BM82] M. Blum and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo-Random
Bits," SIAM J. of Computing, 13:850-864 (1984),
and FOCS 82.
[Ch89] D. Chaum, "The Spymasters Double-Agent Problem: Multiparty Computations Secure Unconditionally from Minorities and Cryptographically from
Majorities," CRYPTO-89 Proceeding.
[CCD88] D. Chaum, C. Cr@peau and 1. Damg£rd, "Multiparty Unconditionally Secure Protocols," Proc. ofthe 20th STOC (1988), 11-19.
[CDG87] D. Chaum, I. Damg£rd and J. van de Graft,"Multiparty Computations Ensuring the Privacy ofEach Party's Input and Correctness of the Result,"
CRYPTO-87 Proceedings, 87-119.
[CGMA85] B. Chor, O. Goldreich, S. Micali and B. Awerbuch, "Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults," Proc. of the
26th FOCS (1985), 383-95.
512

[C,R87] B. Chor and M. Rabin, "Achieving Independence in
Logarithmic Number of Rounds," Proc. of the 6th
P O D C (1987).
[Fe88] P. Feldman, "One Can Always Assume Private
Channels," unpublished manuscript (1988).
[FM88] P. Feldman and S. Micali, "Optimal Algorithms
for Byzantine Agreement," Proc. of the 20th S T O C(1988), 148-161.
[C.HY87] Z. Galil, S. Haber and M. Yung, "Cryptographic
Computation: Secure Fault-Tolerant Protocols andthe Public-Key Model," CRYPTO-87 Proceedings,
135-155.
[GMW87] O. Goldreich, S. Micali and A. Wigderson, "Howto Play Any Mental Game," Proc. of the 19th S T O C(1987), 218-229.
[GV87] O. Goldreich and R. VaJnish, "How to Solve any
Protocol Problem--An Efficiency Improvement,"
CRYPTO-87 Proceedings, 76-86.
[Ha88] S. Haber, "Multi-Party Cryptographic Computation: Techniques and Applications," Columbia University Ph.D. Thesis (1988).
[H~90] J. H£stad, "Pseudo-Random Generators with Uniform Assumptions," these proceedings.
[KMR90] J. Kilian, S. Micah and P. Rogaway, "The Notionof Secure Computation," manuscript, March 1990.
[IIL89] R. Impagliazzo, L. Levin and M. Luby, "PseudoRandom Generation from One-Way Functions,"
Proc. of the 21st S T O C (1989), 12-23.
[RB89] T. Rabin and M. Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority," Proc. of the 21st S T O C (1989), 73-85.
[Ro90] P. Rogaway, "The Round Complexity of Secure Protocols," MIT Ph.D. Thesis (1990).
[Ya82a] A. Yao, Protocols for Secure Computation, Proc. ofthe 23rd F O C S (1982) 160-164.
[¥a82b] A. Yao, "Theory and Applications of Trapdoor
Functions," Proc. of the 23rd F O C S (1982) 80-91.
[Ya86] A. Yao, "How to Generate and Exchange Secrets,"
Proc. of the 18th S T O C (1986) 162-167.

513