Michel Abdalla

Céline Chevalier

Mark Manulis

David Pointcheval

Flexible Group Key Exchange with On-Demand Computation of Subgroup Keys

Modern multi-user communication systems, including popular instant messaging tools, social network platforms, and cooperative-work applications, offer flexible forms of communication and exchange of data. At any time point concurrent communication sessions involving different subsets of users can be invoked. The traditional tool for achieving security in a multi-party communication environment are group key exchange (GKE) protocols that provide participants with a secure group key for their subsequent communication. Yet, in communication scenarios where various user subsets may be involved in different sessions the deployment of classical GKE protocols has clear performance and scalability limitations as each new session should be preceded by a separate execution of the protocol. The motivation of this work is to study the possibility of designing more flexible GKE protocols allowing not only the computation of a group key for some initial set of users but also efficient derivation of independent secret keys for all potential subsets. In particular we improve and generalize the recently introduced GKE protocols enabling on-demand derivation of peer-to-peer keys (so called GKE+P protocols). We show how a group of users can agree on a secret group key while obtaining some additional information that they can use on-demand to efficiently compute independent secret keys for any possible subgroup. Our security analysis relies on the Gap Diffie-Hellman assumption and uses random oracles.

Introduction

Despite more than 20 years of research (see surveys in [START_REF] Boyd | Protocols for Authentication and Key Establishment[END_REF][START_REF] Manulis | Security-Focused Survey on Group Key Exchange Protocols[END_REF]), group key exchange (GKE) protocols are still far from being widely used in practice, especially if one compares to two-party key (2KE) exchange protocols which found their deployment in various standards and daily applications. Among the main reasons for this limited spectrum of applications is the fact that GKE protocols are rather complex, costly to implement, and not versatile enough. Modern communication platforms, including diverse instant-messaging tools and collaborative applications, allow their users to communicate and exchange data within almost any subset of participants. Had classical GKE protocols been deployed in this multi-user environment, then every new communication attempt would require a different execution of the GKE protocol. This constraint is anchored in the design rationale behind existing GKE protocols. A possible improvement would be to design more flexible GKE protocols, which would not only provide their participants with the group key but would also leave space for the efficient computation of secret keys for use within any subset of the original group.

Recently, Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] suggested flexible GKE protocols allowing for a secure combination of two communication forms: secure communication within a group and secure communication amongst any two parties from the group. In particular, he designed GKE protocols enabling on-demand derivation of peer-to-peer (p2p) keys, denoted GKE+P, which provide any pair of participants with an independent secure p2p key in addition to the common group key. The main ingredient of GKE+P constructions in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] is the parallel execution of the classical Diffie-Hellman key exchange (PDHKE) protocol [START_REF] Diffie | New Directions in Cryptography IEEE Tran[END_REF] and, in particular, the user's ability to re-use the same value g x in the computation of group and p2p keys, where g is a generator and x is the private user's exponent.

Building on this, we investigate the even more generalized and flexible approach -the extension of GKE protocols with the ability to compute an independent session key for any possible subgroup of the initial GKE participants. Similar to [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF], we are interested in solutions which would allow the derivation of the subgroup keys in a more efficient way than simply running an independent session of a GKE protocol for each subgroup. GKE protocols enriched in this way, which we denote GKE+S, would allow the combination of different forms of secure communication. For example, a single file deposited in a file sharing network or broadcasted to the group may contain documents encrypted for the whole group and different attachments encrypted for different subgroups.

The required independence between different key types imposes further security challenges on GKE+S protocols: The classical GKE security requirement concerning the secrecy of the group key with respect to the external parties (typically called AKE-security [START_REF] Bresson | Provably Authenticated Group Diffie-Hellman Key Exchange[END_REF][START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF]) should now be preserved even if some subgroup keys leak, and the independence of any subgroup key implicitly requires us to handle (collusion) attacks from parties that are external to that subgroup but internal to the preliminary computation process of the common group key or to a different subgroup with membership overlap. As a result, the specification of the adequate security requirements for GKE+S protocols with respect to these threats appears to be an interesting task from a formal point of view.

The protocols being considered in this paper are all based on the well-studied Burmester-Desmedt (BD) group key exchange protocol [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF]. Interestingly, Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] had shown that, if users try to use the same exponents in the computation of group and p2p keys in the original BD protocol, then the AKE-security of p2p keys could no longer be guaranteed. In this work, we illustrate how a small modification of the original BD protocol suffices to obtain a secure GKE+P protocol. Interestingly, this modification of the original BD protocol only applies to the computation steps and leaves the communication complexity unchanged. In particular, our GKE+P protocol has better overall complexity than those proposed in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF]. After presenting our new GKE+P protocol, we show how to extend it into a secure GKE+S protocol. Our GKE+S protocol requires only one additional communication round for setting up any subgroup key as opposed to the two-round communication that one would need to compute a subgroup key via an independent protocol execution.

Related Work

Security of key exchange protocols is usually defined with the requirement of Authenticated Key Exchange (AKE) security; see [START_REF] Bellare | Entity Authentication and Key Distribution[END_REF][START_REF] Canetti | Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels[END_REF][START_REF] Choo | Examining Indistinguishability-Based Proof Models for Key Establishment Protocols[END_REF][START_REF] Lamacchia | Stronger Security of Authenticated Key Exchange[END_REF] for the 2KE case and [START_REF] Bresson | Provably Authenticated Group Diffie-Hellman Key Exchange[END_REF][START_REF] Bresson | Contributory Group Key Exchange in the Presence of Malicious Participants[END_REF][START_REF] Gorantla | Nieto Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols[END_REF][START_REF] Katz | Modeling Insider Attacks on Group Key-Exchange Protocols[END_REF][START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF] for the GKE case. AKE-security models the indistinguishability of the established session group key with respect to an active adversary treated as an external entity from the perspective of the attacked session. The signature-based compilation technique by Katz and Yung [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF] (see also the work by Bresson, Manulis, and Schwenk [START_REF] Bresson | On Security Models and Compilers for Group Key Exchange Protocols[END_REF]) can be used to achieve AKE-security for GKE protocols that already provide such indistinguishability but with regard to the passive attacks only. Besides AKE-security some security models for GKE protocols (e.g. [START_REF] Bresson | Contributory Group Key Exchange in the Presence of Malicious Participants[END_REF][START_REF] Bresson | Securing Group Key Exchange against Strong Corruptions[END_REF][START_REF] Gorantla | Nieto Modeling Key Compromise Impersonation Attacks on Group Key Exchange Protocols[END_REF][START_REF] Katz | Modeling Insider Attacks on Group Key-Exchange Protocols[END_REF]) define optional security against insider attacks.

The notion of GKE+P protocols has been put forth by Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF]. He showed how to compile the so-called family of Group Diffie-Hellman protocols, i.e. protocols such as [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF][START_REF] Desmedt | Revisiting Pairing Based Group Key Exchange[END_REF][START_REF] Ingemarsson | A Conference Key Distribution System[END_REF][START_REF] Kim | Group Key Agreement Efficient in Communication[END_REF][START_REF] Kim | Tree-Based Group Key Agreement[END_REF][START_REF] Nam | Constant-Round Authenticated Group Key Exchange with Logarithmic Computation Complexity[END_REF][START_REF] Steer | A Secure Audio Teleconference System[END_REF][START_REF] Steiner | Diffie-Hellman Key Distribution Extended to Group Communication[END_REF] which extend the classical Diffie-Hellman method to the group setting, in such a way, that at the end of the protocol any pair of users can derive their own p2p key on-demand and without subsequent communication. The main building block of his GKE+P compiler is the parallel Diffie-Hellman key exchange (PDHKE) in which each user broadcasts a value of the form g x and uses x for the derivation of different p2p keys. For the two efficient two-round unauthenticated GKE protocols by Burmester and Desmedt (BD) [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF] and by Kim, Perrig, and Tsudik (KPT) [START_REF] Kim | Group Key Agreement Efficient in Communication[END_REF], in which users need to broadcast g x anyway, Manulis analyzed optimizations based on the re-use of the exponent x for the computation of both group and p2p keys showing that KPT remains secure whereas BD not.

We also notice that PDHKE has been used by Jeong and Lee [START_REF] Jeong | Parallel Key Exchange[END_REF] for the simultaneous computation of multiple two-party keys amongst a set of users, yet without considering collusion attacks against the secrecy of keys computed by non-colluding users and without considering group keys. In another work, Biswas [START_REF] Biswas | Diffie-Hellman Technique: Extended to Multiple Two-Party Keys and One Multi-Party Key[END_REF] proposed a slight modification to the original Diffie-Hellman protocol allowing its participants to obtain up to 15 different shared two-party keys.

While GKE+P protocols take the top-down approach in the sense that the computation of p2p keys for any pair of users is seen as a feature of the GKE protocol there have been several suggestions, e.g. [START_REF] Abdalla | Password) Authenticated Key Establishment: From 2-Party to Group[END_REF][START_REF] Mayer | Secure Protocol Transformation via "Expansion": From Two-Party to Groups[END_REF][START_REF] Wu | Constant-Round Password-Based Authenticated Key Exchange Protocol for Dynamic Groups[END_REF], that construct GKE protocols from 2KE protocols used as a building block. For example, Abdalla et al. [START_REF] Abdalla | Password) Authenticated Key Establishment: From 2-Party to Group[END_REF], as well as Wu and Zhu [START_REF] Wu | Constant-Round Password-Based Authenticated Key Exchange Protocol for Dynamic Groups[END_REF] order protocol participants into a cycle (in a BD fashion) and a 2KE protocol is executed only between the neighbors. However, these constructions do not explicitly meet the requirements of GKE+P protocols as an independent p2p key may not be available for every pair of users.

Contributions and Organization

In Section 2, we recall the classical Burmester-Desmedt (BD) protocol [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF] and explain problems behind the re-use of its exponents for PDHKE following the analysis by Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF]. In Section 3, we propose a slight modification to the computations steps of the BD protocol such that the overall communication complexity remains unchanged, yet secure, non-interactive derivation of p2p keys through the re-use of users' exponents becomes possible. Our GKE+P protocol obtained in this way and denoted mBD+P is more efficient than other solutions proposed in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF].

We then continue in Section 4 with our second contribution -the description of a GKE+S protocol in which users compute the common group key first and then any subgroup of these users can agree on an independent subgroup key. Our GKE+S protocol, denoted mBD+S, requires two-rounds for the computation of the group key and only one round for the subsequent on-demand computation of any subgroup key. In comparison to the naive approach of computing a subgroup key through an independent execution of the full GKE protocol our solution is more scalable as it halves the number of communication rounds and required messages.

In Section 5, we formally model the security of GKE+S protocols. We address AKE-security of both group and subgroup keys whereby security of the latter is modeled under consideration of possible collusion attacks representing the main challenge is such protocols. Our model generalizes the security model by Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF], which considered only derivation of p2p keys.

Finally, we apply the model in Section 6 to prove that mBD+P provides AKEsecurity for group and p2p keys and that mBD+S additionally provides AKE-security for the derived subgroup keys. We conclude our work in Section 7 by comparing the communication and computation complexity of our protocols with the previous solutions showing the expected efficiency gain.

Preliminaries and Background

Notations and Assumptions

Throughout the paper, unless otherwise specified, by G := g we denote a cyclic group of prime order Q generated by g. By H g , H p , H s : {0, 1} * → {0, 1} κ we denote three cryptographic hash functions, which will be used to derive group, p2p, and subgroup keys, respectively, and by H : G → {0, 1} κ an auxiliary hash function which will be used to slightly modify the computations of the original Burmester-Desmedt protocol. The symbol "|" will be used for the concatenation of bit-strings. Since we are interested in authenticated protocols we will further use a digital signature scheme Σ = (KeyGen, Sign, Verify), which we assume to be existentially unforgeable under chosen message attacks (EUF-CMA). Additionally, we recall the following well-known cryptographic assumption (see e.g. [START_REF] Boldyreva | Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme[END_REF]): Definition 1. Let G := g as above and a, b, c ∈ R Z Q . The Gap Diffie-Hellman (GDH) problem in G is hard if the following success probability is negligible:

Succ GDH G (κ) := max A ′ Pr a,b A ′D(•) (g, g a , g b ) = g ab ,
where D(•) denotes the Decision Diffie-Hellman (DDH) oracle, i.e. D(g, g a , g b , g c ) outputs 1 if c = ab and 0 otherwise. Note that Succ GDH G (κ) is computed over all PPT adversaries A ′ running within time κ. In other words, the Computation Diffie-Hellman (CDH) problem in G is assumed to be hard even if the DDH problem in G is easy.

Burmester-Desmedt Group Key Exchange

The Burmester-Desmedt (BD) protocol from [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF] is one of the best known unauthenticated GKE protocols. Its technique has influenced many GKE protocols, including [START_REF] Abdalla | Password-Based Group Key Exchange in a Constant Number of Rounds[END_REF][START_REF] Kim | Constant-Round Authenticated Group Key Exchange for Dynamic Groups[END_REF]. The BD protocol arranges participants U 1 , . . . , U n into a cycle, and requires two communication rounds: Round 1. Each U i broadcasts y i := g x i for some random x i ∈ R Z Q . Round 2. Each U i broadcasts z i := (y i+1 /y i-1 ) x i (the indices i form a cycle, i.e. 0 = n and n + 1 = 1). Group Key Computation. Each U i computes the secret group element

k ′ i := (y i-1 ) nx i • z n-1 i • z n-2 i+1 • • • z i+n-2 = g x 1 x 2 +x 2 x 3 +...+xnx 1 ,
which is then used to derive the group key.

As shown by Katz and Yung [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF] the group element k ′ i remains indistinguishable from a randomly chosen element in G under the DDH assumption with regard to a passive adversary; using the general authentication technique from [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF] this indistinguishability can be extended to resist active attacks.

Parallel Diffie-Hellman Key Exchange

The following one-round parallelized Diffie-Hellman protocol (PDHKE) with the additional key derivation step based on a hash function H p (modeled as a random oracle) has been deployed by Manulis [27] for the computation of independent p2p keys between any two users U i and U j : Round 1. Each U i chooses a random x i ∈ R Z Q and broadcasts y i := g x i . P2P Key Computation. Each U i proceeds as follows:

-for the input identity U j compute k ′ i,j := y x i j = g x i x j , -derive k i,j := H p (k ′ i,j , U i |y i , U j |y j ). (W.l.o.g. we assume that both users U i and U j use the same order for the inputs to H p .)

As motivated in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] the input (U i |y i , U j |y j ) to H p in addition to k ′ i,j = g x i x j is necessary in order to ensure the independence of p2p keys in the presence of collusion attacks. This independence follows from the uniqueness of user identities and the negligible probability that an honest user U i chooses the same exponent x i in two different sessions. It has been shown in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] that PDHKE provides security of p2p keys in the presence of passive attacks and that the authentication technique from [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF] is also sufficient to preserve this property in the presence of active attacks.

Insecure Merge of BD and PDHKE

Given BD and PDHKE one of the questions investigated by Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] was whether a user U i can safely re-use own exponent x i for the computation of the group key and any p2p key. In other words whether a two-round merged version of original BD and PDHKE would result in a secure GKE+P protocol in which the keys are computed as follows: the group key k i := H g (k ′ i , U 1 |y 1 , . . . , U n |y n ) and any p2p key k i,j := H s (k ′ i,j , U i |y i , U j |y j ). The analysis given in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] shows that this merge is insecure. More precisely, for any group size n ≥ 3 an attack (possibly by colluding participants) was presented that would break the AKE-security of any p2p key k i,j .

In the next section we revise this result. We show how to slightly modify the computation of z i in the original BD protocol in order to allow secure computation of

k i := H g (k ′ i , U 1 |y 1 , . . . , U n |y n ) and k i,j := H s (k ′ i,j , U i |y i , U j |y j ).
We stress that our changes do not increase the original communication complexity of the BD protocol which is the actual goal for considering its merge with PDHKE. Then, based on our new construction we show how to obtain a secure GKE+S protocol where the communication effort for the derivation of subgroup keys requires only one round; this in contrast to two rounds that would be necessary to establish a subgroup key using the original BD protocol from the scratch.

GKE+P Protocol from Modified BD and PDHKE

In order to obtain a secure merge of BD and PDHKE we make use of the following trick in the computation of z i : Instead of computing z i := (y i+1 /y i-1 ) x i we let each

U i first compute k ′ i,i+1 := y x i i+1 and k ′ i-1,i := y x i i-1 and then compute z i as an XOR sum H(k ′ i-1,i ) ⊕ H(k ′ i,i+1
). This does not introduce new communication costs to the BD protocol but has impact on the computation of the group key. We observe that similar trick has been applied for a different purpose by Kim, Lee, and Lee [START_REF] Kim | Constant-Round Authenticated Group Key Exchange for Dynamic Groups[END_REF], who considered possible extensions of BD-like protocols to handle dynamic membership events such as join and leave or to speed up the computation process, whereas here we use the trick exclusively to achieve independence between the group and p2p keys.

The actual description of the protocol which we denote mBD+P follows. Since we are interested in AKE-secure constructions we describe the necessary authentication steps as well. For this we assume that each U i is in possession of a long-lived key pair (sk i , pk i ) ← KeyGen(1 κ ) for the EUF-CMA secure digital signature scheme Σ = (KeyGen, Sign, Verify). The authentication procedure is similar to the general authentication technique from [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF], except that we construct the session id using elements from G as nonces; thus saving the communication costs. The protocol proceeds in two stages: the group stage involves all members of the group and results in the computation of the common group key, whereas the p2p stage is executed on-demand by any two group members wishing to compute an independent p2p key.

Group Stage. Let the group be defined by pid = (U 1 , . . . , U n ). In the following description we assume that user indices form a cycle such that U 0 = U n and U n+1 = U 1 . Round 1. Each U i computes y i := g x i for some random x i ∈ R Z Q and broadcasts (U i , y i ). Round 2. Each U i proceeds as follows:

-

compute sid i := (U 1 |y 1 , . . . , U n |y n ), -k ′ i-1,i := y x i i-1 and k ′ i,i+1 := y x i i+1 , -z ′ i-1,i := H(k ′ i-1,i , sid i ) and z ′ i,i+1 := H(k ′ i,i+1 , sid i ), -z i := z ′ i-1,i ⊕ z ′ i,i+1 , -σ i := Sign(sk i , (U i , z i , sid i )), -broadcast (U i , z i , σ i ).
Group Key Computation. Each U i checks whether z 1 ⊕. . .⊕z n = 0 and whether all received signatures σ j are valid and aborts if any of these checks fails. Otherwise, U i proceeds as follows:

-iteratively for each j = i, . . . , i + n -1:

z ′ j,j+1 := z ′ j-1,j ⊕ z j , -accept k i := H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ).
P2P Stage. On input any user identity U j ∈ pid i the corresponding user U i proceeds as follows:

-compute k ′ i,j := y x i j = g x i x j , -derive k i,j := H p (k ′ i,j , U i |y i , U j |y j ). (W.l.o.g. we assume that both users U i and U j use the same order for the inputs to H p .)

Here we observe that the computation of p2p keys proceeds without any interaction.

GKE+S Protocol from Modified BD and PDHKE

In this section we extend our previous protocol to a secure GKE+S solution. We call it mBD+S. The design rationale is as follows: Users run the group stage to compute the group key and then any subgroup can on-demand repeat the second round of the protocol re-using the exponents from the group stage. Observe that each subgroup identified by some spid ⊂ pid uniquely determines its own cycle. However, there can be many subgroups involving the same pair of users U i and U j in which they are located at neighboring positions. In order to avoid the use of the same value z ′ i,j for the derivation of different subgroup keys we include a subgroup session id ssid i given as the concatenation of all (U i , y i ) with U i ∈ spid as additional input to H.

Since the group stage of the current protocol does not change with respect to the protocol in the previous section, we only present below the subgroup stage.

Subgroup Stage. On input any subgroup spid ⊂ pid the corresponding users perform the following steps. For the ease of presentation we assume that spid = (U 1 , . . . , U m ) with m < n and that U 0 = U m and U m+1 = U 1 . Round 1. Each U i ∈ spid proceeds as follows:

-

extract ssid i := (U 1 |y 1 , . . . , U m |y m ) from sid i ; -k ′ i-1,i := y x i i-1 and k ′ i,i+1 := y x i i+1 , -z ′ i-1,i := H(k ′ i-1,i , ssid i ) and z ′ i,i+1 := H(k ′ i,i+1 , ssid i ), -z i := z ′ i-1,i ⊕ z ′ i,i+1 , -σ i := Sign(sk i , (U i , z i , ssid i )), -broadcast (U i , z i , σ i ).
Subgroup Key Computation. Each U i checks whether z 1 ⊕ . . . ⊕ z m = 0 and whether all received signatures σ j are valid and aborts if any of these checks fails. Otherwise, U i proceeds as follows:

-iteratively for each j = i, . . . , i + m -1:

z ′ j,j+1 := z ′ j-1,j ⊕ z j , -accept k i,J := H s (z ′ 1,2 , . . . , z ′ m,1
, ssid i ). (W.l.o.g. we assume that all users in spid use the same order for the inputs to H s .) Note that for subgroups of size two, i.e. containing only U i and U j , both users can still derive their p2p key without executing the subgroup stage simply as k i,j := H s (z ′ i,j , (U i |y i , U j |y j )).

Generalized Security Model

Here we generalize the GKE+P model by Manulis [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] towards consideration of subgroup keys computed by participants of a GKE protocol.

Participants, Sessions, and Correctness of GKE+P Protocols

Let U denote a set of at most N users (more precisely, their identities which are assumed to be unique) in the universe. We assume that any subset of n users (2 ≤ n ≤ N ) can be invoked for a single session of a GKE+S protocol P. Each U i ∈ U holds a (secret) long-lived key LL i . The participation of U i in distinct, possibly concurrent protocol sessions is modeled via an unlimited number of instances Π s i , s ∈ N. An instance Π s i can be invoked for one GKE+S session with some partner id pid s i ⊆ U encompassing the identities of all the intended participants (including U i ). An execution of a GKE+S protocol is then split in two stages, denoted as group stage and subgroup stage, described in the following.

The group stage results in Π s i holding a session id sid s i which uniquely identifies the current protocol session. Any two instances Π s i and Π t j are considered as being partnered if sid s i = sid t j and pid s i = pid t j . The success of the group stage for some instance Π s i is modeled through its acceptance with some session group key k s i . Each instance Π s i that has accepted in the group stage can later be invoked for the subgroup stage on input some subgroup partner id spid s i ⊂ pid s i (which includes U i ). This invocation can be performed several times for different subgroups of pid s i . The success of the subgroup stage for some Π s i is modeled through its acceptance with some session subgroup key k s i,J , whereby J denotes the set of indices of users in spid s i , i.e. it includes all j with U j ∈ spid s i .

Definition 2 (GKE+S/GKE+P Protocols). P is a group key exchange protocol enabling on-demand derivation of subgroup keys (GKE+S) if P consists of the following two protocols/algorithms:

P.GKE(U 1 , . . . , U n ): For each U i , a new instance Π s i with pid s i = (U 1 , . . . , U n
) is created and a probabilistic interactive protocol between these instances is executed such that at the end every instance Π s i accepts holding the session group key k s i . This protocol defines the group stage. P.SKE(Π s i , spid s i ): On input an accepted instance Π s i and a subgroup partner id spid s i ⊂ pid s i this deterministic (possibly interactive) algorithm outputs the session subgroup key k s i,J . This algorithm defines the subgroup stage. (We assume that SKE is given only for groups of size n ≥ 3 since for n = 2 the group key is sufficient.)

A GKE+S protocol P is correct if (when no adversary is present) all instances invoked for the group stage P.GKE accept with identical group keys and for all instances Π t j partnered with Π s i the subgroup stage results in P.SKE(Π t j , spid t j ) = P.SKE(Π s i , spid s i ) if spid t j = spid s i . P is a group key exchange protocol enabling on-demand derivation of p2p keys (GKE+P) if it is a GKE+S protocol in which the only admissible input to SKE is of the form spid s i = (U i , U j ). The execution of SKE in this case defines the p2p stage.

Adversarial Model and Security Goals

Security of GKE+S protocols must ensure independence of the session group key k s i and any subgroup key k s i,J . In particular the secrecy of k s i must hold even if any subgroup key k s i,J is leaked to the adversary. Similarly, the leakage of the group key k s i must guarantee the secrecy of any subgroup key k s i,J . Since the computation of subgroup keys is triggered on-demand we must provide the adversary with the ability to schedule the execution of P.SKE on the subgroups of its choice.

Additionally, GKE+S protocols must ensure independence amongst different subgroup keys. That is the knowledge of some k s i,J should not reveal information about any other subgroup key computed by Π s i or any partner Π t j . This requirement implicitly assumes that some participants U j with j ∈ J may collude during the protocol execution.

Finally, the described independence amongst the group and subgroup keys must hold across different sessions of GKE+S.

Adversarial Model. The adversary A, modeled as a PPT machine, can schedule the protocol execution and mount attacks through a set of queries:

-Execute(U Terminology. We say that U is honest if no Corrupt(U ) has been asked by A; otherwise, U is corrupted (or malicious). This also refers to the instances of U .

Two Notions of Freshness. The classical notion of freshness imposes several conditions in order to prevent any trivial break of the AKE-security. Obviously, we need two definitions of freshness to capture such conditions for the both key types.

First, we define the notion of instance freshness which will be used in the definition of AKE-security of group keys. Our definition is essentially the one given in [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF].

Definition 3 (Instance Freshness). An instance Π s

i is fresh if Π s i has accepted in the group stage and none of the following is true, whereby Π t j denotes an instance partnered with Π s i : (1) RevealGK(Π s i ) or RevealGK(Π t j ) has been asked, or (2) Corrupt(U ′ ) for some U ′ ∈ pid s i was asked before any Send(Π s i , •).

Note that in the context of GKE+S the above definition restricts A from active participation on behalf of any user during the attacked session, but implicitly allows for the leakage of (all) subgroup keys. Additionally, we define the notion of instance-subgroup freshness which will be used to specify the AKE-security of subgroup keys.

Definition 4 (Instance-Subgroup Freshness

). An instance-subgroup pair (Π s i , spid s i ) is fresh if Π s i has accepted in the group stage and none of the following is true, whereby Π t j is assumed to be partnered with Π s i and spid t j = spid s i : (1) RevealSK(Π s i , spid s i )

or RevealSK(Π t j , spid t j ) has been asked, or (2) Corrupt(U i ) or Corrupt(U j ) was asked before any Send(Π s i , •) or Send(Π s j , •).

Here A is explicitly allowed to actively participate in the attacked session on behalf of any user except for U i and any U j ∈ spid s i . Also A may learn the group key k i and all subgroup keys except for k i,J returned by P.SKE(Π s i , spid s i ). This models possible collusion of participants from pid s i \ spid s i during the execution of the protocol aiming to break the secrecy of the subgroup key k i,J . AKE-Security of Group and Subgroup Keys. For the AKE-security of group keys we follow the definition from [START_REF] Katz | Scalable Protocols for Authenticated Group Key Exchange[END_REF].

Definition 5 (AKE-Security of Group Keys). Let P be a correct GKE+P protocol and b a uniformly chosen bit. By Game ake-g,b A,P (κ) we define the following adversarial game, which involves a PPT adversary A that is given access to all queries:

-A interacts via queries; -at some point A asks a TestGK(Π s i ) query for some instance Π s i which is (and remains) fresh; -A continues interacting via queries; -when A terminates, it outputs a bit, which is set as the output of the game.

We define

Adv ake-g A,P (κ) := 2 Pr[Game ake-g,b A,P (κ) = b] -1 and denote with Adv ake-g P (κ) the maximum advantage over all PPT adversaries A. We say that P provides AKE-security of group keys if this advantage is negligible.

Finally, we define AKE-security of subgroup keys while considering possible collusion attacks, as above but with a TestSK(Π s i , spid s i ) query.

Definition 6 (AKE-security of Subgroup Keys). Let P be a correct GKE+S protocol and b a uniformly chosen bit. By Game ake-s,b A,P (κ) we define the following adversarial game, which involves a PPT adversary A that is given access to all queries:

-A interacts via queries; -at some point A asks a TestSK(Π s i , spid s i ) query for some instance-subgroup pair (Π s i , spid s i ) which is (and remains) fresh; -A continues interacting via queries; -when A terminates, it outputs a bit, which is set as the output of the game.

We define

Adv ake-s A,P (κ) := 2 Pr[Game ake-s,b A,P (κ) = b] -1 and denote with Adv ake-s P (κ) the maximum advantage over all PPT adversaries A. We say that P provides AKE-security of subgroup keys if this advantage is negligible.

Security of Our GKE+P and GKE+S Protocols

In this section we analyze security of our mBD+P and mBD+S protocols using our generalized security model. The corresponding proofs of our theorems can be found in appendix. The security results hold in the random oracle model. The following two theorems show that mBD+P is a secure GKE+P protocol. Theorem 7. If the GDH problem is hard in G then our protocol mBD+P provides AKE-security of group keys and

Adv ake-g mBD+P (κ) ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ-1 +2N Succ euf-cma Σ (κ) + 2q Se N q H Succ GDH G (κ) + q Hg 2 κ
with at most (q Ex + q Se ) sessions being invoked via Execute and Send queries and at most q Hg , q Hp , and q H random oracle queries being asked.

Theorem 8. If the GDH problem is hard in G then our protocol mBD+P provides AKE-security of p2p keys and

Adv ake-p mBD+P (κ) ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ-1 +2N Succ euf-cma Σ (κ) + 2q Se (N q H + q SKE q Hp )Succ GDH G (κ)
with at most (q Ex + q Se ) sessions being invoked via Execute and Send queries, at most q SKE p2p keys being computed via SKE queries, and at most q Hg , q Hp , and q H random oracle queries being asked.

Our next two theorems prove that mBD+S is a secure GKE+S protocol. The main difference in the security analysis is the consideration of the additional communication round for the subgroup stage (Theorem 10). Since the group stage of mBD+S does not differ from that of mBD+P, the proof of Theorem 9 follows from that of Theorem 7.

Theorem 9. If the GDH problem is hard in G then our protocol mBD+S provides AKE-security of group keys and

Adv ake-g mBD+S (κ) ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hs ) 2 2 κ-1 +2N Succ euf-cma Σ (κ) + 2q Se N q H Succ GDH G (κ) + q Hg 2 κ
with at most (q Ex + q Se ) sessions being invoked via Execute and Send queries and at most q Hg , q Hs , and q H random oracle queries being asked.

Theorem 10. If the GDH problem is hard in G then our protocol mBD+S provides AKE-security of subgroup keys and

Adv ake-s mBD+S (κ) ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hs ) 2 2 κ-1 + 2N Succ euf-cma Σ (κ) +2q Se N + (N -1)q SKE q H Succ GDH G (κ) + q SKE q Hs 2 κ
with at most (q Ex + q Se ) sessions being invoked via Execute and Send queries, at most q SKE subgroup stages being invoked via SKE queries, and at most q Hg , q Hs , and q H random oracle queries being asked.

Performance Comparison

In Table 1 we compare the complexity of our protocols. We measure the communication costs as a total number of transmitted elements in G, and computation costs as a number of modular exponentiations per U i (in the case of BD we count only exponentiations with x i assuming that |x i | ≫ n). We omit signature generation and verification costs, which are equal for all considered protocols. The first part of the table is devoted to GKE+P protocols. By GKE+P BD we denote the protocol from [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] in which the original Burmester-Desmedt protocol is executed in parallel with PDHKE, i.e. each user U i uses two independent exponents i and xi for the computation of the group key and any p2p key, respectively. By GKE+P KPT we denote the tree-based Kim-Perrig-Tsudik protocol from [START_REF] Kim | Group Key Agreement Efficient in Communication[END_REF] in which each user U i holds only one exponent x i and uses it to compute both types of keys, which has been proven secure in [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF]. Since all GKE+P protocols apply the PDHKE technique for the derivation of p2p keys we also exclude the computation costs needed to compute a Diffie-Hellman secret k ′ i,j that requires constantly one exponentiation per each U j . Then, we observe that in comparison to GKE+P BD our mBD+P protocol has better communication complexity since it requires each U i to hold only one exponent x i . Note also that the PDHKE-KPT protocol has asymmetric costs, depending on the position of U i in the sequence U 1 , . . . , U n . Although this asymmetry may have benefits in groups with heterogeneous devices we remark that in general this protocol has much worse computation complexity.

The second part of the table compares the effort needed to derive a subgroup key for any subgroup of size m < n. By GKE+S BD we consider the trivial solution in which the original BD protocol from [START_REF] Burmester | A Secure and Efficient Conference Key Distribution System[END_REF] is executed for each new subgroup. We compare it to the subgroup stage of our mBD+S protocol, which requires only one communication round per subgroup. Observe that the group stage of mBD+S is executed only once and its complexity is identical to the complete execution of the BD protocol. By ≤ 2 in the computation costs of mBD+S we point out that users can re-use the intermediate values k ′ i-1,i and k ′ i,i+1 possibly computed during the group stage or during the subgroup stage for another subgroup, provided the relative position of U i-1 and U i or of U i and U i+1 in the cyclic order of the new subgroup remains the same. In this way our mBD+S protocol also offers a trade-off between space and computation complexity depending on whether users wish to cache the intermediate values that re-occur in different protocol stages.

Conclusion

The increasing popularity of multi-user communication systems offering various forms of communication can be secured using flexible GKE protocols that provide more than just a secret group key for the initial set of their participants. This paper addressed the extension of this basic functionality of GKE protocols towards the computation of different types of keys allowing a secure mix of group, subgroup, and peer-to-peer communication. While our mBD+P protocol with improved complexity compared to the protocols from [START_REF] Manulis | Group Key Exchange Enabling On-Demand Derivation of Peer-to-Peer Keys[END_REF] allows a secure mix of group and peer-to-peer communication our mBD+S protocol extends this approach to obtain the additional secure communication within any possible subgroup. upper-bound the probability of collisions for k i and collisions between k i and any k i,j by (q Hg + q Hp ) 2 /2 κ . Thus,

| Pr[Win ake-g 1 ] -Pr[Win ake-g 0 ]| ≤ N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ . Game G 2 .
In this game we assume that ∆ fails and bit b ′ is set at random if A queries Send containing (U i , z i , σ i ) with σ i being a valid signature that has not been previously output by an uncorrupted oracle Π s i . In other words the simulation aborts if A outputs a successful forgery. Following the classical reductionist argument (see for instance [START_REF] Bresson | Provably Authenticated Group Diffie-Hellman Key Exchange[END_REF]) we can build a forger against the signature scheme and upper-bound the probability difference

| Pr[Win ake-g 2 ] -Pr[Win ake-g 1 ]| ≤ N Succ euf-cma Σ (κ).
Game G 3 . In this game we let ∆ guess a value q * ∈ [1, q Se ] and abort if the TestGK query is not asked for the session invoked by the q * -th query. Let Q be the event that this guess is correct and Pr[Q] = 1/q Se . Thus,

Pr[Win ake-g 3 ] = Pr[Win ake-g 2 ] 1 q Se + 1 2 1 - 1 q Se .
This implies,

Pr[Win ake-g 2 ] = q Se Pr[Win ake-g 3 ] - 1 2 + 1 2 .
Game G 4 . In this game we assume that ∆ is given access to the private random oracle H ′ : {0, 1} * → {0, 1} κ and computes in the simulation of the q * -th session for each pair of consecutive users (U i , U i+1 ) in the cycle z ′ i,i+1 = H ′ (i, i + 1). Clearly both games remain indistinguishable unless A queries H(k ′ i,i+1 ) for any i ∈ [1, n]. However, this query can be used to break the GDH problem in G, i.e. ∆ embeds g a and g b from the challenge of the GDH problem into the corresponding values g x i and g x i+1 , and uses the access to the DDH oracle D in order to identify k ′ i,i+1 = g x i x i+1 provided by A as input to H. Therefore,

| Pr[Win ake-g 4 ] -Pr[Win ake-g 3 ]| ≤ N q H Succ GDH G (κ).
As a result of this game the group key k i computed in the q * -th session is the output of H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) where all input values z ′ 1,2 , . . . , z ′ n,1 are uniform in {0, 1} κ . Since H g is modeled as a random oracle and collisions on group keys computed in two different sessions have been excluded in Game G 1 the probability that A wins without querying H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) is 1/2; on the other hand, the probability that A asks such a query is given by q Hg /2 nκ < q Hg /2 κ (for the guess of z ′ 1,2 , . . . , z ′ n,1 ). Hence, Pr[Win ake-g 4 ] ≤ 1/2 + q Hg /2 κ . Summarizing the above equations we obtain a negligible advantage

Adv ake-g mBD+P (κ) = |2 Pr[Win ake-g 0 ] -1| ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ-1 + 2N Succ euf-cma Σ (κ) + 2q Se N q H Succ GDH G (κ) + q Hg 2 κ . ⊓ ⊔

B Proof of Theorem 2

In the following we show that the advantage of A in distinguishing any k i,j computed by uncorrupted users U i and U j from some random element in {0, 1} κ is negligible. We construct a sequence of games G 0 , . . . , G 6 and denote by Win ake-g i the event that the bit b ′ output by A is identical to the randomly chosen bit b in the i-th game. Recall that in each game TestSK(Π s i , spid s i ) is answered only if the instance-subgroup pair (Π s i , spid s i ) is fresh. Game G 0 . This is the real execution of mBD+P in which a simulator ∆ truly answers all queries of A on behalf of the instances as defined in Game ake-p,b A,mBD+P (κ). We assume that A has access to the hash queries for the hash functions H, H g , and H p , which are modeled as random oracles. Game G 1 . In this game we exclude for every honest user U i the collisions of the transcripts (U i , y i ) and group keys k i . We also exclude collisions between k i and any p2p key k i,j . we exclude collisions amongst p2p keys k i,j computed by U i for different (possibly malicious) U j . Since sessions can be invoked via Execute and Send queries we obtain for the collision on transcripts (according to the birthday paradox) the probability of at most N (q Ex + q Se ) 2 /Q over all possible users. Collisions amongst k i and collisions between k i and any k i,j can be upper-bounded by (q Hg + q Hp ) 2 /2 κ using the same argument as in Game G 1 from the proof of Theorem 7. This upper-bound also includes collisions amongst k i,j computed by the same honest U i for different U j . To see this observe that even if U j malicious and chooses own y j in some rogue way (e.g. in relation to other values) the input to H p (k ′ i,j , U i |y i , U j |y j ) still remains unique due to the uniqueness of the honest user's transcript (U i , y i ) and identity U j . Hence,

| Pr[Win ake-p 1 ] -Pr[Win ake-p 0 ]| ≤ N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ .
Game G 2 . In this game we abort simulation (setting bit b ′ at random) if A queries Send containing (U i , z i , σ i ) with σ i being a valid signature that has not been previously output by an oracle of uncorrupted U i . In other words the simulation fails if outputs a successful forgery such that

| Pr[Win ake-p 2 ] -Pr[Win ake-p 1 ]| ≤ N Succ euf-cma Σ (κ).
Game G 3 . In this game ∆ randomly chooses a session q * ∈ R [1, q Se ] and aborts the simulation (setting bit b ′ at random) if A asks the TestSK query to some oracle Π s i that accepted in a group stage of another session, i.e. not in the q * -th session. Using similar argument as in Game G 3 from the proof of Theorem 7 we obtain

Pr[Win ake-p 2 ] = q Se Pr[Win ake-p 3 ] - 1 2 + 1 2 .
As a result of this game it is sufficient for the simulator to focus on the q * -th session and to simulate instances of users participating in the group and p2p stages of that session.

Game G 4 . In this game ∆ is given access to the private random oracle H ′ : {0, 1} * → {0, 1} κ and in the simulation of the q * -th session for each pair of consecutive users (U i , U i+1 ) in the cycle ∆ computes z ′ i,i+1 = H ′ (i, i + 1) if both users U i and U i+1 are uncorrupted. Note that the definition of AKE-security for p2p keys requires the TestSK query to be asked to a fresh instance-subgroup pair (Π s i , spid s i ). In case of p2p keys spid s i would contain two users U i and U j that must be uncorrupted at the moment when their p2p key is computed. However, A is allowed to corrupt and act on behalf of other users during the protocol execution. This replacement remains indistinguishable unless A queries H(k ′ i,i+1 ), in which case we can solve the challenge of the GDH problem (similar to the proof of the previous theorem). Thus,

| Pr[Win ake-p 4 ] -Pr[Win ake-p 3 ]| ≤ N q H Succ GDH G (κ).
This game implies that in the q * -th session the computation of the group key

k i = H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) uses values ′ i,i+1
that are uniform in {0, 1} κ if the respective users U i and U i+1 were uncorrupted at the moment when z ′ i,i+1 was computed. Game G 5 . In this game ∆ randomly chooses value q * * ∈ R [1, q SKE ] and aborts the simulation (setting bit b ′ at random) if A asks its q * * -th query SKE(Π s i , spid s i ) without asking the TestSK(Π s i , spid s i ) query later. I.e. ∆ tries to guess which invocation in the p2p stage of the q * -th session will lead to the computation of the target p2p key. Then,

Pr[Win ake-p 4 ] = q SKE Pr[Win ake-p 5 ] - 1 2 + 1 2 .
Note that if the guess is positive then spid s i contains two uncorrupted users U i and U j .

Game G 6 . In this game we assume that ∆ is given access to the private random oracle H ′ p : {0, 1} * → {0, 1} κ and in response to the q * * -th SKE(Π s i , spid s i ) query guessed above ∆ computes the corresponding p2p key k i,j as H ′ p (U i |y i , U j |y j ) that is independent of k ′ i,j . Again, this replacement remains indistinguishable unless A queries H p (k ′ i,i+1 , U i |y i , U j |y j ), in which case reduction to the GDH problem becomes possible, i.e.

| Pr[Win

ake-p 6 ] -Pr[Win ake-p 5 ]| ≤ q Hp Succ GDH G (κ).
As a consequence the p2p key k i,j is uniform in {0, 1} κ and, thus Pr[Win ake-p 6 ] ≤ 1/2. Summarizing the above equations we obtain a negligible advantage

Adv ake-p mBD+P (κ) = |2 Pr[Win ake-p 0 ] -1| ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hp ) 2 2 κ-1 + 2N Succ euf-cma Σ (κ) + 2q Se (N q H + q SKE q Hp )Succ GDH G (κ) . ⊓ ⊔

C Proof of Theorem 3

In the following we show that the advantage of A in distinguishing k i from some random element from {0, 1} κ is negligible. We construct a sequence of games G 0 , . . . , G 4 and denote by Win ake-g i the event that the bit b ′ output by A is identical to the randomly chosen bit b in the i-th game. Recall that in each game TestGK(Π s i ) is answered only if the instance Π s i is fresh.

uniform in {0, 1} κ . Since H g is modeled as a random oracle and collisions on group keys computed in two different sessions have been excluded in Game G 1 the probability that A wins without querying H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) is 1/2; on the other hand, the probability that A asks such a query is given by q Hg /2 nκ < q Hg /2 κ (for the guess of z ′ 1,2 , . . . , z ′ n,1 ). Hence, Pr[Win ake-g 4 ] ≤ 1/2 + q Hg /2 κ . Summarizing the above equations we obtain a negligible advantage Adv ake-g mBD+S (κ) = |2 Pr[Win ake-g 0 ] -1| ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hs ) 2 2 κ-1 + 2N Succ euf-cma Σ (κ)

+ 2q Se N q H Succ GDH G (κ) + q Hg 2 κ .
⊓ ⊔

D Proof of Theorem 4

In the following we show that the advantage of A in distinguishing any k i,J computed by an instance Π s i of some uncorrupted U i in the subgroup stage with regard to the subgroup spid s i = {U j } j∈J from some random element in {0, 1} κ is negligible. We construct a sequence of games G 0 , . . . , G 8 and denote by Win ake-s i the event that the bit b ′ output by A is identical to the randomly chosen bit b in the i-th game. Recall that in each game TestSK(Π s i , spid s i is answered only if the instance-subgroup pair s i , spid s i ) is fresh. Game G 0 . This is the real execution of mBD+S in which a simulator ∆ truly answers all queries of A on behalf of the instances as defined in Game ake-s,b A,mBD+S (κ). We assume that A has access to the hash queries for the hash functions H, H g , and H s , which are modeled as random oracles. Game G 1 . this game we exclude for every honest user U i the collisions of the transcripts (U i , y i ) and group keys k i . We also exclude collisions between k i and any subgroup key k i,J . Additionally, we exclude collisions amongst subgroup keys k i,J computed by U i for different subgroups spid i consisting of (possibly malicious) U j , j ∈ J. Since sessions can be invoked via Execute and Send queries we obtain for the collision on transcripts (according to the birthday paradox) the probability of at most N (q Ex + q Se ) 2 /Q over all possible users. Collisions amongst k i and collisions between k i and any k i,J can be upper-bounded by (q Hg + q Hs ) 2 /2 κ using the same argument as in Game G 1 from the proof of Theorem 9. This upper-bound also includes collisions amongst k i,J computed by an honest U i for different subgroups involving U j , j ∈ J. This holds since even if U j , j ∈ J is corrupted and chooses own y j in some rogue way (e.g. in relation to other values) the input to H s (z ′ 1,2 , . . . , z ′ m,1 , ssid i ) still remains unique due to the uniqueness of the honest user's transcript (U i , y i ) and identity U j . (Note that for any subgroup spid i ⊂ pid i the subgroup stage can be invoked only once.) Hence, | Pr[Win ake-s 1 ] -Pr[Win ake-s 0 ]| ≤ N (q Ex + q Se ) 2 Q + (q Hg + q Hs ) 2 2 κ .

Game G 2 . In this game we abort simulation (setting bit b ′ at random) if A queries Send containing (U i , z i , σ i ) with σ i being a valid signature that has not been previously replacement remains indistinguishable unless A queries H(k ′ i,i+1 , ssid i ) in which case we again can solve the GDH problem. Since m (the size of the subgroup) is strictly smaller than the size of the group n ≤ N we have This game implies that in the q * * -th subgroup stage the computation of the subgroup key k i,J = H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) uses values z ′ i,i+1 that are uniform in {0, 1} κ . Hence, the probability that A wins without querying H s (z ′ 1,2 , . . . , z ′ n,1 , ssid i ) is 1/2; on the other hand, the probability that A asks such a query is given by q Hs /2 mκ < q Hs /2 κ (for the guess of z ′ 1,2 , . . . , z ′ n,1 ). Hence, Pr[Win ake-s 6 ] ≤ 1/2 + q Hs /2 κ . Summarizing the above equations we obtain a advantage Adv ake-s mBD+S (κ) = |2 Pr[Win ake-s 0 ] -1| ≤ 2N (q Ex + q Se ) 2 Q + (q Hg + q Hs ) 2 2 κ-1 + 2N Succ euf-cma Σ (κ) + 2q Se N + (N -1)q SKE q H Succ GDH G (κ) + q SKE q Hs 2 κ .

⊓ ⊔

| 6 ] 5 ]

 65 Pr[Win ake-s -Pr[Win ake-s | ≤ (N -1)q H Succ GDH G (κ).

  1 , . . . , U n ): This query executes the group stage protocol between new instances of U 1 , . . . , U denotes the identity of its sender. A is then given the protocol message generated by Π s i in response to m (the output may also be empty if m is unexpected or if Π s i accepts). A special invocation query of the form Send(U i , ( ′ start ′ , U 1 , . . . , U n )) creates a new instance Π s i with pid s i := (U 1 , . . . , U n ) and provides A with the first protocol message. This query can be used by A also during the subgroup stage if P.SKE requires interaction. Corrupt(U i ): This query provides A with LL i . Note that in this case A does not gain control over the user's behavior, but might be able to communicate on behalf of the user.-TestGK(Π s i ): This query models indistinguishability of session group keys. Depending on a given (privately flipped) bit b A is given, if b = 0 a random session group key, and if b = 1 the real k s i . This query can be asked only once and is answered only if Π s i has accepted in the group stage.

	-SKE(Π s i , spid s i ): This query allows A to schedule the on-demand computation of subgroup keys. If P.SKE requires interaction then Π s i returns A its first message for the subgroup stage; otherwise Π s i computes the subgroup key k s i,J . This query is processed only if Π s i has accepted and spid s i ⊂ pid s i . Additionally, this query can be asked only once per input (Π s i , spid s i ). -RevealGK(Π s i ): This query models the leakage of group keys and provides A with k s i . It is answered only if Π s i has accepted in the group stage. -RevealSK(Π s i , spid s i ): This query models the leakage of subgroup keys and pro-vides A with the corresponding k s i,J ; the query is answered only if the algorithm SKE(Π s i , spid s i ) has already been invoked and the subgroup key computed.
	-

n ∈ U and provides A with the execution transcript.

-Send(Π s i , m) : With this query A can deliver a message m to Π s i whereby U -TestSK(Π s i , spid s i ): This query models indistinguishability of session subgroup keys. Depending on a given (privately flipped) bit b A is given, if b = 0 a random session p2p key, and if b = 1 the real k s i,J . This query is answered only if the algorithm SKE(Π s i , spid s i ) has already been invoked and the subgroup key computed.

Table 1 .

 1 Performance Comparison of GKE+P and GKE+S Protocols

	GKE+P/S Protocols Rounds Communication	Computation
			(in log Q bits)	(in mod. exp. per Ui)
	GKE+P BD [27]	2	3n	3
	GKE+P KPT [27]	2	2n -2	n + 2 -i (2n -2 for U1)
	our mBD+P	2	2n	3
	GKE+S BD	2	2m	2
	our mBD+S	1	m	≤ 2

c Springer-Verlag, 2010.

Acknowledgments

This work was supported in part by the European Commission through the ICT Program under Contract ICT-2007-216676 ECRYPT II, by the French ANR-07-SESU-008-01 PAMPA Project, and through the Center for Advanced Security Research Darmstadt (www.cased.de).

A Proof of Theorem 1

In the following we show that the advantage of A in distinguishing k i from some random element from {0, 1} κ is negligible. We construct a sequence of games G 0 , . . . , G 4 and denote by Win ake-g i the event that the bit b ′ output by A is identical to the randomly chosen bit b in the i-th game. Recall that in each game TestGK(Π s i ) is answered only if the instance Π s i is fresh. Game G 0 . This is the real execution of mBD+P in which a simulator ∆ truly answers all queries of A on behalf of the instances as defined in Game ake-g,b A,mBD+P (κ). We assume that A has access to the hash queries for the hash functions H, H g , and H p , which are modeled as random oracles in the classical way, i.e., by returning new random values for new queries and replaying answers if the queries were previously made.

Game G 1 . In this game we exclude for every honest user U i the collisions of the transcripts (U i , y i ) and group keys k i computed in different sessions. We also exclude any collisions between k i and any p2p key k i,j . Regarding the transcripts we observe that if U i is honest then its session value y i is randomly distributed in G (as a result of y i := g x i for x i ∈ R Z Q ). Thus, according to the birthday paradox the collision on transcripts occurs with the probability of at most N (q Ex + q Se ) 2 /Q over all possible users (recall that sessions can be invoked via Execute and Send queries). The uniqueness of transcripts also implies the uniqueness of inputs to H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ). By construction inputs to H g remain always different from the inputs to H p . Since H g and H p are modeled as random functions we can also apply the birthday paradox and Game G 0 . This is the real execution of mBD+S in which a simulator ∆ truly answers all queries of A on behalf of the instances as defined in Game ake-g,b A,mBD+S (κ). We assume that A has access to the hash queries for the hash functions H, H g , and H s , which are modeled as random oracles in the classical way, i.e., by returning new random values for new queries and replaying answers if the queries were previously made. Game G 1 . In this game we exclude for every honest user U i the collisions of the transcripts (U i , y i ) and group keys k i computed in different sessions. We also exclude any collisions between k i and any subgroup key k i,J . Regarding the transcripts we observe that if U i is honest then its session value y i is randomly distributed in G (as a result of y i := g x i for i R Z Q ). Thus, according to the birthday paradox the collision on transcripts occurs with the probability of at most N (q Ex + q Se ) 2 /Q over all possible users (recall that sessions can be invoked via Execute and Send queries). The uniqueness of transcripts also implies the uniqueness of inputs to H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ). Since for each possible subgroup the corresponding ssid i ⊂ sid i by an instance of i for the computation of the subgroup key does not repeat and since H g and H s are modeled as random functions we can also apply the birthday paradox and upper-bound the probability of collisions for k i and collisions between k i and any k i,J by (q Hg +q Hs ) 2 /2 κ . Thus,

In this game we assume that ∆ fails and bit b ′ is set at random if forges some signature, i.e. if A queries Send containing (U i , z i , σ i ) with σ i being a valid signature that has not been previously output by an uncorrupted instance of U i . Hence,

Game G 3 . In this game we let ∆ guess a value q * ∈ [1, q Se and abort if the TestGK query is not asked for the session invoked by the q * -th query. Similar to Game G 3 from the proof of Theorem 7 we obtain

Game G 4 . In this game we assume that ∆ is given access to the private random oracle H ′ : {0, 1} * → {0, 1} κ and computes in the group stage of the q * -th session for each pair of consecutive users

Clearly both games remain indistinguishable unless A queries H(k ′ i,i+1 ) for any i ∈ [1, n]. However, this query can be used to break the GDH problem in G, i.e. ∆ embeds g a and g b from the challenge of the GDH problem into the corresponding values g x i and g x i+1 used on behalf U i and U i+1 in the group stage, and uses the access to the DDH oracle D in order to identify k ′ i,i+1 = g x i x i+1 provided by A as input to H. Therefore,

As a result of this game the group key k i computed in the q * -th group stage session is the output of H g (z

Game G 3 . In this game ∆ randomly chooses a session q * ∈ R [1, q Se ] and aborts the simulation (setting bit b ′ at random) if A asks the TestSK query to some oracle Π s i that accepted in a group stage of another session, i.e. not in the q * -th session. Using similar argument as in Game G 3 from the proof of Theorem 7 we obtain

As a result of this game it is sufficient for the simulator to focus on the q * -th session and to simulate instances of participating in the group and subgroup stages of that session.

Game G 4 . In this game ∆ is given access to the private random oracle H ′ : {0, 1} * → {0, 1} κ and in the simulation of the q * -th group stage session ∆ computes for each pair of consecutive users (U i , U i+1 ) in the cycle z ′ i,i+1 = H ′ (i, i + 1) if both users i and U i+1 are uncorrupted. Note that the definition of AKE-security for subgroup keys requires the TestSK query to be asked to a fresh instance-subgroup pair (Π s i , spid s i ), that is users in the subgroup spid s i remain uncorrupted until the computation of the subgroup key. Our replacement remains indistinguishable unless A queries H(k ′ i,i+1 ), in which case we can solve the GDH problem. Thus,

Note also that the simulation remains perfect if A corrupts U i or U i+1 later since the corrupt query does not reveal their secret exponents. This game also implies that in the q * -th session values z ′ i,i+1 computed for pairs (U i , U i+1 ) of uncorrupted users and used in the computation of k i = H g (z ′ 1,2 , . . . , z ′ n,1 , sid i ) are uniform in {0, 1} κ . Game G 5 . In this game ∆ tries to guess the invocation of the subgroup stage which will be selected by A as a target for the attack. That is ∆ chooses a value q * * ∈ R [1, q SKE ] at random and aborts the simulation (setting bit b ′ at random) if A does not ask its TestSK query to an instance that participates in the q * * -th subgroup stage. The probability that ∆ correctly guesses q * * is 1/q SKE , and

If the guess is successful then users in the target subgroup remain uncorrupted until the subgroup key is computed. The target subgroup defines its own cycle for the order of users in which two neighboring users U i and U i+1 may have not been neighbors in the defined by the group stage. Therefore, we need to apply the same changes as in the previous game with respect to the subgroup's cycle in order to achieve uniformity of values z ′ i,i+1 that will be used to compute the subgroup key. Game G 6 . In this game ∆ has access to the private random oracle H ′ : {0, 1} * → {0, 1} κ . In the simulation of the guessed q * * -th subgroup stage ∆ computes for each pair of consecutive users (U i , U i+1 ) in the cycle defined by spid s i = (U 1 , . . . , U m ) the intermediate value z ′ i,i+1 = H ′ (i, i + 1, ssid i ), that is independent of k ′ i,i+1 . This