Asynchronous group key exchange with failures.
Group key exchange protocols allow a group of servers communicating over an asynchronous network of point-to-point links to establish a common key, such that an adversary which fully controls the network links (but not the group members) cannot learn the key. Currently known group key exchange protocols rely on the assumption that all group members participate in the protocol and if a single server crashes, then no server may terminate the protocol. In this paper, we propose the first purely asynchronous group key exchange protocol that tolerates a minority of servers to crash. Our solution uses a constant number of rounds, which makes it suitable for use in practice. Furthermore, we also investigate how to provide forward secrecy with respect to an adversary that may break into some servers and observe their internal state. We show that any group key exchange protocol among n servers that tolerates tc > 0 servers to crash can only provide forward secrecy if the adversary breaks into less than n - 2tc servers, and propose a group key exchange protocol that achieves this bound.
INTRODUCTION
Group Key Exchange (GKE) protocols allow a group of
servers communicating over a complete network of point-to-
point links to establish a common session key such that anyone
outside the group that can only observe the network traffic
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
July 25-28, 2004, St. Johns, Newfoundland, Canada.
cannot learn this key. Such a session key can later be used to
achieve cryptographic goals like for example multicast message
confidentiality, or multicast data integrity. Hence, GKE
protocols are essential for applications such as secure video-
or tele-conferencing, or other collaborative applications. To
model environments like the Internet, one assumes an asynchronous
network where the scheduling of messages is determined
by an adversary, and where the servers do not have access
to a common clock.
The main goals of a GKE protocol are to ensure secrecy of
the session key, and to ensure that every member of the group
eventually terminates the protocol and computes the session
key. So far, GKE protocols have been designed to meet these
goals only as long as all members of the group follow the protocol
specification [8, 26, 3, 7]. These solutions have the draw-back
that if only a single server crashes, then no member of
the group will terminate the protocol. This makes such protocols
specifically vulnerable to denial of service attacks, as the
execution time of the protocol is determined by the slowest
member of the group.
One way to solve this problem, explored by Amir et al. [2],
is to base GKE on a view-based group communication system
(GCS), which provides the abstraction of the "currently live
nodes" to all servers in a consistent way (Chockler et al. [15]
provide a survey of GCS). Since the GCS can detect crashes
among the servers also during the execution of a GKE proto-
col, the protocol can react accordingly; as GCSs rely on time-outs
to detect crashed participants, the approach leads to solutions
that are not purely asynchronous and subject to timing
attacks, however.
In this paper we propose the first GKE protocol in a purely
asynchronous model that terminates for every member as long
as at least a majority of the participants remain up, which is
optimal for this model. Our solution is conceptually simple
and efficient, which makes it suitable for practice. In particu-
lar, it consists of the following two stages. In the first stage, the
group members exchange keying information using two communication
rounds and a total of O(n 2 ) messages, where n
denotes the size of the group. In the second stage, they execute
a consensus protocol to select the contributions from
the first stage from which the session key is computed. The
protocol may use randomized asynchronous consensus in the
fully asynchronous model or a consensus protocol in the asynchronous
model augmented with a failure detector [14]. In the
latter case, our approach yields a modular solution for GKE in
the same model as the GCS-based protocol mentioned above.
Comparing the efficiency of our construction with the most
efficient solution for GKE without failures [8] shows that the
price we pay for tolerating failures lies only in the consensus
protocol executed in the second stage. We also show that the
communication complexity of our construction is nearly op-
timal. In particular, we show that given an optimal solution
for consensus, our construction yields a solution for GKE that
uses only O(n 2 ) messages and O(1) communication rounds
more on average than an optimal solution for GKE with failures

Following the approach of Steiner [27], we analyze the security
of our protocol in the framework for asynchronous re-active
systems proposed by Pfitzmann and Waidner [23]. In
particular, we first specify the target behavior of a GKE protocol
in terms of an idealized service, and then show that our
protocol has the same input-output behavior as this idealized
service. This approach has the benefit of guaranteeing com-
posability, i.e., the security of any application relying on an
ideal service for GKE remains the same when our real protocol
is used to implement the ideal service.
We first prove the security of our construction in the so-called
corruption model with failures, where the adversary
may schedule and observe the network, crash servers, but
not break into a server and observe its internal state. We show
that in this model, our protocol tolerates tc < n=2 servers that
crash, which is optimal for this setting.
We then investigate how to provide forward secrecy in the
strong corruption model, where the adversary is additionally
allowed to break into some servers and to observe their internal
state. Such break-ins should only compromise the security of
the session keys that are being generated during the attack, but
not the keys generated previously or afterwards. We first show
that if a GKE protocol tolerates tc > 0 servers that crash, then
it can tolerate strictly less than n 2tc break-ins. We then
show how to build a GKE protocol with this optimal resilience.
Our construction is also practical: It uses one execution of a
consensus protocol, and additionally O(n 2 ) messages in three
rounds.
Related Work. One can classify previous work on GKE along
two dimensions: The assumptions made on the communication
links, and the framework used for proving security. Along
the first dimension, one can distinguish between GKE protocols
that assume an authentic network (as we do) [19, 8, 26,
24, 27], and GKE protocols that rely on a-priori distributed
public and private keys (as for example provided by a public-key
recent paper of Katz and
Yung [21] closes the bridge between these two approaches by
showing how any GKE protocol built for an authentic network
can be "compiled" into a GKE protocol for an insecure net-work
with a-priori distributed public and private keys. The
compilation only adds one additional communication round
and O(n 2 ) messages.
With respect to the framework used for proving security, one
can identify two approaches. One approach, taken by Bresson
et al. [7] and by Katz and Yung [21], is to extend the frame-work
for modeling two-party key exchange proposed by Bellare
et al. [5] to the n-party case. Another approach, taken by
Steiner [27] and by this work, is to use a general framework for
modeling asynchronous reactive systems - such as the one of
Pfitzmann and Waidner [23] or the one of Canetti [12] - and
define and prove security therein. The advantage of using such
a framework is that security is preserved under modular composition

Some of the above-mentioned works [3, 26, 24, 7] also address
the dynamic case of GKE, where servers may join or
leave the group and the session key must be updated whenever
this occurs. Recently, Amir et al. [1] showed how the
dynamic join and leave protocols of Steiner et al. [26] can
be integrated with a view-based GCS to maintain a common
group key, which is later used to encrypt the communication
among the group. The group key has to be updated whenever
the underlying GCS detects a change in the group structure.
This is accomplished as outlined in [2], i.e., by running the
corresponding dynamic GKE protocol whenever servers join
or leave. In case that the GCS detects nested leaves, i.e., detects
leaving servers during the execution of a (dynamic) GKE
protocol, this protocol is aborted and a basic GKE protocol is
run from scratch among the remaining servers. Establishing a
key in case of nested leaves can also be seen as crash-tolerant
GKE. Note that if tc servers crash one by one, this approach
leads to tc sequential executions of a basic GKE protocol. If
the basic GKE protocol of Steiner et al. [26] is used, this results
in O(tcn) messages and O(tcn) rounds. Furthermore, as
GCSs rely on timeouts to detect crashes, this approach is not
purely asynchronous and subject to timing attacks.
Organization. In the next section, we introduce our system
model and give the formal definitions for GKE and consen-
sus. In Section 3, we present our construction for GKE with
failures in the weak corruption model, and elaborate on its op-
timality. In Section 4, we first introduce the strong corruption
model and adjust the definition of GKE to this model. We then
prove an upper bound on the number of break-ins one can tolerate
for GKE with failures in the strong corruption model,
and finally show how to build a GKE protocol with this optimal
resilience.
2. PRELIMINARIES
2.1 The Framework
Our computational model is parameterized by a security parameter
k; a function (k) is called negligible if for all c > 0
there exists a k0 such that (k) < 1
k c for all k > k0 . Two
ensembles fvar k gk 2 N and fvar 0
k gk2N of random variables
(or probability distributions) are called computationally
indistinguishable if for every algorithm D (the distinguisher)
that runs in probabilistic polynomial-time in its first input, the
following quantity is negligible:
Throughout the paper, we abbreviate
this by saying that "var k and var k 0 are indistinguishable",
and write "var k  var k 0 ".
We will study our protocols in the framework for universally
composable asynchronous reactive systems of Pfitzmann and
Waidner [23]. We sketch a simplified version of the model.

Overview

. We model a protocol  as a collection of n probabilistic
polynomial-time (in Turing machines
n called the servers, which communicate
over an authentic network NET modeled as a PPT ITM.
We call the collection fNET; M
n g a real system for
protocol  in network NET and denote it by Sys real;
n . We
model protocol-specific input and output of a server M
in
terms of messages that occur at M
's input and output connections
in i and out i , respectively. We call the set I of the input-output
connections of all servers the interface 1 of Sys real;
n .
1 For readers familiar with [23]: The interface corresponds to
the specified ports.
We model an execution of a protocol  in a network NET
as a run of the real system Sys real;
augmented with two PPT
ITMs: a user H and an adversary A real . We call the collection
fSys real;
real g a real configuration for . The user
H represents a higher-level application that builds on top of
the servers. It may interact with the servers through the interface
(or a subset thereof), and may also communicate with
A real at arbitrary points during the protocol. A real may attack
the servers and schedule the network. We model attacks on
a server M
in terms of special messages that may occur at
a designated input connection cor in i of M
(also part of the
interface). For now, we consider the weak corruption model,
where the only available attack of the adversary is to crash a
server; if this happens, the server halts, i.e., does not participate
in the protocol anymore. In Section 4, we will discuss the
strong corruption model, where also break-ins are allowed.
We describe the security properties of  in terms of a service
f that the corresponding real system Sys real;
should guarantee
at its interface. Formally, we define the service f in terms
of an ideal system Sys ideal;f
n . This ideal system has the same
interface I as the real system, but comprises only a single PPT
ITM called the trusted host TH f
n that serves the interface. It
also runs in a configuration with a user H and an adversary
A ideal (both modeled as PPT ITM), where A ideal may communicate
with TH f
n at arbitrary points during the protocol. This allows
to model the non-determinism in the ideal service f which
may be controlled by the adversary.
The security of the protocol  is then defined by requiring
that whatever can happen to an arbitrary user H in the real system
Sys real;
could also happen to the same user in the ideal
system Sys ideal;f
cannot distinguish an ideal configuration
from a real one. In this case, we say that Sys real;
n is
as secure as Sys ideal;f
n . The standard argument how to prove
this notion of security is a constructive one. Specifically, one
shows how to construct for any user H and any adversary A real
an ideal adversary A ideal such that H cannot distinguish the
corresponding real configuration from the ideal configuration.
The framework also allows modular composition of protocols
by describing a protocol  that runs on top of an ideal service
g. We model this as a hybrid system Sys hybrid; g
consisting
of the real system Sys real;
for  with an ideal sub-system
Sys ideal;g
n . In such a hybrid system, the servers M
have access to Sys ideal;g
n as if they were the user of this sys-
tem. An important property of the framework is that if a real
system Sys real;
n is as secure as Sys ideal;g
, then the real system
Sys real;
n (where the servers have access to Sys real;
instead
of Sys ideal;g
n ) is as secure as Sys hybrid; g
. Below, we add a few
more details. For a more elaborate treatment of the framework
we refer to [23].
Ideal and Real Configurations. On an abstract level, a real or
an ideal configuration can be seen as a set of PPT ITM called
machines, that are connected with each other through communication
tapes [18] and may interact. For every communication
tape there is exactly one machine that can write to the tape, and
another machine that can read from the tape. We also call such
a communication tape a connection. Figure 1 shows an example
of a configuration of the real and the ideal system for a
protocol  and a service f, respectively; it shows the connections
(denoted by arrows) and the interface (the connections
that cross the dashed lines) of the configurations.
Executing a Configuration: The execution of a configuration
is called a run and is defined as follows. 2 At the beginning
of the run, every machine is initialized with the
security parameter k. Then, the run proceeds in steps.
In the first step, a designated machine called the master
scheduler is activated (for the configurations in this
paper, the master scheduler is the adversary). In every
step, the currently active machine may read its communication
input tapes, perform some computation (possi-
bly involving random choices), and then write a message
to one of its communication output tapes. It then
either halts or terminates the activation. In either case,
the machine which can read from the tape that has been
written to is activated and proceeds with the next step.
If this machine has halted before, or no message was
written to a tape, then the master scheduler is activated
instead. This process continues until the master scheduler
halts.
The Network: The network NET provides authentic communication
among the servers with scheduling determined
by the adversary. It connects to every server M  i through
connections net out i and net in i , and connects to the
adversary A real through the connections to Adv net and
from Adv net , and works as follows. A server M
can
send a message m to M
by sending the message (m;
on the connection net out i to NET. If this happens,
NET stores (m; i; j) in a collection M , and sends the
tuple (m; i; j) on the connection to Adv net to the ad-
versary. Similarly, A real can schedule a message m to
be delivered from M  i to M  j by sending (m; i;
the connection from Adv net . If this happens, and if
and outputs (m; i) to M
receives m
from M  i . We say that the adversary delivers all messages
among M
, if at the end of the run, the
collection M does not contain any tuples (m;
message m.
The Interface: The interface of a real and an ideal system
comprises the connections in i , out i , and cor in i for
n]. The first two connections are used to invoke the
provided by the systems, and to receive service-specific
output from the systems, respectively. The connections
cor in i for are used to model attacks
of the adversary on a server i. These connections have
to be part of the interface because attacks on the servers
will affect the service that a system provides. For now,
we describe the weak corruption model, where the adversary
may only crash a server i, modeled as a message
(crash) sent on the connection cor in i (see Section 4
for the strong corruption model, where also break-ins
are allowed). If this happens in a real configuration,
then M
outputs (crash) at cor out i and halts. If this
happens in an ideal configuration, then TH f
outputs
(crash; i) at to Adv th .
Other Connections: The trusted host TH n also connects to
A ideal through connections to Adv th and from Adv th .
These connections are used to model the non-determinism
2 The model of execution described here is not as general as
the model described in the original work [23], but will be sufficient
for our purpose.
real
A
net_in
net
I
Sys real
in out in out cor_in
cor_in
cor_out
net_in
net_out
net_out
cor_out ideal
A
th
th
Sys n
I
in out in out cor_in
cor_in

Figure

1: Configurations of the real and ideal systems for protocol  and service f, respectively.
in the ideal service f, which may be controlled by the ad-
versary. Furthermore, every server M
i connects to A real
through connections cor out i . These connections are
used to model effects of an attack, e.g., in Section 4 we
will use these connections for revealing server internal
data to the adversary as a result of a break-in.
We are now ready to state the definition for a real system
Sys real;
n to be as secure as an ideal system Sys ideal;f
n . For this
purpose, let V real;
n;H;A real
denote the probability distribution of
the view of H (the internal state of H and all messages that H
sees) in a run of Sys real;
n with security parameter k, configured
with H and A real , and let V ideal;f
n;H;A ideal
(k) be defined analogously

We say that Sys real;
n is as secure as Sys ideal;f
if for all users H, and all real adversaries A real , there exists
an ideal adversary A ideal such that the distribution ensembles
n;H;A real
(k)gk2Nand fV ideal;f
n;H;A ideal
(k)gk2N are computationally
indistinguishable.
Composition. The framework allows to describe protocols in
a modular way, i.e., a protocol  may build on a sub-protocol .
Such a composition is modeled as a real system Sys real;
comprising the two systems Sys real;
n and Sys real;
, where the
servers of Sys real;
have access to the sub-system Sys real;
n as
if they were the user of this system. To ensure that an attack
on a server M
also affects the sub-system, we assume that the
connection cor out i of a server M  i is linked to the connection
cor in i of server M
outputs (crash) on cor out i ,
then M
receives (crash) on cor in i . The sub-system may also
be an ideal system, in which case we call the entire system
hybrid. The following composition theorem is an important
property of the framework [23].
Theorem 1 (Composition Theorem [23]) If a hybrid system
Sys hybrid; g
n consisting of a real system Sys real;
n with sub-system
Sys ideal;g
n is as secure as an ideal system Sys ideal;f
n , and if a
real system Sys real;
n is as secure as the ideal system Sys ideal;g
then the real system Sys real;
n consisting of Sys real;
n with sub-system
Sys real;
n is at least as secure the ideal system Sys ideal;f
n .
Complexity Measures. We will measure the complexity of a
protocol  in terms of its expected message complexity M(),
and its expected round complexity R(). The first measure
represents the bandwidth required by the protocol, and is defined
as follows. Let M H;A real () denote an upper bound on
the expected number of messages that the servers send across
the network in a run of Sys real;
configured with H and A real ,
where the expectation is taken over the random choices of the
servers. Then, M() is the maximum of M H;A real () over all
users H and adversaries A real .
The round complexity measures the running time of the pro-
tocol. To define it, we assign round numbers to the messages
sent by servers across the network as follows. Note that a
server only sends a message m across the network in response
to an input from the user or in response to a message m 0 from
the network. In the first case, we assign round number 0 to m,
and in the second case, we assign round number r + 1 to m,
where r is the round number of m 0 . Let R H;A real () denote an
upper bound on the expected highest round number assigned
to a message in a run of Sys real;
configured with H and A real ,
where the expectation is taken over the random choices of the
servers. Then, R() is the maximum of R H;A real () over all
users H and adversaries A real .
2.2 The Ideal System for Group Key Ex-
change
Our ideal system Sys ideal;gke
n for group key exchange models
how n servers repeatedly establish a session key. In particular,
we say a server i starts a session with tag ID when an input
(start; ID) occurs at in i (ID is an arbitrary bit string and
represents a unique identifier for the session). Similarly, we
say a server i finishes a session with tag ID when an output
(nish; ID; key) occurs at out i .
Our trusted host TH gke
n models the traditional security properties
that one expects from a GKE protocol. In particular, it
guarantees that the session key of every session ID is generated
independently at random; this property is sometimes also
called freshness. Furthermore, it guarantees mutual key
authentication, which means that every server computes the
same key in a session ID . Definition 2 below captures these
ideas more formally. We do not yet address forward secrecy,
as this becomes only an issue if the adversary can break into
a server and learn its internal state (we discuss this model in
Section 4).
Definition 2 The ideal system Sys ideal;gke
n for group key exchange
consists of the trusted host TH gke
given by the following
transition rules:
Init: At system initialization, it sets S [i] ;, F [i] ; for
Start: When a server i starts a session with tag ID , the trusted
host adds ID to the set S [i], and outputs the message
ID ;i) to the adversary.
When the adversary inputs (nish; ID ;i) where ID 2
first adds ID to the set F [i]. Next,
at random over f0; 1g k .
Finally, it outputs (deliver; ID; [ID]) at out i .
Recall that our goal is to build a GKE protocol  that is not
only secure, but also guarantees to terminate for every server
even if up to tc servers crash. This is captured by the following
definition of a tc -resilient group key exchange protocol.
Definition 3 We call a protocol  a tc -resilient group key exchange
protocol, if Sys real;
n is as secure as Sys ideal;gke
n , and if
for every run of a configuration of Sys real;
n where at most tc
servers crash, the following holds: If all non-crashed servers
start a session ID , then they all finish session ID , provided
that the adversary delivers all messages among non-crashed
servers.
2.3 The Ideal System for Consensus
In a consensus protocol, every server receives as input a bit
string of some length l(k), and produces as output some bit
string of length l(k). The goal is that all servers output the
same bit string, and that this bit string corresponds to the input
of at least one server.
Below we give the ideal system for consensus, which will
serve as building block in our construction for a GKE pro-
tocol. It models how n servers repeatedly and concurrently
agree on bit strings of some length l(k), where every consensus
instance is identified by a tag ID . We model that a server
starts a consensus instance with tag ID and input v by a message
(propose; ID; v) that occurs at in i . If this happens, we
also say server proposes v for ID . Similarly, we model that
a server terminates a consensus with tag ID and value v 0 by a
message (decide; ID; v 0 ) that occurs at out i . In this case, we
say server
Definition 4 The ideal system Sys ideal;cons
n for consensus consists
of the trusted host TH cons
given by the following transition
rules:
Init: At system initialization, TH cons
sets
-[ID] ? for all ID .
Propose: If a server i proposes v i for ID , TH cons
n adds the
tuple to the set P [ID], and outputs (propose,ID ,
v) to the adversary.
Decide: When TH cons
receives (decide; ID;i;v) from the ad-
versary, it verifies (by consulting P [ID] and -[ID ]) that
server i has proposed some value for ID
at least one server proposed v for ID
no other server has decided another value for ID
If all checks succeed, it sets -[ID] v, and outputs
(decide; ID; v) to the user at out i .
We will need a consensus protocol  that is not only secure,
but also guarantees to terminate for every server even if up to
servers crash. The following definition captures this more
formally.
Definition 5 We call a protocol  a tc -resilient consensus pro-
tocol, if Sys real;
n is as secure as Sys ideal;cons
n , and if for every
run of a configuration of Sys real;
n where at most tc servers
crash, the following holds: If all non-crashed servers propose
a value for some ID , then they all decide some value for ID ,
provided that the adversary delivers all messages among non-crashed
servers.
The best-known randomized asynchronous tc -resilient consensus
protocol can be derived from the protocol of Canetti
and Rabin [13], which actually solves the harder problem of
Byzantine agreement, where the servers may not only crash
but behave arbitrarily, and is unconditionally secure. A consensus
protocol can be derived from this as described in [4,
Section 14.3.2]. It uses an expected number of O(n 3 ) mes-
sages, proceeds in expected O(1) rounds, and has resilience
Assuming a trusted dealer that initializes the system
and working in a realistic model with a computationally
bounded adversary, there exist cryptographic protocols due to
Cachin et al. [10, 9] and to Nielsen [22], which use O(n 2 )
messages and O(1) rounds on average, and have optimal resilience
As mentioned in the introduction, it is also possible to implement
consensus in the failure-detector model [14], where
some very efficient protocols exist. A failure detector is a local
module available to every server that periodically outputs a list
of servers that it suspects to have crashed and is usually based
on a timing assumption. We do not pursue this further and
focus on the fully asynchronous model, but note that in certain
practical settings, such protocols might actually be more
efficient than the fully asynchronous protocols mentioned.
3. IMPLEMENTATION
3.1
We now describe our protocol ! for GKE. It builds on a
sub-system for consensus, and on a semantically secure encryption
scheme [17] (K; for elements of f0; 1g k with
key-generation algorithm K, encryption algorithm E , and decryption
algorithm D. In the following, all computations are
done over F 2 k if not indicated otherwise.
When a server i starts a session with tag ID , it first chooses
a contribution y i randomly from f0; 1g k ; the goal is to compute
the session key as
set G of n tc
servers. It then runs K to generate a pair of public key/private
to every other server.
When server i receives such a public key p j from another
server j, it sends the contribution value y i encrypted under
to server j. Once it has received the contribution values
servers like this, it computes the
differences d1 yu 1
proposes the sequences
and in the consensus sub-system,
where cs is an arbitrary constant string. Note that the difference
between any pair of contribution values may be leaked to
the adversary through this, but since no other information is
all contribution values remain secret.
When a server i decides two sequences hu
un t c i
and h
in the consensus instance IDjcs, it computes
the session key as follows. It first chooses an arbitrary
such that it has received y
um before
(notice that such an m exists, as it has received at least n tc
values y j at this point, and it holds that tc < n=2). It then
computes the session key
um .The detailed protocol is given in Algorithm 1. Here
and in the algorithm description, we make the convention that
d l
d l (n t c ) and u l  u l (n t c ) for n tc < l <
2(n
It is easy to see that every server terminates. It is also easy
to verify that every server computes the same session key
regardless of which m it chooses. Finally, since
upon initialization:
upon input (start; ID):
choose y i uniformly at random from f0; 1g k
send (enc to every server
upon receiving (enc
send (key part; ID; z ij ) to server j, where z ij Ep j (y i )
upon receiving (key part; ID; z ji ) from server j:
propose
upon deciding
IDjcs:
choose such that y
um
sk
um
output
Algorithm 1: Protocol ! for server i, implementing GKE
with crashes.
all contribution values remain secret (as argued above), the
same holds for the session key.
This technique is a fault-tolerant abstraction of the GKE
protocol of Burmester and Desmedt [8]. In their protocol the
public-key encryption scheme is instantiated with the ElGamal
scheme. The servers choose y i in the same way, and then
jointly compute the values g d
is a generator of a multiplicative group of prime
order q). The session key is then derived from these values
(and one contribution value y j ) as
We prove the following theorem in the next section.
Theorem 2 If  is a tc -resilient consensus protocol, then the
real system Sys real;!
n consisting of Sys real;!
n with sub-system
Sys real;
n is a tc -resilient group key exchange protocol.
Further Improvements. For repeatedly generating session
keys, there is a faster way than running protocol ! for every
session. The idea is to use a family of
pseudorandom functions [16], where a function i maps bit
strings used for the session tags ID to bit strings of length
k. Pseudorandom function families have the property that one
cannot distinguish i (ID) from a value randomly chosen from
knowing the index i. This allows the servers
to repeatedly generate session keys by running the protocol !
only once to get a secret index s. The session key for a session
with tag ID can then simply be computed as s(ID). We
remark that this construction is only secure in the weak corruption
model, where the adversary cannot break into a server
and learn the index s.
3.2 Security Analysis
To establish Theorem 2 and prove the security of Protocol
!, we have to show that for a tc -resilient consensus protocol
, Sys real;!
n is as secure as the ideal system Sys ideal;gke
and that Sys real;!
n is live, i.e., that if all servers U that do not
crash during a run of Sys real;!
start a session ID , then all
servers U finish session ID , provided that at most tc servers
crash and all messages among non-crashed servers are delivered

To show liveness of Sys real;!
n , we argue as follows. By the
assumption that at most tc servers crash, it follows that every
server in U receives n tc contribution values y j and proposes
some values for ID jcs. By the assumption that  is a
-resilient consensus protocol, every server therefore also decides
some sequences hu
for IDjcs. By construction, every server knows at that step
different values fy j g. By tc < n=2 it follows that for
every server there exists at least one index
that it knows the contribution value y
um . Hence, all servers in
U will be able to compute the key and finish the session ID .
To show security of Sys real;!
n , we consider the hybrid system
Sys hybrid;! cons
n consisting of the real system Sys real;!
n with
the ideal sub-system Sys ideal;cons
n for consensus. Note that it
suffices to show that Sys hybrid;! cons
n is as secure as Sys ideal;gke
since the security of Sys real;!
then follows by the composition
theorem and the assumption that  is a secure consensus
protocol.
We now show that Sys hybrid;! cons
n is as secure as Sys ideal;gke
using a constructive argument. In particular, we provide for
every user H, and every adversary A hybrid against the hybrid
system Sys hybrid;! cons
n the construction of an adversary A ideal
against the ideal system such that the views of H in a run of the
ideal and hybrid system configured with H, A ideal , and A hybrid ,
respectively, are computationally indistinguishable.
Recall that the view of H in a run of the hybrid system also
comprises messages that it exchanges with A hybrid . In order to
ensure that these messages have the same distribution as the
messages that H exchanges with A ideal in a run of the ideal
system, we construct A ideal using a technique called black-box
simulation. Specifically, we assume that we are given the hybrid
adversary A hybrid as a black-box, and then construct A ideal
out of a simulator SIM and the given black-box A hybrid . The
idea is that the simulator feeds the black box A hybrid with a
simulated view of a run of the hybrid system, where SIM must
compute this view based on the information it receives from
TH gke
. If the simulated view is indistinguishable from what
the hybrid adversary would see in a corresponding hybrid run,
we can use the outputs of the black-box A hybrid to simulate the
messages exchanged with H. The construction is illustrated in

Figure

(w.l.o.g. we only show how to build A ideal for a configuration
where H interacts with the ideal system through the
th
th
A ideal
A hybrid
th cons
th
cons
I
TH
cor_in cor_in
gke
cor_out
cor_out
net
in out in out
nn

Figure

2: The Construction of A ideal with Black Box Access
to A hybrid
The Simulator. As usual in black-box simulations, we construct
the simulator SIM as the combination of a simulated
user
H and a simulated hybrid system
Sys hybrid;! cons
n .
H interacts
with TH gke
n through to Adv th and from Adv th , and with
the simulated hybrid system
Sys hybrid;! cons
through its entire
interface.
Sys hybrid;! cons
interacts with A hybrid through connections
to Adv net ; from Adv net ; to Adv TH cons
; from Adv TH cons
and cor out j for
H provides the same inputs to
Sys hybrid;! cons
n as H provides to TH gke
and, moreover, schedules
TH gke
n such that whenever a server
cons
outputs a session
also outputs a session key for ID
at out i . More precisely,
H works as follows.
upon receiving (started; ID ; i) from TH gke
send (start; ID) to
cons
upon receiving (deliver; ID; k) from
cons
send (nish; ID; i) to TH gke
upon receiving (crash; i) from TH gke
send (crash) to
cons
Comparing the Views. To show that for every H and A hybrid ,
the view of H in a run of the hybrid system Sys hybrid;! cons
configured
with H and A hybrid is indistinguishable from the view
of H in a run of the ideal system Sys ideal;gke
configured with
the adversary A ideal , it suffices to show that the joint view of H
and A hybrid in a hybrid and an ideal run, respectively, are indistinguishable
(note that by construction of A ideal , this joint view
is well-defined in the ideal run).
We argue inductively over the steps of the runs. The base
case, i.e., indistinguishability of the initial states, follows by
construction. It remains to show that if the joint view of H and
A hybrid in a hybrid run up to a step l > 0 is indistinguishable
from their view in an ideal run up to step l (induction hypoth-
esis), then the same holds for step l (inductive step).
First note that the joint view of H and A hybrid only changes
if one of them either sends a message, or receives a message.
In the first case, the inductive step follows directly by the induction
hypothesis. In the second case, we argue as follows.
By the protocol specification, the messages received by H
and A hybrid for different sessions are statistically independent
of each other. Hence, it suffices to show that the probability
distributions of the received messages associated with a single
session in an ideal and a hybrid run, respectively, are indis-
tinguishable. We first investigate the distribution in an ideal
run. Let y denote the values
computed by
cons
during the run. Then, the values contained
in messages received by H and A hybrid up to and including
of the run are a subset of
un t c ig [
a subset of any linear combination
of the values y1 y2 ; y2 We
denote these values by the random variable V ideal
k . Notice that
we may ignore the index vectors proposed by
the servers, as they are determined by the scheduling of A hybrid ,
and thus, identically distributed in an ideal and a hybrid run.
The distribution of V ideal
k is as follows:
R
ideal

In a hybrid run, H and A hybrid receive the same messages,
but with a different distribution. In particular, the session key
is not drawn at random from f0; 1g k but is the sum of the
Specifically, the distribution V hybrid
k of the
received messages in a hybrid run is as follows:
R
y  u l

Let Uk denote the uniform distribution over f0; 1g k . To
show that V ideal
k , it is sufficient to show that from
ideal
k one can compute values
such that the following
holds:
y (i mod
y  un t c (2)
The values  y i can be computed as follows. For
let - i denote the value y i y (i mod n)+1 from V ideal
k , and let
un t c +1   u1 . Furthermore, for
the value y  u i y
Note that every such value  - i can be
computed as follows:
One can now compute
y  u 1 as (sk
The remaining values
can be computed
as follows:
y
It is easy to verify that the computed values
(2). Furthermore, (3) holds because y i for
are uniformly distributed over f0; 1g k . Finally, (4) holds by
the semantic security of the encryption scheme used.
3.3 Efficiency Analysis
We now analyze the expected message and round complexities
of our construction for generating a single session key. In
the first paragraph, we give the complexities for two concrete
instantiations of consensus protocols found in the literature. In
the second paragraph we show that our construction is almost
optimal in the sense that given an optimal consensus protocol,
our construction yields an almost optimal GKE protocol.
Concrete Efficiency. Let ! denote our GKE protocol ! with
sub-protocol  for consensus. Recall that R() and M()
denote the expected round and message complexities, respec-
tively, of a protocol  (cf. Section 2.1). It is easy to see that
M(). The best
known solution (in terms of round complexity) for GKE without
failures [8] proceeds in two rounds and uses 2n+n 2 mes-
sages; hence, the price we pay for tolerating crashes is essentially
a single consensus execution.
Below we give the asymptotic complexities of ! for some
known protocols  for consensus. Specifically, we consider
the consensus protocol  CR93 of Canetti and Rabin [13] and
the consensus protocol CKS00 of Cachin et al. [10], simplified
according to the remark in Section 2.3.
M(!) R(!) resilience dealer
Optimality of the Construction. We now investigate the optimality
of our protocol in terms of the round and message
complexities. In particular, let ! opt denote an optimal protocol
for GKE and let  opt denote an optimal protocol for consensus
optimal either in round complexity or in message
complexity, respectively, depending on the context. Let ! opt
denote our GKE protocol ! with sub-protocol  opt for con-
sensus. We want to know how close the efficiency of ! opt
is
to the efficiency of ! opt . We show that
R(! opt
M(! opt
We argue as follows. By construction of Protocol !, we have
R(! opt
Substituting this in (5) and (6) gives
Hence, it suffices to show that an optimal consensus protocol
opt uses at most 6 rounds and 6n 2 messages more on average
than an optimal solution ! opt for GKE. We show this by
a constructive argument. Specifically, we show how to build
from any given GKE protocol ! 0 a consensus protocol  ! 0 that
uses an average of 6 communication rounds and 6n 2 messages
more than a single execution of ! 0 . By the assumption that
opt is round-optimal, it follows that R( opt )
by the assumption that  opt is message-optimal,
it follows M( opt )
Because this holds for any GKE protocol ! 0 , it also holds for
opt , which implies (7) and (8).
We derive the protocol  ! 0 from the protocol  coin
pro-
posed by Cachin et al. [10], which is based on a protocol coin
for a common coin; such a common coin protocol provides
every server with a random bit that is unpredictable by the ad-
versary. The consensus protocol  coin
invokes coin twice on
average, proceeds in expected 6+2  R(coin ) rounds, and has
an expected message complexity of 6n
The main idea behind our protocol  ! 0 is to modify  coin
as follows. At the beginning, the servers execute GKE protocol
once to get a secret key sk . Then, they follow the
original protocol  coin
, except that instead of invoking coin
to get the i'th random bit c i , they use the i'th bit of sk (if more
than k random bits are used, the servers can also use sk as the
seed to a pseudorandom generator, and derive the random bits
It remains to show that if  coin
is a tc -resilient consensus
protocol, then the same holds for . The result will follow
from the composition theorem if we can show that the common
coins derived from ! 0 are unpredictable by the adversary
(as the same holds for the common coins derived from coin ).
But this follows directly from the definition of TH gke
n , which
guarantees that the adversary cannot predict a single bit of the
session key, even after seeing all other bits of the key.
4. THESTRONGCORRUPTIONMODEL
In this section, we investigate GKE in the presence of a
stronger adversary that may also break into the servers and
observe their internal state. We first formally describe such
attacks and the desired security requirements of GKE in this
model. We then prove an upper bound on the number of break-ins
that a GKE protocol can tolerate, and describe an implementation
of a protocol with optimal resilience.
4.1 Modeling Break-ins and Forward Secure
We model a break-in as a message (break in; s) sent on a
connection cor in i , where s represents an arbitrary bit string.
If in a real system Sys real;
n for a protocol , a server M
receives such a message, it computes a variable state  i and
sends (done; state
i ) on cor out i to A real . When this happens
we also say the adversary breaks into M  i . The variable
state
i comprises all internal data that has not explicitly been
erased, including the string s received with the break in mes-
sage. This ensures that if the protocol  is built on a sub-protocol
, then the adversary learns the internal state of M
and M
receives (by the system model) on cor in i every
message (break in; state
i outputs on cor out i ,
and hence, outputs the internal state of M
i to the adversary

The desired security requirement of a GKE protocol in this
model is called forward secrecy, and means that breaking into
a server reveals only the session keys being currently computed
by this server, but nothing about previously computed
session keys. Here, we define a threshold version of forward
secrecy, i.e., we require a GKE protocol to be forward-secure
only as long as the adversary does not break into more than
different servers. Formally, we capture this notion of security
in terms of an ideal system Sys ideal;fs gke
containing the
trusted host TH fs gke
b . This trusted host works exactly as TH gke
(cf., Definition 2), except for maintaining an additional set B
containing the indices of broken-into servers (initialized to ;),
and for the following additional transition rule:
Break-in: When the adversary breaks into a server i, TH fs gke
adds i to the set B, and chooses for every ID 2 S[i] the
[ID ] at random over f0; 1g k , if this key is not defined
yet. It then computes a set K of keys to be revealed
as follows:
Finally, it outputs (keys; K) to the adversary.
Note that the adversary is adaptive in the sense that she may
break into a server at any point during a run, and not only at
the beginning of the computation. The definition of a secure
GKE protocol in this model is as follows.
Definition 6 We call a protocol  a (tc ; t b )-resilient group key
exchange protocol, if Sys real;
n is as secure as Sys ideal;fs gke
and if for every run of a configuration of Sys real;
n where at
most tc servers crash, the following holds: If all non-crashed
servers start a session ID , then they all finish ID , provided
that the adversary delivers all messages among non-crashed
servers.
4.2 An Upper Bound on the Number of
Break-ins
Given a GKE protocol that tolerates tc servers that crash,
we now investigate for how many break-ins one can prove this
protocol as secure as TH fs gke
. For proving that a protocol
is as secure as an ideal service f, one has to show how to
construct for every user H and every adversary A real against
Sys real;
n an adversary A ideal against Sys ideal;f
n , such that H cannot
distinguish the corresponding ideal configuration from the
real one. The difficulty in constructing A ideal is to ensure that
it communicates with H in the same way as A real does. Cur-
rently, the only known way how this can be done is by constructing
A ideal using the technique of black-box simulation as
in Section 3.2.
We now argue that for tc > 0, no protocol
! can be proven
to be a (tc ; t b )-resilient GKE protocol using black-box simulation
In other words, we show that n 2tc is an
upper bound on the number of break-ins that one can tolerate
when building forward-secure GKE.
To see this, assume toward a contradiction that there exists a
)-resilient GKE protocol
for
We show how to build for a particular user H a real adversary
A real against
such that for any ideal adversary A ideal based on
black-box access to A real , the following holds: The joint view
of H and A real in a run of the real configuration is efficiently
distinguishable from the joint view of H and A real in a run of
the ideal configuration. This contradicts the initial assumption
that
is a (tc ; t b )-resilient GKE protocol.
We construct A real for a user that invokes a single session
ID as follows. The adversary A real runs
in two stages: In the
first stage, it chooses an arbitrary set M of n tc servers, and
runs the protocol in an arbitrary way, but ensuring that:
all messages sent among servers in M are delivered,
no message is delivered which is either sent by or sent
to a server not in M , and
no server is crashed or broken into.
When every server in M has finished the session ID , the first
stage ends. In the second stage, A real crashes tc arbitrary servers
in M and breaks into the remaining n 2tc servers of M . It
then continues to run the protocol in an arbitrary way, but ensuring
that no server is crashed or broken into, and that all
messages sent among non-crashed servers are delivered. Once
every non-crashed server has finished the session ID , the second
stage ends, and the adversary halts. Notice that by the
assumption that
is a (tc ; t b )-resilient GKE protocol, both
stages terminate, and moreover, every server that finishes session
ID outputs the same key.
Let sk denote this key, let state j denote the internal state
of a server M
j at the end of stage one, and let M denote the
set of all messages sent (but not yet delivered) to servers not
in M during the first stage. The fact that the servers in M do
not interact during the first stage with a server that is not in M
implies that the session key sk is efficiently computable from
M and the states fstate j g of all servers in M ; otherwise, a
server not in M could not compute sk and output the key at
the and of the second stage.
Suppose now we want to build an adversary A ideal , i.e., we
want to build a simulator that provides a black-box adversary
A real the (simulated) information seen in a real run of
, based on the information received by TH fs gke
. By definition
of TH fs gke
n;t b and A real , the simulator will not receive any
information on the session key sk 0 that the trusted host outputs
to the user. Hence, the information that the simulator
feeds to A real (comprising M and fstate j g) is statistically
independent of sk 0 , and therefore defines a key sk such that
. But in a real run, the key sk defined by
this information is always equal to the key sk 0 that the user re-
ceives. We conclude that the joint views of H and A real in a run
of an ideal and a real configuration, respectively, are efficiently
distinguishable.
4.3 An Implementation with Optimal Re-
silience
We now describe a (tc ; t b )-resilient GKE protocol ! fs derived
from !. We first explain why ! is not forward-secure
and then describe the necessary modifications to derive ! fs .
In protocol !, a server i continues to participate in the protocol
after outputting the session key sk . Specifically, it still
responds to arriving enc key messages by sending back its encrypted
contribution y i . This is necessary to ensure that every
non-crashed server eventually computes the session key. As a
result, an adversary that breaks into a server i after this server
has output sk has access to the server's contribution y i and
may compute the key sk . This contradicts forward secrecy,
which requires that the adversary must not learn any information
on sk when breaking into t b servers after they have output
the key sk .
To ensure forward secrecy, a server could simply erase all
local data after outputting the key. However, the resulting protocol
would not be live anymore, as the slowest servers might
never receive enough contributions from other servers to compute
the key. To ensure forward secrecy without compromising
liveness, we extend ! as follows. In addition to computing
the session key sk , every server i also computes a share s i of
sk such that any set of at most t b shares do not reveal any information
on sk , whereas any set of t b shares allows to
efficiently compute sk . Once a server has computed its share
and the session key, it outputs the key, and erases all local data
except for the share (this ensures forward secrecy). It then
continues to send its share to every server that requests it. This
ensures that every server eventually receives enough information
to compute the session key, and hence, ensures liveness.
To compute the shares of sk , we use polynomial secret sharing
as proposed by Shamir [25], where the shares s i of a secret
sk are computed by first choosing a random polynomial
f() of degree t b with computing every
share as s This technique requires that every server i
derives its share s i of the session key sk using the same polynomial
f(). This can be ensured by generating
in parallel, and then defining the polynomial
as
(the session key sk is
then defined as Generating
in parallel can be done by modifying protocol ! such that
a server i does not only choose a single contribution value
but a contribution vector y
and using this vector instead of y i throughout the protocol (op-
erations such as additions or encryptions are simply applied
component-wise). As a result, the servers compute the desired
in form of a vector sk 2 (f0; 1g k )
We could also have used a single session key sk in conjunction
with a pseudorandom function f i g i2f0;1g k to derive the
coefficients of the polynomial as sk m  sk (m) for m 2
this could not be proven secure against an adaptive
adversary.
For the same reason, one has to adjust ! such that a server i
sends the contribution y i to another server j in a non-committing
way [11]. This can be done as follows. When server j receives
server i's public key p i , it chooses a random vector r ij over
, encrypts it (component-wise) under p i to get
ij , and sends c ij to server i. Upon receiving c ij , server i derives
to server j. Upon receiving
this message, server j computes y
Modifying protocol ! as outlined above yields our desired
forward-secure protocol ! fs . It uses one execution of a consensus
protocol, and additionally, 3n 2 messages in 3 communication
rounds. A security proof for protocol ! fs can be derived
by modifying our proof for protocol ! accordingly.
5.



--R

"Secure group communication using robust contributory key agreement,"
"Exploring robustness in group key agreement,"
"New multiparty authentication services and key agreement protocols,"
Distributed Computing: Fundamentals
"Authenticated key exchange secure against dictionary attacks,"
"On key agreement and conference key agreement,"
"Provably authenticated group Diffie-Hellman key exchange,"
"A secure and efficient conference key distribution system,"
"Secure and efficient asynchronous broadcast protocols (extended abstract),"
"Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography,"
"Adaptively secure computation,"
"Universally composable security: A new paradigm for cryptographic protocols,"
"Fast asynchronous Byzantine agreement with optimal resilience,"
"Unreliable failure detectors for reliable distributed systems,"
"Group communication specifications: A comprehensive study,"
"How to construct random functions,"
"Probabilistic encryption,"
"The knowledge complexity of interactive proof-systems,"
"A conference key distribution system,"
"Authenticated multi-party key agreement,"
"Scalable protocols for authenticated group key exchange,"
"A threshold pseudorandom function construction and its applicatoins,"
"A model for asynchronous reactive systems and its application to secure message transmission,"
"A study of group rekeying,"
"How to share a secret,"
"Key agrement in dynamic peer groups,"
Secure Group Key Agreement.
"A practical and secure fault-tolerant conference key agreement protocol,"
--TR
How to construct random functions
The knowledge complexity of interactive proof systems
Fast asynchronous Byzantine agreement with optimal resilience
Adaptively secure multi-party computation
Random oracles in constantipole
Key Agreement in Dynamic Peer Groups
How to share a secret
Distributed computing
Provably authenticated group Diffie-Hellman key exchange
Group communication specifications
On Key Agreement and Conference Key Agreement
Secure and Efficient Asynchronous Broadcast Protocols
A Threshold Pseudorandom Function Construction and Its Applications
Authenticated Multi-Party Key Agreement
A Practical and Secure-Fault-Tolerant Conferenc-Key Agreement Protocol
A Study of Group Rekeying
Universally Composable Security
Exploring Robustness in Group Key Agreement
A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission
Secure Group Communication Using Robust Contributory Key Agreement

--CTR
Jonathan Katz , Ji Sun Shin, Modeling insider attacks on group key-exchange protocols, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA
Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Provably secure authenticated group Diffie-Hellman key exchange, ACM Transactions on Information and System Security (TISSEC), v.10 n.3, p.10-es, July 2007
provable security;universal composability;group key exchange;group communication