st1 := (PID, (Πi , piidi ), Yi , comi , deci , bi , ri ) (1)

i

and broadcasts

(Π; PID, (Π, piid), Yi , comi ). (2)

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

Round 2: Each instance (Πi , piidi ) receives messages (Πj ; PID, (Πj , piidj ), Yj ,

comj ) for j = i. Then it generates

sid := {(Πi , piidi )}i=1,...,n ,

cont = (PID, sid, Y1 , com1 , . . . , Yn , comn ),

creates a signature sigi on cont, and computes for ±, β, γ ∈ {0, 1}

ri

yi’1,±

xi,±,β = , zi,γ = e(yi+1,γ , v)ri . (3)

yi+1,β

We de¬ne Xi := (xi,0,0 , xi,0,1 , xi,1,0 , xi,1,1 ) and Zi := (zi,0 , zi,1 ). The internal

state is updated to

st2 := ((Πi , piidi ), cont, bi , Xi , Zi )

i

and broadcasts

(Πi ; (Πi , piidi ), PID, sid, sigi , bi , deci , Xi )

to all parties. Remark that the initial secret ri has been deleted and been ”re-

placed” by Xi and Zi . While this still allows to compute the key, this step makes

the straight-line simulatability feasible (see next section).

Key generation: Given an internal state st2 and messages

i

(Πj ; Πj , piidj , PID, sid, sigj , bj , decj , xj )

for j = i from the second round, (Πi , piidi ) generates the group key as follows.

First, it veri¬es that the following conditions hold for all j = 1, . . . , n:

1. sigj is valid signature of Πj on cont,

2. bj = TVer(comj , decj ),

3. the values yj,bj , xj,bj’1 ,bj+1 are elements in G,

4. e(xj,bj’1 ,bj+1 , g) = e(yj’1,bj’1 /yj+1,bj+1 , yj,bj ). Remark that this equation

holds only when the parties generated their second messages honestly. This

solves the problem 2 we mentioned in the previous sub-section.

In the positive case (and only then), it generates a group key by

n n

g rj,bj rj+1,bj+1 , v),

κ := (zi,bi+1 ) e( (xi+j,bi+j’1 ,bi+j+1 ) , v) = e(

n n+1’j

j=1 j=1

(4)

outputs (Πi , piidi , PID, sid, κ) and deletes the party instance, i.e., clears the inter-

nal state of the party instance (Πi , piidi ).

In the above protocol, messages whose length depend on the number n of participants,

e.g, PID and sid, can be shortened to constant size by taking their hash values or com-

monly agreed alias when possible.

In the next section, we will prove that our protocol UC-realizes Finit-gke . In Appendix

A, we will show that any protocol that UC-realizes Finit-gke needs at least two com-

munication rounds. Hence, our protocol has the minimum possible number of rounds.

Furthermore, this shows that the derived bound is tight.

A Universally Composable Group Key Exchange Protocol 401

4 Proof of Security

In this section, we prove that the 2-round GKE π proposed in Section 3 UC-realizes

Finit-gke . The proof of security relies on a new hardness assumption which we call the

linear oracle bilinear Dif¬e-Hellman (LO-BDH) assumption. Observe that the main

reason for introducing the new assumption is not to capture any new security properties

but to show that it is indeed possible to construct protocols which achieve the minimum

number of rounds and the according minimal number of messages. This assumption is

a combination of the decision bilinear Dif¬e-Hellman assumption and the linear Dif¬e-

Hellman assumption [7].

De¬nition 6. We say that the linear oracle bilinear decision Dif¬e-Hellman (LO-BDH)

˜

assumption holds for a bilinear pairing quadruple (G, G, e, g), if for every polynomial-

time adversary A and for every polynomial-size q, the advantage of A to win the fol-

lowing game is negligible.

Setup: Challenger C randomly chooses ±, β, γ, δ ∈ Z/pZ, and b ∈ {0, 1}. Then, C

generates χ = e(g, g)±βγ if b = 0, otherwise χ = e(g, g)δ . C also randomly

chooses μi ∈ Z/pZ and generates mi = g μi for i = 1, . . . , q.

Input At the beginning of the game, C gives A the tuple

(g, g1 , g2 , g3 , χ) = (g, g ± , g β , g γ , χ) and {mi }i=1,...,q

LDH Oracle query The game consists of q rounds. In each round, A can send a query

(i, bi ) for some i ∈ {1, . . . , q} (but for each i only once) and bi ∈ {0, 1}.

“ If bi = 0, C gives g ±(μi +β) to A.

“ If bi = 1, C gives μi to A.

Answer: At the end of the game, A outputs b ∈ {0, 1}. The advantage of A is |P r[b =

b ] ’ 1/2|.

In short, an adversary is required to solve the bilinear Dif¬e-Hellman problem while

it is helped by asking the LDH oracle either to solve a linear Dif¬e-Hellman problem

with respect to given random elements mi , g1 and g2 or to reveal logg mi . Although the

assumption that an adversary has an access to oracles might appear to be quite strong,

several assumptions have been proposed before that allow such queries, e.g., one-more-

discrete-log assumption [3], one-more-RSA-inversion assumption [2], LRSW assump-

tion in [14], etc. Furthermore, one can show that LO-BDH assumption assumption holds

in the generic bilinear group model (see the full version for a proof).

In [17], the notion of generalized UC (GUC) is proposed which overcomes a weak-

ness of the conventional UC framework. The major motivation for introducing GUC

was that UC does not provide deniability and adaptive soundness when a global setup

is assumed. A deniable protocol allows a party A to interact with party B in a way

that prevents B from later convincing party C that the interaction took place. Adaptive

sound arguments maintain the soundness even when party a A proves to a party B that

x is in some language L that is related to the global setup. Our scheme assumes the exis-

tence of a PKI and a trapdoor commitment scheme for which no one knows its trapdoor.

These are global setups that GUC concerns. However, neither deniability nor adaptive

soundness play a role in the security requirements for GKEs. We consider GKE to be

secure even if a party A can prove to others that A has exchanged a key. We do not

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

need to concern adaptive soundness since nothing related to globally setup parameter is

proved in our protocol. Therefore, we analyze our protocol within the conventional UC

framework and consider the GUC framework to be out of scope.

To prove the security of π within the UC framework, we have to describe for any

pair of environment Z and adversary A an ideal adversary S such that the real and

ideal executions are indistinguishable. Next, we give ¬rst a description of S. After that,

we sketch the proof which shows that the existence of a successful pair of environment

and adversary would contradict the LO-BDH assumption. Due to space limitations, the

full proof is can be found in the full version.

De¬nition 7. The ideal adversary S is assumed to have black box access to the ad-

versary A. Messages from Z to S (Z believes it is sending to A) are forwarded to A,

and messages from A to S (A believes it is sending to Z) are forwarded to Z. Addi-

tionally, S simulates the real parties. At the beginning, it generates public/private key

pairs (PK¦ , SK¦ ) for each party ¦ and gives the public keys to A. Furthermore, it

runs TGen to create pairs (tparam, tdr) and hands the public parameter tparam to A.

When S receives a message (PID, (¦, piid), new-session) from A for an uncorrupted

party ¦, it begins simulating for A a party instance with party instance ID piid being

run for ¦. More precisely, it executes on behalf of (¦, piid) the computations for the

¬rst round. Any messages sent by A to ¦ are processed by a party instance (¦, piid) for

suitable piid and any messages output by a party instance (¦, piid) are given to A.

In addition to the above, the ideal adversary S proceeds as follows:

SKG: (Session Key Generation) Assume that a simulated party instance (¦, piid) out-

puts a session key ((¦, piid), PID, sid, κ). If S has sent before (PID, sid , ok) to

Finit-gke for sid = sid and if there exists an uncorrupted party instance (¦ , piid ) ∈

sid © sid , then S aborts. If not, S checks whether any of the party instances

(¦ , piid ) ∈ sid have been corrupted.

SKG.¬cor.: If no party instance (¦ , piid ) ∈ sid has been corrupted, then:

SKG.¬cor.¬ok: If S has not yet sent (PID, sid, ok) to Finit-gke , then S checks

that it has received all pairs (¦, piid) ∈ sid from Finit-gke . If not, S aborts.

Otherwise, it sends (PID, sid, ok) to Finit-gke , followed by

(PID, sid, deliver, (¦, piid)).

SKG.¬cor.ok: If S has already sent the message (PID, sid, ok) to Finit-gke ,

this means that another party instance (¦ , piid ) has generated a session

key κ before. If κ = κ , S aborts. Otherwise, S sends

(PID, sid, deliver, (¦, piid)) to Finit-gke .

SKG.cor.: If some party instances C ⊆ sid \ {(¦, piid)} are corrupted, then:

SKG.cor.¬ok: If S has not yet sent (PID, sid, ok) to Finit-gke , it sends the mes-

sage (PID, (¦ , piid ), new-session) to Finit-gke on behalf of all corrupted

party instances (¦ , piid ) ∈ C who have not done so already. If S does

not receive (PID, (¦ , piid )) for all pairs (¦ , piid ) ∈ sid after execut-

ing the above, it aborts. Otherwise, it sends the messages (PID, sid, ok),

(PID, sid, key, κ), and (PID, sid, deliver, (¦, piid)) to Finit-gke .

SKG.cor.ok: If S has already sent (PID, sid, ok) to Finit-gke , then S has sent