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

A Universally Composable Group Key Exchange Protocol 403

COR: When A intends to corrupt a party instance (¦, piid), S provides A with the

current internal state as follows:

COR.¬ok: If S has not yet sent to Finit-gke the message (PID, sid, ok) for some

(PID, sid) with (¦, piid) ∈ sid, then S simply gives A the current internal

state of (¦, piid). Such a state is guaranteed to exist unless some message

(PID, sid, ok) has been sent followed by (PID, sid, deliver, ¦, piid). This state

for i = 1, 2, or the empty

can be either one of the two internal states sti ¦,piid

state, depending on the current round of the protocol execution sid.

COR.ok: Consider now the case that S has already sent (PID, sid, ok) to Finit-gke .

COR.ok.¬del: If S has not yet sent (PID, sid, deliver, (¦, piid))

(with (¦, piid) ∈ sid), then it checks if (¦, piid) does have a internal state

st2 , i.e., the second round is completed. If this is not the case, then

(¦,piid)

S aborts.

Otherwise, let the party instances be ordered as explained in the protocol

description in Section 3, that is sid = {(¦1 , piid1 ), . . . , (¦n , piidn )}, and

let (¦i , piidi ) denote the party instance that is corrupted by S to obtain a

key (PID, sid, κ) from Finit-gke . This might either be provided by S before

or be generated by Finit-gke . In the ¬rst case, S simply forwards the internal

state of (¦i , piidi ) to A. For the second case, we make use of the fact that as

S has already sent (PID, sid, ok). This implies that at least one simulated

copy (¦j , piidj ) ∈ sid has already distributed values (bj , Xj ) and has

received n ’ 1 tuples (b , X ) before. S uses these values and κ, which it

obtains by corrupting a party instance via Finit-gke , to replace the value of

zi,bi+1 in the internal state of (¦i , piidi ) to

⎛ ⎞1/n

n

zi,bi+1 := ⎝κ/e( , v)⎠

n+1’j

((xi+j,bi+j’1 ,bi+j+1 ) ,

j=1

sets zi,1’bi+1 := zi,1’bi+1 , and hands to A the internal state

(PID, sid, (¦i , piidi ), conti , deci , bi , Xi , Zi ).

COR.ok.del: If S has already sent (PID, sid, deliver, ¦, piid) to Finit-gke , then

S returns nothing (i.e., an empty internal state) to A.

Theorem 1. The GKE π UC-realizes Finit-gke under the LO-BDH assumption when the

number n of participants is even.

Proof

(Sketch) We sketch only the proof ideas here. A detailed proof can be found in the full

version. The description of S contains several cases in which S aborts. Using a hybrid

argument, one can prove that these abortions never occur unless the used signature

scheme or commitment scheme are broken.

With respect to the straight-line simulatability, an ideal adversary can easily simu-

late the internal state of the (simulated) party instances in the case of corruption if no

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

party instance has output a key. However, if the adversary A requests the corruption

of a party instance when some other party instances have output keys before, the ideal

adversary S is forced to present an internal state to A for the corrupted party instance

that ¬ts to the key that has been randomly chosen by the ideal functionality Finit-gke .

The simulator description tells how this can be achieved and in the full proof, we show

that this reconstructed internal state cannot be distinguished from a honestly generated

state if the LO-BDH assumption holds.

Finally, we prove that if real and ideal executions are distinguishable, then the LO-

BDH assumption is violated. For this purpose, we embed a corresponding problem into

the executions. For this embedding, we make use of the fact that although the number

of possible sets sid is superpolynomial in the number of invoked party instances, the

number of sets sid that actually appear during the execution is only polynomial in the

security parameter. For this purpose, we make use of the trapdoor in the commitment

scheme.

5 Conclusions and Open Questions

In this paper, we followed the path initiated by Katz and Shin in [35] and presented a

group key exchange protocol that is secure within the universal composability frame-

work. However, while Katz and Shin demonstrated merely the general feasibility of

constructing UC-secure GKEs, we aimed for improved solutions. Our protocol requires

only two communication rounds (which we show to be minimal) and includes ses-

sion identi¬er generation (which is a prerequisite within the UC-framework but is only

rarely provided in practice). In the protocol, every party send to every other party in

each round one message, which yields a total number of 2n(n ’ 1) messages. We show

that the number of messages cannot be further reduced in two-round protocols.

Although our protocol improves over existing results, there is still room for further

improvements or extensions. An important question is if a two-round UC-realization

of Finit-gke exists where the security can be reduced to a more standard assumption.

Furthermore, we imagine that the basic idea on how to integrate protocol initialization

into the protocol (using a trapdoor commitment scheme) might be transferred to other

types of protocols as well.

References

1. Barak, B., Lindell, Y., Rabin, T.: Protocol initialization for the framework of universal com-

posability. Cryptology ePrint Archive, Report2004/006 (2004),

http://eprint.iacr.org/

2. Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-rsa-inversion

problems and the security of chaum™s blind signature scheme. J. Cryptology 16(3), 185“215

(2003)

3. Bellare, M., Palacio, A.: Gq and schnorr identi¬cation schemes: Proofs of security against

impersonation under active and concurrent attacks. In: Yung, M. (ed.) CRYPTO 2002.

LNCS, vol. 2442, pp. 162“177. Springer, Heidelberg (2002)

4. Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dic-

tionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139“155.

Springer, Heidelberg (2000)

A Universally Composable Group Key Exchange Protocol 405

5. Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.)

CRYPTO 1993. LNCS, vol. 773, pp. 232“249. Springer, Heidelberg (1994)

6. Bellare, M., Rogaway, P.: Provably secure session key distribution: the three party case. In:

STOC, pp. 57“66. ACM, New York (1995)

7. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin [13], pp. 41“55

8. Bresson, E., Chevassut, O., Pointcheval, D.: Provably authenticated group dif¬e-hellman

key exchange - the dynamic case. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248,

pp. 290“309. Springer, Heidelberg (2001)

9. Bresson, E., Chevassut, O., Pointcheval, D.: Dynamic group dif¬e-hellman key exchange

under standard assumptions. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332,

pp. 321“336. Springer, Heidelberg (2002)

10. Bresson, E., Chevassut, O., Pointcheval, D., Quisquater, J.-J.: Provably authenticated group

dif¬e-hellman key exchange. In: CCS 2001: Proceedings of the 8th ACM conference on

Computer and Communications Security, pp. 255“264. ACM Press, New York (2001)

11. Bresson, E., Manulis, M., Schwenk, J.: On Security Models and Compilers for Group

Key Exchange Protocols. In: Miyaji, A., Kikuchi, H., Rannenberg, K. (eds.) IWSEC 2007.

LNCS, vol. 4752, pp. 292“307. Springer, Heidelberg (2007)

12. Burmester, M., Desmedt, Y.: A secure and ef¬cient conference key distribution system (ex-

tended abstract). In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 275“286.

Springer, Heidelberg (1995)

13. Cachin, C., Strobl, R.: Asynchronous Group Key Exchange with Failures. In: Proceed-

ings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC

2004), pp. 357“366. ACM Press, New York (2004)

14. Camenisch, J., Lysyanskaya, A.: Signature schemes and anonymous credentials from bilin-

ear maps. In: Franklin [31], pp. 56“72

15. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols.

Cryptology ePrint Archive, Report 2000/067 (revised in 2005) (2000),

http://eprint.iacr.org/

16. Canetti, R.: Universally composable signature, certi¬cation, and authentication. In: CSFW,

p. 219. IEEE Computer Society, Los Alamitos (2004)

17. Canetti, R., Dodis, Y., Pass, R., Wal¬sh, S.: Universally composable security with global

setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61“85. Springer, Heidelberg

(2007)

18. Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.)

CRYPTO 2001. LNCS, vol. 2139, pp. 19“40. Springer, Heidelberg (2001)

19. Canetti, R., Halevi, S., Katz, J., Lindell, Y., MacKenzie, P.D.: Universally composable

password-based key exchange. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494,

pp. 404“421. Springer, Heidelberg (2005)

20. Canetti, R., Krawczyk, H.: Analysis of key-exchange protocols and their use for building

secure channels. In: P¬tzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453“

474. Springer, Heidelberg (2001)

21. Canetti, R., Krawczyk, H.: Universally composable notions of key exchange and secure

channels. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 337“351.

Springer, Heidelberg (2002)

22. Canetti, R., Kushilevitz, E., Lindell, Y.: On the limitations of universally composable two-

party computation without set-up assumptions. J. Cryptology 19(2), 135“167 (2006)