Detectable byzantine agreement secure against faulty majorities.
It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.
INTRODUCTION
Broadcast (a.k.a. Byzantine agreement) is an important primitive
in the design of distributed protocols. A protocol with a
designated sender s achieves broadcast if it acts as a megaphone
for s: all other players will receive the message s sends, and
moreover if an honest player receives a message, then he knows
that all other honest players received the same message | it
is impossible even for a cheating s to force inconsistency in the
outputs.
Lamport, Shostak, and Pease [24, 22] showed that if players
share no initial setup information beyond pairwise authenticated
channels, then in fact broadcast is possible if and only if t <
n=3, where n is the number of players and t is the number of
actively corrupted players to be tolerated by the protocol. By
the impossibility proofs in [20, 10, 11], even additional resources
(e.g., secret channels, private random coins, quantum channels
and computers) cannot help to improve this bound unless some
setup shared among more than just pairs of players is involved.
On the other hand, the picture changes dramatically if some
previous setup is allowed. If secure signature schemes exist and
the adversary is limited to polynomial time, then having pre-
agreement on a public verication key for every player allows
for e-cient broadcast for any t < n [22, 8]. Ptzmann and
Waidner [25] showed that broadcast among n players during a
precomputation phase allows for later broadcast that is e-cient
and unconditionally secure, also for any t < n. Those two works
will be key pieces for our constructions.
Surprisingly, very strong agreement protocols are still achievable
without previous setup. Fitzi, Gisin, Maurer, and von Rotz [13,
12] showed that a weaker variant of broadcast, detectable broad-
cast, can be achieved for any t < n=2. In a detectable broadcast,
cheaters can force the protocol to abort, but in that case all honest
players agree that it has aborted. This is ideal for settings in
which robust tolerance of errors is not necessary, and detection
su-ces.
1.1 Contributions
We show that detectable broadcast is possible for any t < n, in
three dierent models. The rst protocol requires only pairwise
authenticated channels, but assumes a polynomial-time adversary
and the existence of secure signature schemes. The second
protocol requires pairwise secure channels, but is secure against
unbounded adversaries. The third protocol requires authenticated
classical channels and (insecure) quantum channels, but
also tolerates unbounded adversaries.
Theorem 1. Detectable broadcast is achievable based on (1):
a network of pairwise authenticated channels and assuming a
secure signature scheme; or based on (2): a network of pairwise
secure channels with no computational assumptions; or based on
(3): a network of pairwise authenticated channels and insecure
quantum channels with no computational assumptions.
The protocol for (1) requires t rounds and O(n 3
message bits to be sent by correct players, where k is the length
of a signature. The protocol for (2) requires t
roughly O(n 8 (log message bits to be sent, where
k is the security parameter. The protocol for (3) requires
rounds and roughly O(kn 4 log n) bits (qubits) of communica-
tion. The message complexities above are stated with respect to
message domains of constant size. The exact complexities with
dependencies on the domain size are given later.
In particular, our results show that the impossibility of weak
broadcast for deterministic protocols, due to Lamport [21], does
not extend to randomized ones (Lamport's proof does apply to
protocols with only public coins, but fails when players are allowed
to have private random inputs).
Combined with results from the previous literature, our results
yield protocols for \detectable" versions of multi-party computation
(mpc) with resilience t < n, in which the adversary may
force the protocol to abort, assuming only pairwise authenticated
channels and the existence of trapdoor permutations. An
mpc protocol allows players with inputs x1 ; :::; xn to evaluate
some function f(x1 ; :::; xn) such that the adversary can neither
corrupt the output nor learn any information beyond the value
of f . We give two ways to apply our detectable broadcast protocol
to the generic construction of [15, 2, 14] to remove the
assumption of a broadcast channel.
In independent work, Goldwasser and Lindell [17] give a dier-
ent, more general transformation, which also eliminates the use
of a broadcast channel. Their transformation achieves a weaker
notion of agreement than ours|honest players may not always
agree on whether or not the protocol terminated successfully
(see their work for a more precise denition). On the other
hand, that transformation is more e-cient in round complexity
and satises partial fairness (which is not satised by the more
e-cient of our transformations). Additionally, they analyze the
behaviour of their transformation with respect to arbitrary mpc
protocols, not only that of [15, 2, 14], and with respect to concurrent
composition.
Finally, it can be observed that, in order to achieve detectable
broadcast or multi-party computation, no prior agreement among
the players is necessary. This implies that such a protocol can
be spontaneously initiated by any player at any time. It also
implies that players in a synchronous network can achieve \de-
tectable clock synchronization," namely either all honest players
end up with synchronized clocks, or all honest players abort (not
necessarily at exactly the same time).
1.2 Models and Definitions
Models: We consider a synchronous network in which every pair
of players is connected by an unjammable, authenticated chan-
nel. That is, for every pair i; j, player p i can always send messages
directly to p j . The adversary can neither prevent those
messages from being delivered nor introduce new messages on
the channel. By synchronous, we mean that all players run on a
common clock, and messages are always delivered within some
bounded time. Our protocols are secure even if the adversary
can rush messages, i.e., even if messages from honest players are
delivered before corrupted players send their messages.
Our protocols are secure against Byzantine (or \active") adver-
saries, that select up to t players and coordinatedly corrupt them
in an arbitrarily malicious way. The corruptions may be adap-
tive, that is the adversary grows the set of corrupted players on
the
y, based on the execution so far.
In this framework, we consider three models, denoted Mauth ,
1. Mauth : Authenticated channels, computational security.
The adversary may read all communication in the network,
even among honest players, but is limited to polynomial
time computations (and may not tamper with the chan-
nels). Here, the only information not available to the adversary
is the internal state and random coins of the honest
players.
2. Msec : Secure channels, unconditional security (a.k.a. \in-
security"). The channels between honest
players are unreadable, but the adversary is computationally
unbounded.
3. unconditional security. All pairs
of players share an authenticated classical channel and an
insecure quantum channel (which the adversary can tamper
with). The adversary is computationally unbounded.
If one is only interested in feasability results, then one only needs
to consider the second model, Msec . By (carefully) encrypting
communication over authenticated channels, one can implement
secure channels in Mauth [5], so in fact any protocol for Msec is
also a protocol for Mauth . However, protocols designed specifically
for Msec can use computational cryptographic tools for
greater simplicity and e-ciency 1 . Similarly, any protocol for
Msec leads to a protocol for Mq (by implementing secure channels
using quantum key distribution), but protocols designed
specically for Mq may be more e-cient.
Denitions: In the denitions below, D may be any nite domain
(say We require that the conditions for each task
hold except with probability exponentially small in the security
parameter (super-polynomially small in the case of computational
security). Protocols should have complexity polynomial
in both n and k.
ers, where player s (called the sender) holds an input value
xs 2 D and every player p i (i 2 [n]) nally decides on an output
value broadcast if it satises:
Validity: If the sender is honest then all honest players p i
decide on the sender's input value, y
Consistency: All honest players compute the same output
value
(Detectable Broadcast). A protocol among n
players achieves detectable broadcast if it satises:
Correctness: All honest players commonly accept or commonly
reject the protocol. If all honest players accept then
the protocol achieves broadcast.
Completeness: If no player is corrupted during the protocol
then all players accept.
Fairness: If any honest player rejects the protocol then
the adversary gets no information about the sender's input.It turns out that our protocols achieve a stronger notion, namely
they \detectably" establish the setup needed to perform strong
broadcast using the protocols of [8, 25].
Definition 3 (Detectable Precomputation). A protocol among
players achieves detectable precomputation for broadcast (or
detectable precomputation, for short) if it satises:
Correctness: All honest players commonly accept or commonly
reject the protocol. If all honest players accept then
strong broadcast will be achievable.
Completeness: If no player is corrupted during the protocol
then all honest players accept.
Independence: A honest player's intended input value
for any precomputed broadcast need not be known at the
time of the precomputation. 4
Independence implies two important properties: rst, the pre-computation
may be done long before the actual broadcasts it
designed specically for Mauth may also use potentially
weaker computational assumptions. For example, our protocols
require only the existence of one-way functions, while the
general reduction from Msec to Mauth requires semantically secure
encryption.
will be used for; and second, that the adversary gets no information
about any future inputs by honest senders (i.e., that
fairness as dened for detectable broadcast is guaranteed). In
particular, this means that detectable precomputation implies
detectable broadcast.
As opposed to detectable broadcast, the advantage of detectable
precomputation for broadcast is that the preparation is separated
from the actual execution of the broadcasts, i.e., only the
precomputation must be detectable. As soon as the precomputation
has been successfully completed, strong broadcast is
possible secure against any number of corrupted players.
2. GENERICPROTOCOLFORDETECTABLE
Along the lines of [13], we give constructions of protocols for
detectable precomputation, which implies detectable broadcast.
We present protocols for three models: a network of authenticated
channels with computational security (Mauth ), secure
channels with unconditional security (Msec ), and quantum channels
(Mq ). The protocols for models Mauth and Mq are more
e-cient, while the one for model Mauth is ultimately more general
(since it can be used, with small modications, in all three
models).
Note that, although stated dierently, the known results in [22,
8] and those in [25] can both be viewed in context of the second
one: In models Mauth and Msec , a temporary phase wherein
broadcast is achievable (for some reason) allows running a pre-computation
such that future broadcast will be achievable without
any additional assumptions. In Mauth , this precomputation
can simply consist of having every player p i compute a secret-
broadcast his public key
In Msec , more involved methods must be applied, but
still, the principle of the precomputation is similar: the players
broadcast some information that allows all players to consistently
compute keys for a pseudo-signature scheme among the
players.
Our construction for detectable precomputation is generic in the
sense that any \reasonable" precomputation protocol exploiting
temporary broadcast in order to allow for future broadcast can
be transformed into a protocol for detectable precomputation.
This transformation is based on an implementation of conditional
gradecast, dened below, which is a variant of graded
broadcast [9]. The independent work of Goldwasser and Lindell
[17] calls this task \broadcast with designated abort."
Definition 4 (Conditional Gradecast). A protocol among n
players, where player s (called the sender) holds an input value
xs 2 D and every player p i (i 2 [n]) nally decides on an output
value
gradecast if it satises:
Value validity: If the sender is honest then all honest
players decide on the sender's input value, y
Conditional grade validity: If all players are honest
then all players p i decide on grade
Consistency: If any honest player p i gets grade
then all honest players p j decide on the same output value
Assume set png of players in model M 2 fMauth ;
Msecg. Let  be a precomputation protocol for model M where,
additionally, players are assumed to be able to broadcast mes-
sages; and let ng be a set of protocols for model
M where each protocol  i achieves broadcast with sender p i
when based on the information exchanged during an execution
of . Furthermore, assume that  satises the independence
property of Denition 1.2 with respect to the protocols in B.
If protocol  always e-ciently terminates even if all involved
broadcast invocations fail and all protocols  i always e-ciently
terminate even when based on arbitrary precomputed information
then a protocol - for detectable precomputation can be
achieved from  and B as follows:
1. Run protocol  wherein each invocation of broadcast is
replaced by an invocation of conditional gradecast with
the same sender.
2. Each player p i computes the logical AND over the grades
he got during all invocations of conditional gradecast in
(the modied) protocol , G
3. For each player p an invocation of protocol  i is run
4. Each player p i accepts if and only if G received
during Step 3.
Note that the protocols  i in Step 3 do not necessarily achieve
broadcast since the invocation of  during Step 1 might have
failed. However, they will always e-ciently terminate by as-
sumption. We now informally argue that protocol - achieves
detectable precomputation.
Correctness. Suppose p j and pk to be honest players and suppose
that accepts. Then G invocations
of conditional gradecast during protocol  achieved
broadcast (when neglecting the grade outputs) and hence,
all protocols in B indeed achieve broadcast. Since p j ac-
cepts, all players p i broadcasted G during Step 3,
especially all honest ones, and hence all honest players accept
at the end.
Completeness. If no player is corrupted during the invocation
of protocol - then no player p i ever computes a grade
and all players accept.
Independence. Independence directly follows from the assumed
independence property of .
Before giving a more detailed view on our concrete protocols for
the models Mauth and Msec , we rst describe a protocol that
achieves conditional gradecast in both models Mauth and Msec .
Protocol CondGradecast: [with respect to sender s]
1. Sender s sends his input xs to every player; player p i receives
2. Every player p i redistributes y i to every other player and computes
grade the value y i was reconrmed by everybody
during Step 2, and else
Lemma 1. Protocol CondGradecast achieves conditional grad-
ecast for t < n.
Proof. Both validity conditions are trivially satised. On
the other hand, suppose that p i is honest and that
honest player p j sent y during Step 2, and
hence consistency is satised.
3. COMPUTATIONAL SECURITY
Let (G; be a signature scheme, i.e., secure under adaptive
chosen message attack. Here G is a key generation algorithm,
S is the signing algorithm and V is the verication algorithm.
All algorithms take a unary security parameter 1 k as input. For
simplicity, we assume that signatures are k bits long.
The Dolev-Strong protocol [8] achieves (strong) broadcast when
a consistent public-key infrastructure has been setup:
Definition 5 (Consistent Public-Key Infrastructure (PKI)).
We say that a group of n players have a consistent public-key
infrastructure for (G; has a
verication key PK i which is known to all other players and was
chosen by p i (in particular, the keys belonging to honest players
will have been chosen correctly according to G, using private
randomness, and the honest players will know their signing keys).
Note that the cheaters' keys may (and will, in general) depend
on the keys of honest players. 4
Proposition 2 (Dolev-Strong [8]). Given a consistent
PKI and pairwise authenticated channels, (strong) broadcast tolerating
any t < n cheaters is achievable using t rounds and
an overall message complexity of O(n 2 log jDj bits where
D is the message domain (including possible padding for session
IDs, etc). An adversary which makes the protocol fail with probability
" can be used to forge a signature in an adaptive chosen
message attack with probability "=n.
Let DSBroadcast denote the Dolev-Strong broadcast protocol. A
precomputation \protocol"  among n players
allowing for future broadcast is to set up a consistent infrastruc-
ture. Given broadcast channels this is very simple: have every
player generate a signing/verication key pair (SK
broadcast the verication key. Hence, by applying the generic
transformation described in the previous section we get the following
protocol for detectable precomputation:
Protocol DetPrecomp: [Protocol for Model Mauth
1. Every player p i generates a signing/verication key pair
according to G. For every player p j protocol
CondGradecast is invoked where p j inputs his public key PK j
as a sender. Every player p i stores all received public keys
i and grades g (1)
2. Every player p i computes G
3. For every player p j an instance of DSBroadcast is invoked
as a sender. Every player p i stores the
received values G (j)
ng n fig) and G (i)
4. All players p i accept if
reject otherwise.
Theorem 2. Protocol DetPrecomp achieves detectable precomputation
among n players for model Mauth tolerating any t < n
corrupted players. An adversary who can make the protocol fail
with probability " can be used to forge a signature with probability
"=n.
Proof. Completeness and independence are trivially satis-
ed. It remains to prove that the correctness condition is satis-
ed. Assume p j and pk to be two honest players and assume that
accepts. We show that hence pk also accepts: Since p j accepts
it holds that G
1. By the
denition of conditional gradecast, this implies that the players
have set up a consistent PKI and that hence any invocation of
Protocol DSBroadcast achieves broadcast. Since p j accepts, all
players during Step 3 and hence all honest
players decide to accept at the end of the protocol.
Note that Protocols DetPrecomp and DSBroadcast have another
important property, i.e., that they keep the players synchronized:
If the players accept then they terminate these protocols during
the same communication round. This can be easily veried.
As Protocol DSBroadcast requires t+1 rounds of communication
and an overall message complexity of O(n 2 log jDj +n 3 bits to
be sent by honest players, Protocol DetPrecomp requires t
rounds and an overall message complexity of O(n 3 log jDj+n 4
bits. Any later broadcasts are conventional calls to DSBroadcast.
The message complexity of Protocol DetPrecomp can be reduced
to O(n 3 (log jDj bits overall by replacing the n parallel
invocations of DSBroadcast during Step 3 by a consensus-like
protocol with default value 1. For this, the n DSBroadcast protocols
are run in parallel in a slightly modied way. In the rst
round, a sender ps who accepts simply sends bit
a signature (or no message at all), and only if he rejects sends
together with a signature on it. As soon as, during
some round accepts the value
from one or more senders ps because he received valid signatures
from r dierent players (including ps) on value
with respect to the protocol instance with sender ps then, for
excactly one arbitrary such sender ps , he adds his own signature
for 0 with respect to this protocol instance and, during the next
round, relays all r signatures to every other player, decides
on 0, and terminates. If a player never accepts value
from any sender ps then he decides on 1 after round t + 1. If
all players ps are honest and send value clearly, all
players decide on 1 at the end. On the other hand, if any correct
player decides 0 then all correct players do so. Finally, during
this protocol, no player distributes more signatures than during
a single invocation of Protocol DSBroadcast.
4. UNCONDITIONAL SECURITY WITH
PSEUDO-SIGNATURES
We now consider the applying of the same framework to the
setting of pairwise secure channels, but requiring information-theoretic
security. The basic procedures come from [25], which
is itself a modied version of the Dolev-Strong protocol, with
signatures replaced by information-theoretically secure \pseu-
dosignatures".
Proposition 3 (Pfitzmann-Waidner, [25]). There exist
protocols PWPrecomp and PWBroadcast such that if PWPrecomp is
run with access to a broadcast channel, then subsequent executions
of PWBroadcast (based on the output of PWPrecomp) achieve
strong broadcast secure against an unbounded adversary and tolerating
any t < n.
The total communication is polynomial in n; log jDj; k; log b, where
k is the security parameter (failure probability < 2 k ) and b is
the number of future broadcasts to be performed. The number of
rounds is at most 2n 2 .
The generic transformation described in Section 2 can be directly
applied to the PW-precomputation protocol resulting in a
protocol for detectable broadcast with at most r =  7
communication rounds and an overall message complexity of bits
polynomial in n and the security parameter k. However, most of
the PW-precomputation protocol consists of fault localization,
i.e., subprotocols that allow to identify players that have been
misbehaving. These steps are not required in our context since
we are only interested in nding out whether faults occurred or
not. We now give a protocol for the precomputation of one single
broadcast with sender s where these steps are stripped o.
Thereby, as in [25], log n)) and the key size is
log log log jDj)).
1. For (j = s; A), and (j; A), (j; B) (j ng n fsg) in parallel:
2. For
3. If i 6= j: select random authentication key
4. For
5. 8p h (h 6= i) agree on a pairwise key K (')
6. Broadcast  2' 1
7. If broadcast \accept" or \reject";
8. Decide to accept (h i := 1) if and only if all signers p j sent message
\accept" with respect to (j; A) and (j; B);
otherwise reject (h i := 0);
The proof of the following lemma follows from [25]:
Lemma 4. Given a broadcast channel, Protocol SimpPWPrecomp
detectable precomputation for broadcast (with respect to Protocol
PWBroadcast). It requires three rounds, two of which use the
broadcast channel.
Furthermore, for our purpose, Step 7 does not require broadcast
but can be done by simple multi-sending, since invocations
of precomputed broadcast will follow anyway (see Protocol
DetPrecomp in Section 4).
Protocol DetPrecomp: [Model Msec , for b later broadcasts]
1. Execute protocol SimpPWPrecomp for b
wherein each invocation of broadcast is replaced by an invocation
of Protocol CondGradecast.
2. Every player p i computes G
where the
are all grades received during an invocation of conditional
gradecast during Step 1 and h i is the bit indicating whether
accepted at the end of Step 1.
3. For every player p j an instance of PWBroadcast is invoked
as a sender. Every player p i stores the
received values G (j)
ng n fig) and G (i)
4. All players p i accept if
reject otherwise.
Again, as in the protocol for model Mauth of the previous sec-
tion, the parallel invocations of Protocol PWBroadcast during
Step 3 can be replaced by a consensus-like protocol saving a
factor of n for the bit-complexity of the whole protocol.
Theorem 3. Protocol DetPrecomp achieves detectable precomputation
for b future broadcasts among n players for model Msec
tolerating any number t < n of corrupted players with the following
property: If, for the underlying PWPrecomp, a security
parameter of at least chosen then the
overall error probability, i.e., the probability that either Protocol
DetPrecomp or any one of the b broadcasts prepared for fails,
is at most 2 k .
Proof. The proof proceeds along the lines of the proof of
Theorem 2. The error probability follows from the analysis
in [25] for one single precomputation/broadcast pair. Invoking
PWPrecomp with security parameter k0 hence implies an overall
error probability of at most (n
Protocol SimpPWPrecomp requires 4 rounds of message exchange
and an overall message complexity of O(n 7 log log jDj(k0 +log n+
log log log bits where k0 is the security parameter of the
underlying PWPrecomp and D is the domain of future messages to
be broadcast (including possible padding for session IDs, etc.
Protocol PWBroadcast requires t +1 rounds of message exchange
and an overall message complexity of O(n 2 log jDj
log n) 2 ) bits. Since Protocol DetPrecomp precomputing for b
later broadcasts invokes Protocol SimpPWPrecomp (n
in parallel and Protocol PWBroadcast n times in parallel, it requires
overall t+5 communication rounds and an overall message
complexity of
O(n 3 log jDj
log log log
bits to be sent by correct players. Again, as the protocols presented
in the previous section, if the players accept then they
terminate Protocols DetPrecomp and PWBroadcast during the
same communication round.
Furthermore, as follows from Proposition 3, using the recycling
techniques in [25], the bit complexity of Protocol DetPrecomp can
be reduced to polylogarithmic in the number b of later broadcasts
to be precomputed for, i.e., to polynomial in n, log jDj, k, and
log b.
5. UNCONDITIONAL SECURITY WITH
QUANTUM SIGNATURES
In this section we consider a third network model Mq , in which
participants are connected by pairwise authenticated channels
as well as pairwise (unauthenticated) quantum channels. As for
Msec , we require unconditional security with a small probability
of failure.
Now one can always construct secure channels on top of this
model by using a quantum key distribution protocol (e.g. Bennett-
Brassard [3]). This requires adding two rounds at the beginning
of the protocol. For noiseless quantum channels, agreeing on
a key of ' bits requires sending ' log ') qubits and
classical bits [1]. Note that the key distribution
protocol may fail if the adversary intervenes, but in such a case
the concerned players can set their grades to 0 in the later agreement
protocol and all honest players will abort. All in all, this
yields protocols with similar complexity to those of the previous
section.
One can improve the complexity of the protocols signicantly by
tailoring the pre-computation protocol to the quantum model,
and using the quantum signatures of Gottesman and Chuang [19]
instead of the pseudosignatures of [25]. The idea is to apply the
distributed swap test from [19] to ensure consistency of the distributed
quantum keys. As in [25], one gets a broadcast protocol
by replacing classical signatures in the Dolev-Strong protocol [8]
with quantum signatures. Note that quantum communication is
required only in the very rst round of the computation, during
which (possibly corrupted) EPR pairs are exchanged. Any
further quantum transmissions can be done using quantum tele-
portation. Authentication of the initial EPR transmissions can
be done with the protocols of Barnum et al. [1].
Theorem 4. There is a protocol which achieves detectable
precomputation for b future broadcasts among n players for model
Mq tolerating any number t < n of corrupted players. The protocol
rounds and O(k0n 5 b0) bits (qubits) of com-
munication, where
6. SECURE MULTI-PARTY COMPUTATION
The results of the previous sections suggest two general techniques
for transforming a protocol  which assumes a broadcast
channel into a \detectable" protocol  0 which only assumes pair-wise
communication channels, but which may abort. Suppose
that there is an upper bound r on the number of rounds of interaction
required by  (such a protocol is called \xed-round").
The rst transformation is straightforward, and is also used in
[13]: First, run a protocol for detectable precomputation for
broadcast. If it is succesful, then run , replacing calls to the
broadcast channel with executions of an authenticated broadcast
protocol 2 . The resulting protocol takes t rounds.
The second transformation is suggested by the constructions of
the previous sections. First run , replacing all calls to the
broadcast channel with executions of CondGradecast. Next, run
a detectable broadcast protocol to attempt to agree on whether
or not all the executions of CondGradecast were succesful (i.e.
each player uses the protocol to broadcast the logical and of
his grades from the executions of CondGradecast). If all of the
detectable broadcasts complete successfully with the message 1,
then accept the result of ; otherwise, abort. The resulting
protocol takes O(r rounds. A similar transformation is also
discussed by Goldwasser and Lindell [17] (see below).
Remarks: If protocol  achieves unconditional security then
secure channels are required for both these transforma-
tions. For computational security, authenticated channels are
su-cient. Moreover, when applying the rst transformation in
the computational setting, no bound is needed ahead of time on
the number of rounds of interaction (though it should nonetheless
be polynomial in the security parameter).
At an intuitive level, the rst transformation preserves any security
properties of , except for robustness and zero error: robustness
is lost since the adversaries can force the protocol to
fail by interfering with the initial precomputation protocol, and
zero error is lost since detectable broadcast must have some small
2 Note that when using an authenticated broadcast protocol several
times, sequence numbers need to be added to the broadcast
messages to avoid replay attacks [18, 23].
probability of error when t  n=3 (by the result of Lamport [21]).
In the following section, we formalize this intuition for the case
of secure multi-party computation (mpc).
The second transformation is more problematic: if the protocol
fails partway through, the adversary may learn information he
is not supposed to. Moreover, if the protocol has side eects
such as the use of an external resource, then some of those side
eects may occur even though the protocol aborts. Nonetheless,
in the case of multi-party computing, the transformation may
be modied to avoid some of these problems.
Multi-party Computation for t < n
Informally, an mpc protocol allows players with inputs x1 ; :::; xn
to collectively evaluate a function f(x1 ; :::; xn) such that cheaters
can neither aect the output (except by their choice of inputs),
nor learn anything about honest players' inputs except what can
be gleaned from the output. For simplicity, we consider deter-
ministic, single-output functions (this incurs no loss of general-
ity). Also, for this section of the paper, we restrict our attention
to static adversaries (i.e. the set of corrupted players is decided
before the protocol begins).
The security of multi-party computation is usually dened via
an ideal model for the computation and a simulator for the pro-
tocol. In the ideal model, a trusted third party (T T P) assists the
players, and the simulator transforms any adversary for the real
protocol into one for the ideal model which produces almost the
same output 3 . The standard ideal model for mpc when t  n=2
essentially operates as follows [14]: The players hand their inputs
to the T T P, who computes the output (which is a special
any of the corrupted parties refuse to cooperate).
If Player 1 is honest, then all parties get the output. If Player
1 is corrupted, then the adversary A rst sees the output and
then decides whether or not to abort the protocol. If A decides
to abort, then the T T P sets the output to ?. Finally, the T T P
hands this possibly aborted output to the honest parties. The
notion of security corresponding to this ideal model is called \the
second malicious model" in [14], and \secure computation with
abort" in [17].
Given a broadcast channel, there is a protocol for this denition
of mpc tolerating any t < n static cheaters. This comes essentially
from Goldreich, Micali and Wigderson [15] and Beaver-
Goldwasser [2], though a more careful statement of the deni-
tion, protocol and proof of security appears in Goldreich [14].
That work also points out that replacing calls to the broadcast
channel with an authenticated broadcast protocol | given
a signature infrastructure | does not aect the security of the
protocol 4 . Applying the rst transformation to this protocol, we
obtain:
Theorem 5. Suppose that trapdoor one-way permutations ex-
ist. Then there is a secure mpc protocol (following the denition
of [14]) for any e-ciently computable function in the model of
authenticated channels, which tolerates any t < n.
3 The output here is the joint distribution of the adverary's view
and the outputs of the honest players.
One point which [14] does not discuss explicitly is that sequence
numbers are needed to ensure the independence of the various
executions of the authenticated broadcast protocol. This is not
a problem since the network is synchronous and so the sequence
numbers can be derived from the round number.
Proof. (sketch) The only dierence between our protocol
and that proved correct in Goldreich [14] is the initial detectable
precomputation phase. This allows the adversary to abort the
protocol before he gets any information on the honest parties'
inputs. However, she already has that power in the standard
ideal model (she can refuse to provide input to the T T P).
To construct a simulator S 0 for  0 , we can modify the simulator
S constructed in [14] to add an additional initial phase in which
simulates the detectable precomputation protocol, using the
signature keys of the (real) honest parties as the inputs for the
simulated ones. If the protocol aborts, then S 0 sends the input
? on behalf of all cheating parties to the T T P. Otherwise, S 0
runs the simulator S, using the output of the precomputation
phase as the signature infrastructure. The correctness of this
simulation follows from the correctness of the original simulator
S.
Round-e-cient Multi-party Computation
The protocol above is not very e-cient | the rst transformation
multiplies the round complexity of the original protocol by
t. Instead, consider applying the second transformation to an
mpc protocol: replace every call to the broadcast channel with
an invocation of Conditional Gradecast, and agree at the end of
the protocol on whether or not all the broadcasts were successful
by running the detectable broadcast of Section 3.
As mentioned above, this transformation must be made carefully.
In multi-party computing, it is important that the transformed
protocol not leak any more information than did the original
protocol. If honest players continue to run the protocol after an
inconsistent Conditional Gradecast has occurred, the adversary
could exploit inconsistencies to learn secret values (say by seeing
both possible answers in some kind of cut-and-choose proof). To
ensure that this is not a problem, once an honest player has computed
a grade in one of the executions of CondGradecast,
he no longer continues running the original protocol . Instead,
he only resumes participation during the nal detectable broadcast
phase, in which players agree on whether to accept or reject.
As pointed out by Goldwasser and Lindell [17], the resulting
protocol  0 achieves some sort of secure computation, but it is
not the denition of [14]. In particular, that denition implies
partial fairness, which  0 does not satisfy.
A protocol is fair if the adversary can never learn more about the
input than do the honest players. Fairness is in fact unavoidable
for the setting of t  n=2, since it is unavoidable in the 2-party
setting (Cleve [6], Goldwasser and Levin [16]). A protocol is
partially fair if there is some designated player P1 such that when
P1 is honest, the protocol is fair.  0 is not even partially fair
since the adversary may wait until the end of the computation,
learn the output, and still force the honest players to abort.
Goldwasser and Lindell [17] give a similar transformation to this
second one, in which there is no detectable broadcast phase at
the end. They provide a rigorous analysis, and prove that it
achieves a denition of secure computation in which players need
not agree on whether or not the protocol aborted. They additionally
show how that construction can be modied to achieve
partial fairness. One can think of the protocol  0 as adding a detectable
broadcast phase to the initial protocol of [17], to ensure
agreement on the computation's result.
7. NON-UNISON STARTING AND PKI
For all previous \detectable protocols" it was implicitly assumed
that all players start the protocol in the same communication
round. This requires agreement among the players on which
protocol is to be run and on a point of time when the protocol
is to be started. We now argue that this assumption is unnecessary
| not even agreement on the player set among which the
protocol will be run.
Coan, Dolev, Dwork, and Stockmeyer [7] gave a solution for the
\Byzantine agreement with non-unison start" problem, a problem
related to the ring squad problem introduced by Burns and
Lynch [4]. Given the setup of a consistent PKI, their protocol
achieves broadcast for t < n even when not all honest players
start the protocol during the same round, i.e., the broadcast can
be initiated by any player on the
y. It turns out that this idea is
also applicable to detectable broadcast. This allows a player pI
who shares authenticated (or secure) channels with all members
of a player set P 0 to (unexpectedly) initiate a protocol among
the players in for a detectable precomputation.
Let such a player pI be called the initiator and the players in
be called the initiees of the protocol. The following protocol
description is split into the initiator's part and the initiees' part.
Protocol InitAdHocComp: [Initiator pI
1. Send to P 0 an initiation message containing a unique session
identier id, the specication of the player set P 0 and of a
multi-party computation protocol  among player set
g.
2. Perform protocol DetPrecomp among P 0 to precompute for all
broadcast invocations required by protocol . In the nal
\broadcast round", instead of broadcasting the value G I to
indicate whether all conditional gradecast protocols achieved
broadcast, the value G I ^ S I is broadcast where S I indicates
whether all players in P 0 synchronously entered the precomputation
protocol and always used session identier id.
3. Accept and execute protocol  if and only if G I ^ S I and all
players in P 0 broadcasted their acceptance at the end.
Protocol AdHocComp: [Initiee
1. Upon receipt of an initiation message by an initiator
decide whether you are interested to execute an instance of
among player set P .
check that the specied id is not being used in any concurrent
invocation.
check whether
check whether there are authenticated (or secure) channels
between p i and all other players in P 0 [ fp I g as required
by protocol .
2. If all checks in Step 1 were positive then perform protocol
among P 0 to precompute for all broadcast invocations
required by protocol . In the nal \broadcast round",
instead of broadcasting the value G i to indicate whether all
conditional gradecast protocols achieved broadcast, the value
players
in P 0 synchronously entered the precomputation protocol and
always used session identier id.
3. Accept and execute protocol  if and only if G
players in P 0 broadcasted their acceptance at the end.
Note that the rst check in Step 1 of Protocol AdHocComp implicitly
prevents the adversary from \spamming" players with
initiations in order to overwhelm a player with work load. A
player can simply ignore initiations without aecting consistency
among the correct players.
Theorem 6. Suppose there is a player set P 0 and a player pI
such that pI shares authenticated (or secure) channels with every
player in P 0 (whereas no additional channels are assumed between
the players in P 0 ). Then pI can initiate a protocol among
player set that achieves the following properties
for t < n:
All honest players in P either commonly accept or reject
the protocol (instead of rejecting it is also possible that a
player ignores the protocol, which is an implicit rejection).
If they accept, then broadcast or multi-party computation
will be achievable among P (with everybody knowing this
If all players in P are honest and all players are connected
by pairwise authenticated (or secure) channels then
all players accept.
In particular, such a protocol can be used in order to detectably
set up a consistent PKI without the need for a trusted party.
8.

ACKNOWLEDGEMENTS

We thank Sha Goldwasser and Yehuda Lindell for discussions
which led to a substantial improvement of the treatment of the
results of Section 6, as well as for pointing out errors in earlier
versions of this work. We also thank Jon Katz, Idit Keidar, and
Ra Ostrovsky for helpful discussions. The work of Adam Smith
was supported by U.S. Army Research O-ce Grant DAAD19-
00-1-0177.
9.



--R


Multiparty computation with faulty majority.
An update on quantum cryptography.
The byzantine
Adaptively secure multi-party computation
Limits on the security of coin ips when half the processors are faulty (extended abstract).
The distributed
Authenticated algorithms for Byzantine agreement.
An optimal probabilistic protocol for synchronous Byzantine agreement.
Easy impossibility proofs for distributed consensus problems.
Minimal complete primitives for unconditional multi-party computation
Quantum solution to the Byzantine agreement problem.
Unconditional Byzantine agreement and multi-party computation secure against dishonest minorities from scratch
Secure multi-party computation
How to play any mental game
Fair computation of general functions in presence of immoral majority.
Secure computation without a broadcast channel.
Byzantine agreement with authentication: Observations and applications in tolerating hybrid and link faults.
Quantum digital signatures.

The weak Byzantine generals problem.
The Byzantine generals problem.
On the composition of authenticated byzantine agreement.
Reaching agreement in the presence of faults.

--TR
Easy impossibility proofs for distributed consensus problems
Limits on the security of coin flips when half the processors are faulty
An update on quantum cryptography
How to play ANY mental game
The distributed firing squad problem
Multiparty computation with faulty majority
Adaptively secure multi-party computation
An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
Reaching Agreement in the Presence of Faults
The Weak Byzantine Generals Problem
The Byzantine Generals Problem
On the composition of authenticated byzantine agreement
Minimal Complete Primitives for Secure Multi-party Computation
Fair Computation of General Functions in Presence of Immoral Majority
Unconditional Byzantine Agreement and Multi-party Computation Secure against Dishonest Minorities from Scratch

--CTR
S. Amitanand , I. Sanketh , K. Srinathant , V. Vinod , C. Pandu Rangan, Distributed consensus in the presence of sectional faults, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.202-210, July 13-16, 2003, Boston, Massachusetts
Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated Byzantine Agreement, Journal of the ACM (JACM), v.53 n.6, p.881-917, November 2006
byzantine agreement;multi-party computation;public-key infrastructure;broadcast;quantum signatures