adversary who learned the internal state (by corruption), can compute the key by himself while

the corrupted party is unable to do so as it is still waiting for the ¬nal messages. On the other

hand, if the corrupted party instance did already ¬nish the key generation, the key is handed in

the real world to the invoking party and the internal state is deleted. Hence, the adversary does

learn nothing then.

A Universally Composable Group Key Exchange Protocol 397

protocol that UC-realizes the GKE functionality from [35] UC-realizes its multiple ses-

sion extension as well. In Finit-gke , whenever a party-instance (¦, piid) is invoked, the

session in which it will participate is not determined. Furthermore, each party may be

invoked several times and the attacker has the full control over forming and scheduling

sessions. Hence, our ideal functionality is intrinsically multi-session without the need

for additional mechanisms.

Observe that for the case of a single execution with a ¬xed (possibly externally given)

sid, Finit-gke behaves exactly like FGKE from [35]. Hence, any combination of the

initialization protocol from [1] and a protocol constructed with the Katz-Shin-compiler

UC-realizes Finit-gke . In the next Section, we start from such a construction and explain

how the number of rounds can be reduced.

3 The Protocol

3.1 Problems and Our Approach

Before we describe our protocol in the next (sub-)section, we ¬rst sketch our approach

and which challenges need to be overcome. In principle, we follow the ideas from the

Katz-Shin compiler [35] and the initialization protocol from Barak et al. [1]. To ex-

plain these, let π be a GKE that UC-realizes Finit-gke and that has been compiled by

ˆ

applying the Katz-Shin compiler to an AKE-secure GKE and by prepending the ini-

tialization protocol from Barak et. al. For example, if one applies these modi¬cations

to the Burmester-Desmedt protocol [12] (in its AKE-secure variant given in [36]), one

ˆ

obtains a 5-round GKE π . Our approach for reducing the number of rounds are the two

following independent methods:

ˆ

1. In the ¬rst two rounds of π , that is the initialization protocol, each party sends a

value piid to an initializer. When he received values from each party, he distributes

their concatenation within the group. 3 We integrate this procedure into the third

round by letting each party sends its piid directly to the others and by taking care

that these values are inseparable from the remainder of the protocol.

ˆ

2. In the last round of π , each party broadcasts an acknowledgment. This has two pur-

poses. Firstly, each party can check that all parties obtained the same key. Secondly,

it allows straight-line simulatability for the case that one party has already output a

group key when another party gets corrupted. We use a non-interactive proof in the

penultimate round instead.

As these modi¬cations render the ¬rst, second, and last round obsolete, the number of

rounds can be reduced by three. Although the approaches might sound quite straight-

forward, the problems lie (as often) in the security proof.

1. For a proof of security, one has to show that a successful attacker can be used to

solve a presumably hard problem. In the case of GKEs, this usually means that a

given instance of the problem, for which a solution is sought, is embedded in the

3

Using randomly generated nonces of the length of the security parameter is one way for choos-

ing unique piids.

398 J. Furukawa, F. Armknecht, and K. Kurosawa

messages of the participating parties. But in the case considered here, it is unknown

at the beginning which set of parties will eventually participate into a protocol run.

Indeed, the number of possible sets of parties (or groups) which might execute a

protocol run increases exponentially as the number of parties increases. Thus, new

and more sophisticated methods are necessary to embed the problem instance such

that the reduction can be shown.

2. While several ef¬cient non-interactive proofs within the random oracle model exist,

we aim (to follow the path toward more practicability) for a proof without random

oracles.

3. A dedicated simulator which achieves straight-line simulatability is required as the

general simulator given by Katz and Shin does not hold anymore.

The idea to solve the ¬rst problem deploys a commitment scheme. At the beginning

of the protocol execution, each party generates two possible messages m and m for the

¬rst round, together with corresponding internal states s and s . From these, it chooses

one internal state, say s, and deletes the other. Then, both messages (m and m ) are

send in the ¬rst round together with a commitment to which message is going to be

used later (in this example, m). The commitment is assumed to be a perfectly hiding

trapdoor bit commitment and its trapdoor is kept secret to everyone. But in the security

proof, the ideal adversary S, who chooses the parameters, knows the trapdoor of the

commitment scheme and can decommit in such a way that it is appropriate for him.

For the second problem, we make use of pairings on elliptic curves. More precisely,

we extend the Burmester-Desmedt protocol over bilinear groups where the validity of

messages can be checked by using pairings.

The idea to solve the third problem is to update the internal state in such a way that

the key can still be generated but that the initially chosen secret is deleted. This allows

to simulate the internal state of the corrupted party instance such that it is in compliance

with the revealed group key.

3.2 Protocol Description

In the following, we describe a 2-round GKE π which UC-realizes Finit-gke . Although

we prove in Section 4 the security of the protocol is only for the case of an even number

of parties, the protocol can easily be extended for an odd number of parties if one or

every party plays the role of two parties. The protocol is an extension of the Burmester-

Desmedt protocol [12] which additionally uses a bilinear pairing, a perfect hiding trap-

door bit commitment scheme, and a digital signature scheme as further building blocks.

We assume that the parties can completely erase their state. This ability is indispens-

able to ensure forward secrecy, that is corrupting parties does not compromise keys

from earlier sessions.

˜

De¬nition 3. Let G and G denote two cyclic groups of prime order p. A bilinear pairing

˜

is an ef¬cient mapping e : G — G ’ G such that e(u± , v β ) = e(u, v)±β for all u, v ∈ G

˜

and ±, β ∈ Z/pZ and there exists g ∈ G such that e(g, g) generates G. We will refer to

˜

such a tuple (G, G, e, g) as a bilinear pairing quadruple.

A Universally Composable Group Key Exchange Protocol 399

De¬nition 4. A trapdoor bit commitment scheme is a tuple of algorithms TGen,

TCom, TVer, and TOpen. Given a value 1k , TGen outputs a public parameter tparam

and the corresponding trapdoor tdr. Given tparam, b ∈ {0, 1}, and a random tape,

Tcom outputs com and dec. Given tparam, com, and dec, TVer outputs b ∈ {0, 1}

or ⊥. Given tparam, com, dec, tdr, b ∈ {0, 1}, TOpen outputs dec such that b =

TVer(tparam, com, dec ).

Roughly, a trapdoor bit commitment scheme is hiding/perfect-hiding if distributions

of commitments of 0 and 1 are indistinguishable/identical. A trapdoor bit commit-

ment scheme is binding, if given a randomly generated parameter tparam, to out-

put com, dec, dec such that 0 = TVer(tparam, com, dec) and 1 = TVer(tparam,

com, dec ) is hard. A trapdoor bit commitment scheme is equivocal if for any (com,

dec) = Tcom(tparam, b, r) with b ∈ {0, 1}, the distributions of (com, dec =

TOpen(tparam, com, dec, tdr, b )), b ∈ {0, 1}, and (com, dec) = Tcom(tparam,

b , r ) are indistinguishable. Here, r and r are random tapes. See [25,30] for more

details and possible schemes. The trapdoor bit commitment we use here is perfectly

hiding, binding, and equivocal.

De¬nition 5. (GKE protocol π) Let n denote the size of PID. If we need to distinguish

between the sizes of different sets PID, we write nPID instead. We index each party

in PID by i ∈ {1, . . . , n} in some order and let Πi denote the i-th party. For ≥ n,

we de¬ne Π := Π( mod n) . Let b denote 1 ’ b for b ∈ {0, 1}. Each party Πi has

its public/private key pair (PKi , SKi ) which can be used to sign messages. We assume

the deployed digital signature scheme to be existentially unforgeable against chosen

message attacks. The public keys are known to all parties. The system parameters are a

bilinear pairing quadruple, a randomly chosen element v ∈ G, and parameters tparam

for a perfect hiding trapdoor commitment scheme. The trapdoor tdr that corresponds

to tparam is kept secret to everyone. The protocol is divided into two communication

rounds where each party can send one message to each party per round, and a key

generation step at the end. The protocol works as follows:

Round 1: When Πi receives a message (PID, (Π, piid), new-session), it generates a

new party instance (Πi , piidi ), randomly chooses bi ∈ {0, 1}, and generates

yi,bi := g ri with ri ∈R Z/pZ

ybi ∈R G, and

(comi , deci ) := TCom(tparam, bi ).

We abbreviate Yi := (yi,0 , yi,1 ). Remark that yi,0 and yi,1 play the role of the

two messages we mentioned in the solution approach for problem 1 in the previous