# On Constructing Dynamic and Forward Secure Authenticated Group Key Agreement Scheme from Multikey Encapsulation Mechanism

Authors: Iraj Fathirad; John Devlin
Journal: The Scientific World Journal
 (2015)

---

## Abstract

The approach of instantiating authenticated group key exchange (GAKE) protocol from the multikey encapsulation mechanism (mKEM) has an important advantage of achieving classical requirement of GAKE security in one communication round. In spite of the limitations of this approach, for example, lack of forward secrecy, it is very useful in group environments when maximum communication efficiency is desirable. To enrich this mKEM-based GAKE construction, we suggest an efficient solution to convert this static GAKE framework into a partially dynamic scheme. Furthermore, to address the associated lack of forward-secrecy, we propose two variants of this generic construction which can also provide a means of forward secrecy at the cost of extra communication round. In addition, concerning  associated implementation cost of deploying this generic GAKE construction in elliptic curve cryptosystem, we compare the possible instantiations of this model from existing mKEM algorithms in terms of the number of elliptic curve scalar multiplications.


---

## Body

## 1. Introduction

A reliable and secure shared-key distribution scheme is arguably the most import step toward establishing any cryptographic channel among group of communicating parties. The group key exchange protocol (GKE) allows the members to calculate the shared-key over a public communication medium. An authenticated group key exchange (GAKE) scheme ensures that the resultant shared-key is kept indistinguishable to nonlegitimate peers and provides the participants with resistance against impersonation attack. A recently proposed approach [1] to achieve the classical requirement of authenticated key exchange security [2–4] for group scenario in one communication round is to construct it from the multikey encapsulation mechanism (mKEM). We refer to this generic framework bymkGAKE model. AnmKEM [5] is a multipeer cryptographic solution that assumes receivers with long-term certified private/public-key pairs, and enables one entity to generate and efficiently encapsulate the same random session key for multiple receivers. ThemkGAKE framework is basically constructed by parallel execution of a securemKEM scheme among n parties. While this communicationally efficient GAKE construction provides the participants with basic requirements of key-confidentiality and impersonation resistance, it has two important limitations that can essentially affect the security and functionality of this model. These shortcomings and their undesirable effects are described below:(1)
Lack of forward secrecy (FS): This implies compromising long-term keying materials of peers affects the confidentiality of previously established shared session keys. Since the existingmKEM solutions that used as building block of this framework are not FS, the resultant GAKE construction is not FS as well. FS is a desirable feature of a GAKE solution as it ensures the shared-key history remains confidential even after revealing the long-term keying materials of participants.(2)
Inability to provide an efficient solution for dynamic group environments: This implies the participants need to reexecute the GAKE protocol when new members join or existing members leave. It is desirable for a GAKE protocol to provide an efficient mechanism for join/leave operations rather than reexecuting the scheme in dynamic group environment.Another fundamental factor in analyzing the practicality of this framework is the computational cost of instantiating this generic model. Implementing this framework with the elliptic curve cryptosystem (ECC) can significantly reduce keys/parameters/messages size compared to the non-ECC variants [6]. It is therefore desirable to evaluate the ECC related deployment cost of this generic GAKE construction.


### 1.1. Our Contribution

In this paper we propose a generic framework to convert the existing staticmkGAKE model to a partially dynamic scheme which provides a more efficient mechanism in the operation of joining new members to an already established session. In addition, to enrich the existingmkGAKE construction, we propose two variants of this model to achieve the important goal of forward secrecy at the cost of an extra communication round. As a further contribution, we evaluate the implementation cost of instantiating this model in ECC from existingmKEM schemes.


### 1.2. Related Works

Most of the group key exchange protocols in literature are based on either DH [11] or Joux [12] algorithms and require multiple rounds to establish the shared-key. Constructing a one-round, yet secure, GAKE is very desirable due to its appealing bandwidth efficiency compared to other multiround solutions. One of the first attempts to formalize one-round GAKE protocols was made in [13] that divides protocols into three different classes:(1)
In the first class, peers are assumed to hold a preshared secret which is impractical and unreasonable in real environments [14].(2)
In the second class one party encrypts its nonce to other participants together with digital signature on its encrypted nonce while other parties send their random values in the clear. An instantiation of such a scheme is given in [15]. It suffers from intensive computational overhead imposed by using digital signature as well as an inherent security concern resulting from unequal distribution of the key exchange responsibilities and giving extreme power to the encryptor party.(3)
In the third class, which equally distributes the power and responsibility between participants, all peers encrypt their nonce to other entities using other participants’ certified public-keys. A generic model to efficiently instantiate this class of one-round GAKE scheme frommKEM construction is given in [1] (referred to asmkGAKE model). So far, thismkGAKE model is the only practical one and provably secures one-round implicitly authenticated group key exchange construction in literature to date (while it is theoretically possible to construct a one-round GKE scheme by using multilinear map [16] and then converting it to an implicitly authenticated GAKE scheme in a similar way as MQV [17] or HMQV [18]; but, in spite of some recent improvements in constructing a plausible multilinear map [19, 20], these schemes are still far from being efficiently practical).


### 1.3. Organization

The next section discusses ECC andmKEM schemes and reviews the operation of dynamic GAKE protocols. In this section we also study the existingmKEM-based GAKE framework. In Section 3 we present our two variants ofmKEM-based GAKE model with forward secrecy. In Section 4 we propose a generic framework to convert this existing static GAKE framework to a partially dynamic scheme. Finally, in Section 5 we compare the implementation cost of this framework from the possible ECC translation of existingmKEM solutions. Section 6 gives a summary of our work and highlights the important points.


## 1.1. Our Contribution

In this paper we propose a generic framework to convert the existing staticmkGAKE model to a partially dynamic scheme which provides a more efficient mechanism in the operation of joining new members to an already established session. In addition, to enrich the existingmkGAKE construction, we propose two variants of this model to achieve the important goal of forward secrecy at the cost of an extra communication round. As a further contribution, we evaluate the implementation cost of instantiating this model in ECC from existingmKEM schemes.


## 1.2. Related Works

Most of the group key exchange protocols in literature are based on either DH [11] or Joux [12] algorithms and require multiple rounds to establish the shared-key. Constructing a one-round, yet secure, GAKE is very desirable due to its appealing bandwidth efficiency compared to other multiround solutions. One of the first attempts to formalize one-round GAKE protocols was made in [13] that divides protocols into three different classes:(1)
In the first class, peers are assumed to hold a preshared secret which is impractical and unreasonable in real environments [14].(2)
In the second class one party encrypts its nonce to other participants together with digital signature on its encrypted nonce while other parties send their random values in the clear. An instantiation of such a scheme is given in [15]. It suffers from intensive computational overhead imposed by using digital signature as well as an inherent security concern resulting from unequal distribution of the key exchange responsibilities and giving extreme power to the encryptor party.(3)
In the third class, which equally distributes the power and responsibility between participants, all peers encrypt their nonce to other entities using other participants’ certified public-keys. A generic model to efficiently instantiate this class of one-round GAKE scheme frommKEM construction is given in [1] (referred to asmkGAKE model). So far, thismkGAKE model is the only practical one and provably secures one-round implicitly authenticated group key exchange construction in literature to date (while it is theoretically possible to construct a one-round GKE scheme by using multilinear map [16] and then converting it to an implicitly authenticated GAKE scheme in a similar way as MQV [17] or HMQV [18]; but, in spite of some recent improvements in constructing a plausible multilinear map [19, 20], these schemes are still far from being efficiently practical).


## 1.3. Organization

The next section discusses ECC andmKEM schemes and reviews the operation of dynamic GAKE protocols. In this section we also study the existingmKEM-based GAKE framework. In Section 3 we present our two variants ofmKEM-based GAKE model with forward secrecy. In Section 4 we propose a generic framework to convert this existing static GAKE framework to a partially dynamic scheme. Finally, in Section 5 we compare the implementation cost of this framework from the possible ECC translation of existingmKEM solutions. Section 6 gives a summary of our work and highlights the important points.


## 2. Preliminaries

### 2.1. Elliptic Curve

An elliptic curveE over the prime field of Fq(characteristic(Fq)≠2,3) is defined by a short Weierstrass equation E: y2=x3+ax+b, where the parameters a,b∈Fq are chosen such that Δ≠4a3+27b2 (Δ is the discriminant of the equation). The group of points of E over Fq is denoted by E(Fq) and the order of EFq is indicated by #EFq. An elliptic curve is described by set of parameters (q,a,b,P,p,h), where q specifies the finite field of Fq, a and b are coefficient of E, P=xP,yP is the generator of a cyclic subgroup of P⊂EFq of prime order p, and h=#EFq/p is the cofactor of elliptic curve. Elliptic curve DH assumptions are described as follows:(i)
A Diffie-Hellman (DH) tuple inG is (P,xP,yP,zP)∈G for some x,y,z∈Zq∗ satisfying z=xymod⁡q.(ii)
Computational Diffie-Hellman (CDH) problem: given any three elements from the four elements in a DH tuple compute the remaining element.(iii)
Decision Diffie-Hellman (DDH) problem: given P,xP,yP,zP∈G, decide if it is a valid DH tuple or not (if zP=xyP).(iv)
Hashed Decision Diffie-Hellman (HDDH) problem: given P,xP,yP∈G and h, decide if h=HxyP, where H is a target collision resistant Hash function.


### 2.2.mKEM

AnmKEM scheme allows a peer to efficiently encapsulate a single session key to n parties. A typical mKEM scheme is presented by (gm,Em,Dm) tuples and consists of three core algorithms: private/public-key generation (gm), key encapsulation (Em), and key decapsulation (Dm). The probabilistic algorithm of gm takes domain parameters and generates public/private-key pairs pki,ski. The probabilistic algorithm of Em takes set of public-keys pk={pk1,…,pkn} of receivers and returns the encapsulation pair (K,C), where C={c1,…,cn} and ci is encapsulation of K with pki. The deterministic algorithm of Dm takes private-key ski and the encapsulation C and outputs K. For a mKEM scheme to be secure it is required to be sound, which means, for all key pairs (pki,ski) generated by gm(γ) and all encapsulation pair (K,C) generated by Emγ,pk, we assume all possible range of K is generated by Dm(γ,C,ski).


### 2.3. Dynamic Group Key Exchange

The GKE algorithms are divided into two groups ofstatic and dynamic in terms of their capability to reform the session key with updated group membership. In static GKE the number of peers remains constant during the session whereas in dynamic GKE participants are allowed to join or leave the session at any time during the active session. A typical dynamic GKE consists of three algorithms, namely, shared-key establishment scheme,join operation, andleave operation. The shared-key establishment scheme operates the same as typical static GKE scheme and allows n parties to securely calculate confidential shared-key. The join operation allows new member to jointly establish new key with existing members in the way that the new member should not be able to extract the previously established session keys between those peers. The leave operation removes one of the members from the existing session and allows the remaining members to calculate a fresh key for the session. The leaving group members should be capable of calculating or distinguishing updated session key. Whilst it is possible to convert any static GKE to a dynamic GKE by reexecuting the static GKE with updated members, it is desirable for a GKE protocol to provide more efficient solution for join/leave operations rather than trivial approach of reexecuting the GKE scheme in dynamic environment.


### 2.4.mKEM-Based One-Round GAKE Construction (mkGAKE Model)

The generic model proposed by Gorantla et al. in [1] provides a framework to construct a one-round implicitly authenticated group key exchange (GAKE) from anmKEM scheme. Consider set of parties U={u1,…,un} as participants in the GAKE scheme, where ui∈1,n is the identity of a participant and U is set of identities of all parties. This generic model assumes an IND-CCA secure mKEM(gm,Em,Dm) as the core algorithm and is designed to let the members of U establish a shared session key through parallel execution mKEMgm,Em,Dm. SincemKEM guarantees to the sender that only the legitimate receiver can decapsulate the session key, this generic model constructed from parallel execution ofmKEM among multiple participants can provide all parties with implicit authentication on computed symmetric-key. This model consists of four phases as shown below:(i)
Initiation:(1)ui∈U:ski,pki⟵gmKEMD,pk=pk1,…,pknis  known  to  all  peers.(ii)
Computation:(2)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(iii)
Communication:(3)ui∈Ubroadcastsui,citoU∖ui.(iv)
Key calculation:(4)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.In theInitiation phase, each GAKE participant ui∈U executes gmKEMD to obtain private/public-key pairs of ski,pki, and authentic set of public-keys pk=pk1,…,pkn is known to all peers. In theComputation phase, each ui∈U executesmKEM encapsulation algorithm with other participants’ public-key to obtain the symmetric-key and encapsulation pair. In theCommunication phase each ui∈U broadcasts its computed encapsulation together with its id to all other peers. Finally, in theKey calculation phase each ui∈U executes themKEM decapsulation algorithm on each of the incoming encapsulations using its private-key to obtain n-1 number of the symmetric-keys. Then, set sid to be the concatenation of all the incoming and outgoing exchanged messages sid←(C1∥⋯∥Cn∥U), where U is the set of identities of all the users. Finally, sid and decapsulated keys are fed to a pseudorandom function to calculate the session key.


## 2.1. Elliptic Curve

An elliptic curveE over the prime field of Fq(characteristic(Fq)≠2,3) is defined by a short Weierstrass equation E: y2=x3+ax+b, where the parameters a,b∈Fq are chosen such that Δ≠4a3+27b2 (Δ is the discriminant of the equation). The group of points of E over Fq is denoted by E(Fq) and the order of EFq is indicated by #EFq. An elliptic curve is described by set of parameters (q,a,b,P,p,h), where q specifies the finite field of Fq, a and b are coefficient of E, P=xP,yP is the generator of a cyclic subgroup of P⊂EFq of prime order p, and h=#EFq/p is the cofactor of elliptic curve. Elliptic curve DH assumptions are described as follows:(i)
A Diffie-Hellman (DH) tuple inG is (P,xP,yP,zP)∈G for some x,y,z∈Zq∗ satisfying z=xymod⁡q.(ii)
Computational Diffie-Hellman (CDH) problem: given any three elements from the four elements in a DH tuple compute the remaining element.(iii)
Decision Diffie-Hellman (DDH) problem: given P,xP,yP,zP∈G, decide if it is a valid DH tuple or not (if zP=xyP).(iv)
Hashed Decision Diffie-Hellman (HDDH) problem: given P,xP,yP∈G and h, decide if h=HxyP, where H is a target collision resistant Hash function.


## 2.2.mKEM

AnmKEM scheme allows a peer to efficiently encapsulate a single session key to n parties. A typical mKEM scheme is presented by (gm,Em,Dm) tuples and consists of three core algorithms: private/public-key generation (gm), key encapsulation (Em), and key decapsulation (Dm). The probabilistic algorithm of gm takes domain parameters and generates public/private-key pairs pki,ski. The probabilistic algorithm of Em takes set of public-keys pk={pk1,…,pkn} of receivers and returns the encapsulation pair (K,C), where C={c1,…,cn} and ci is encapsulation of K with pki. The deterministic algorithm of Dm takes private-key ski and the encapsulation C and outputs K. For a mKEM scheme to be secure it is required to be sound, which means, for all key pairs (pki,ski) generated by gm(γ) and all encapsulation pair (K,C) generated by Emγ,pk, we assume all possible range of K is generated by Dm(γ,C,ski).


## 2.3. Dynamic Group Key Exchange

The GKE algorithms are divided into two groups ofstatic and dynamic in terms of their capability to reform the session key with updated group membership. In static GKE the number of peers remains constant during the session whereas in dynamic GKE participants are allowed to join or leave the session at any time during the active session. A typical dynamic GKE consists of three algorithms, namely, shared-key establishment scheme,join operation, andleave operation. The shared-key establishment scheme operates the same as typical static GKE scheme and allows n parties to securely calculate confidential shared-key. The join operation allows new member to jointly establish new key with existing members in the way that the new member should not be able to extract the previously established session keys between those peers. The leave operation removes one of the members from the existing session and allows the remaining members to calculate a fresh key for the session. The leaving group members should be capable of calculating or distinguishing updated session key. Whilst it is possible to convert any static GKE to a dynamic GKE by reexecuting the static GKE with updated members, it is desirable for a GKE protocol to provide more efficient solution for join/leave operations rather than trivial approach of reexecuting the GKE scheme in dynamic environment.


## 2.4.mKEM-Based One-Round GAKE Construction (mkGAKE Model)

The generic model proposed by Gorantla et al. in [1] provides a framework to construct a one-round implicitly authenticated group key exchange (GAKE) from anmKEM scheme. Consider set of parties U={u1,…,un} as participants in the GAKE scheme, where ui∈1,n is the identity of a participant and U is set of identities of all parties. This generic model assumes an IND-CCA secure mKEM(gm,Em,Dm) as the core algorithm and is designed to let the members of U establish a shared session key through parallel execution mKEMgm,Em,Dm. SincemKEM guarantees to the sender that only the legitimate receiver can decapsulate the session key, this generic model constructed from parallel execution ofmKEM among multiple participants can provide all parties with implicit authentication on computed symmetric-key. This model consists of four phases as shown below:(i)
Initiation:(1)ui∈U:ski,pki⟵gmKEMD,pk=pk1,…,pknis  known  to  all  peers.(ii)
Computation:(2)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(iii)
Communication:(3)ui∈Ubroadcastsui,citoU∖ui.(iv)
Key calculation:(4)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.In theInitiation phase, each GAKE participant ui∈U executes gmKEMD to obtain private/public-key pairs of ski,pki, and authentic set of public-keys pk=pk1,…,pkn is known to all peers. In theComputation phase, each ui∈U executesmKEM encapsulation algorithm with other participants’ public-key to obtain the symmetric-key and encapsulation pair. In theCommunication phase each ui∈U broadcasts its computed encapsulation together with its id to all other peers. Finally, in theKey calculation phase each ui∈U executes themKEM decapsulation algorithm on each of the incoming encapsulations using its private-key to obtain n-1 number of the symmetric-keys. Then, set sid to be the concatenation of all the incoming and outgoing exchanged messages sid←(C1∥⋯∥Cn∥U), where U is the set of identities of all the users. Finally, sid and decapsulated keys are fed to a pseudorandom function to calculate the session key.


## 3. Two-Round GAKE with Forward Secrecy

The generic one-roundmKEM-based framework cannot provide forward secrecy, but it can be extended to a two-round unauthenticated scheme to achieve this additional goal. In this approach, the authenticated and certified long-term private/public-key pairs are replaced with ephemeral key pairs. In the two-round variance, the participants execute the mKEM in parallel with on-demand generated ephemeral keys. Using ephemeral and uncertified asymmetric-keys will result in a GKE protocol without an implicit authentication property. In this case an adversary can impersonate any honest participant to other peers by replacing the ephemeral private/public values and resultant protocol is only secure in the presence of a passive adversary. To provide the GKE protocol with authentication, one of the two following approaches may be adopted.


### 3.1. Using Digital Signature in the First Round

In this approach the peerui∈U is assumed to hold a certified long-term private/public-key pair of SKi,PKi corresponding to the employed digital signature scheme. The signing/verification algorithms of the corresponding digital signature scheme are denoted by (Sign, Verify). The key exchange procedure is carried out in two rounds as shown below.Round 1. Peer ui runs the gmKEM function to obtain ephemeral private/public-key pair of ski,pki and then use SKi to compute the digital signature on pki. Then, ui broadcasts the signature together with its id and ephemeral public-key of pki to the other users. The generic framework for the first round interaction is shown below:(i)
Setup:(5)ui∈U:  obtainslong-term  signingverification  keys  ofSKi,PKi.The  verification  public-keysPK=PK1,…,PKnare  known  to  all  peers.(ii)
Initiation:(6)ui∈U:ski,pki⟵gmKEMD.(iii)
Signature:(7)ui∈U:σi⟵SignSKiui,pki.(iv)
Communication 1:(8)ui∈Ubroadcastsui,σi,pkitoU∖ui.Round 2. In the second round, other peers verify the authenticity of pki by validating the received signature using the publicly available certified verification key of PKi and then run the one-round protocol with authentic ephemeral public-keys. The generic framework for the second-round interaction of this approach is shown below:(i)
Verification:(9)For1≤j≠i≤npeerui∈UCheckVerifyPKjuj,pkj,σj=1.(ii)
Computation:(10)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(iii)
Communication 2:(11)ui∈Ubroadcastsui,citoU∖ui.(iv)
Key calculation:(12)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.


### 3.2. Using Digital Signature in the Second Round

A variant of this approach is (also) suggested in [21] and the core idea is originally borrowed from [22]. In this framework, peer ui∈U is assumed to have a pair of certified long-term signing/verification key pair of SKi,PKi corresponding to the employed digital signature scheme. The generic framework for the first-round interaction is shown below.Round 1. In the first round, peer ui runs the gmKEM function to obtain ephemeral private/public-key pair of ski,pki and broadcast it to other peers:(i)
Setup:(13)ui∈U:  obtainslong-term  signingverification  keys  ofSKi,PKi.The  verification  public-keysPK=PK1,…,PKnare  known  to  all  peers.(ii)
Initiation:(14)ui∈U:ski,pki⟵gmKEMD.(iii)
Communication:(15)ui∈UbroadcastspkitoU∖ui.Round 2. In the second round, each ui∈U executesmKEM encapsulation algorithm with other participants’ public-keys to obtain the symmetric-key and encapsulation pair. To provide the authentication property, ui uses SKi to compute digital signature on session key encapsulation Ci concatenated with ephemeral public-keys in the system and broadcast signature and Ci to other participants. Other peers verify the authenticity of received encapsulation of Ci (and corresponding embedded key) by validating the received signature using the publicly available certified verification key of PKi. After validating the authenticity of all received encapsulations, each peer extracts the embedded-keys by usingmKEM decapsulation algorithm and finally computes the shared session key. The generic framework for the second round interaction is shown below:(i)
Computation:(16)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(ii)
Signature:(17)ui∈U:σi⟵SignSKiCi∣pk1∣⋯∣pkn.(iii)
Communication:(18)ui∈Ubroadcastsui,σi,CitoU∖ui.(iv)
Verification:(19)For1≤j≠i≤npeerui∈UCheckVerifyPKjuj,Cj∣pk1∣⋯∣pkn,σj=1.(v)
Key calculation:(20)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.


### 3.3. Security Analysis

The provided security of both approaches relies on the security of the underlying digital signature scheme. Both approaches assume each peerui∈U possesses a certified long-term private/public-key pair of SKi,PKi corresponding to the employed digital signature scheme. The relevant private-key, which is tasked to sign either ephemeral public-key (first approach) or encapsulation of the session key (second approach), should be kept secret as revealing this key to a potential adversary would result in revealing the session key. If we assume the employed signature scheme is secure against existential forgery under an adaptive chosen message attack, and the corresponding signing private-keys are kept secret from potential adversaries, then we can conclude both approaches are forward-secure authenticated group key exchange schemes. In fact, both approaches use a hierarchy of signatures where the first authenticated exchange authenticates the next exchange.It should be noted that the ephemeral session keys are independent of the long-term keying materials, and the long-term keys are only tasked to authenticate the session key and not to take a role in the calculation of these keys. Thus, if an adversary manages to compromise a long-term keying material of any participating peers in a random session, he/she cannot reveal any information about the ephemeral keys of previous sessions in which the corrupted party has been participating in the past. However, the future session keys will not be secure against this adversary as he/she can fake the corrupted party and fool any other party(ies) to enter session key calculation phase with her/him. It should be noted that a forward-secure group key exchange is expected to keep the previous session keys unaccessible, not the future keys. Based on this notion, both of the described approaches are forward-secure key exchange schemes. Note that while the first approach (Section3.1) is basically simpler and more convenient, the second method (Section 3.2) is stronger as it provides mean of mutual authentication on all the session-related ephemeral values.


## 3.1. Using Digital Signature in the First Round

In this approach the peerui∈U is assumed to hold a certified long-term private/public-key pair of SKi,PKi corresponding to the employed digital signature scheme. The signing/verification algorithms of the corresponding digital signature scheme are denoted by (Sign, Verify). The key exchange procedure is carried out in two rounds as shown below.Round 1. Peer ui runs the gmKEM function to obtain ephemeral private/public-key pair of ski,pki and then use SKi to compute the digital signature on pki. Then, ui broadcasts the signature together with its id and ephemeral public-key of pki to the other users. The generic framework for the first round interaction is shown below:(i)
Setup:(5)ui∈U:  obtainslong-term  signingverification  keys  ofSKi,PKi.The  verification  public-keysPK=PK1,…,PKnare  known  to  all  peers.(ii)
Initiation:(6)ui∈U:ski,pki⟵gmKEMD.(iii)
Signature:(7)ui∈U:σi⟵SignSKiui,pki.(iv)
Communication 1:(8)ui∈Ubroadcastsui,σi,pkitoU∖ui.Round 2. In the second round, other peers verify the authenticity of pki by validating the received signature using the publicly available certified verification key of PKi and then run the one-round protocol with authentic ephemeral public-keys. The generic framework for the second-round interaction of this approach is shown below:(i)
Verification:(9)For1≤j≠i≤npeerui∈UCheckVerifyPKjuj,pkj,σj=1.(ii)
Computation:(10)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(iii)
Communication 2:(11)ui∈Ubroadcastsui,citoU∖ui.(iv)
Key calculation:(12)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.


## 3.2. Using Digital Signature in the Second Round

A variant of this approach is (also) suggested in [21] and the core idea is originally borrowed from [22]. In this framework, peer ui∈U is assumed to have a pair of certified long-term signing/verification key pair of SKi,PKi corresponding to the employed digital signature scheme. The generic framework for the first-round interaction is shown below.Round 1. In the first round, peer ui runs the gmKEM function to obtain ephemeral private/public-key pair of ski,pki and broadcast it to other peers:(i)
Setup:(13)ui∈U:  obtainslong-term  signingverification  keys  ofSKi,PKi.The  verification  public-keysPK=PK1,…,PKnare  known  to  all  peers.(ii)
Initiation:(14)ui∈U:ski,pki⟵gmKEMD.(iii)
Communication:(15)ui∈UbroadcastspkitoU∖ui.Round 2. In the second round, each ui∈U executesmKEM encapsulation algorithm with other participants’ public-keys to obtain the symmetric-key and encapsulation pair. To provide the authentication property, ui uses SKi to compute digital signature on session key encapsulation Ci concatenated with ephemeral public-keys in the system and broadcast signature and Ci to other participants. Other peers verify the authenticity of received encapsulation of Ci (and corresponding embedded key) by validating the received signature using the publicly available certified verification key of PKi. After validating the authenticity of all received encapsulations, each peer extracts the embedded-keys by usingmKEM decapsulation algorithm and finally computes the shared session key. The generic framework for the second round interaction is shown below:(i)
Computation:(16)ui∈U:Ki,Ci⟵EmKEMpkj∣pkj∈pk;1≤j≠i≤n.(ii)
Signature:(17)ui∈U:σi⟵SignSKiCi∣pk1∣⋯∣pkn.(iii)
Communication:(18)ui∈Ubroadcastsui,σi,CitoU∖ui.(iv)
Verification:(19)For1≤j≠i≤npeerui∈UCheckVerifyPKjuj,Cj∣pk1∣⋯∣pkn,σj=1.(v)
Key calculation:(20)ui∈Ucalculate  the  shared-key  as  followsKj1≤j≠i≤n⟵DmKEMski,Cj∣1≤j≠i≤n,sid⟵C1∥⋯∥Cn∥U,K⟵fK1sid⊕⋯⊕fKnsid.


## 3.3. Security Analysis

The provided security of both approaches relies on the security of the underlying digital signature scheme. Both approaches assume each peerui∈U possesses a certified long-term private/public-key pair of SKi,PKi corresponding to the employed digital signature scheme. The relevant private-key, which is tasked to sign either ephemeral public-key (first approach) or encapsulation of the session key (second approach), should be kept secret as revealing this key to a potential adversary would result in revealing the session key. If we assume the employed signature scheme is secure against existential forgery under an adaptive chosen message attack, and the corresponding signing private-keys are kept secret from potential adversaries, then we can conclude both approaches are forward-secure authenticated group key exchange schemes. In fact, both approaches use a hierarchy of signatures where the first authenticated exchange authenticates the next exchange.It should be noted that the ephemeral session keys are independent of the long-term keying materials, and the long-term keys are only tasked to authenticate the session key and not to take a role in the calculation of these keys. Thus, if an adversary manages to compromise a long-term keying material of any participating peers in a random session, he/she cannot reveal any information about the ephemeral keys of previous sessions in which the corrupted party has been participating in the past. However, the future session keys will not be secure against this adversary as he/she can fake the corrupted party and fool any other party(ies) to enter session key calculation phase with her/him. It should be noted that a forward-secure group key exchange is expected to keep the previous session keys unaccessible, not the future keys. Based on this notion, both of the described approaches are forward-secure key exchange schemes. Note that while the first approach (Section3.1) is basically simpler and more convenient, the second method (Section 3.2) is stronger as it provides mean of mutual authentication on all the session-related ephemeral values.


## 4. Achieving Dynamic Group Operation

While it is possible to construct a dynamic protocol from this GAKE model by reexecuting (from scratch) the scheme injoin or leave procedure, we propose a solution to perform the join operation more efficiently. The leave operation still requires the member to reexecute the protocol.Consider a scenario where a new memberuz, with knowledge of domain parameters D, KDF, and f, decides to join an ongoing session between U parties with the shared session key of KS. Peer uz is required to run the gmKEM(D) function to obtain the private/public-key pair skz,pkz. The members of U are required to have access to the certified public-key of uz. The members of U also should have access to a secure symmetric encryption algorithm denoted by E,D. To join the ongoing session, each of U members together with uz should follow the corresponding procedure as described below.Peer
u
z. This new member executes the one-round protocol with respect to U public-keys of pk={pk1,…,pkn}:(i)
Initiation:(21)skz,pkz⟵gmKEMD,pkzis  known  to  all  peers.(ii)
Computation:(22)uz:Kz,Cz⟵EmKEMpk1,…,pkn.(iii)
Communication:(23)uzbroadcastsuz,CztoU.(iv)
Key calculation:(24)uzcalculate  the  shared-key  as  followsKi1≤i≤n⟵DmKEMskz,Ci∣1≤i≤n,sid⟵C1∥⋯∥Cn∥C1∥⋯∥Cn∥Cz∥U∥uz,K⟵fK1sid⊕⋯⊕fKnsid⊕fKzsid.Peer
u
i
∈
U. Each member of U executes the one-round protocol with respect to uz public-key of pkz and use a symmetric encryption scheme with already established session key to distribute the new keys among themselves:(i)
Computation:(25)ui∈U:Ki,Ci⟵EmKEMpkz,Ci⟵EKsKi.(ii)
Communication:(26)ui∈Ubroadcastsui,Ci,CitoU∖ui∪uz.(iii)
Key calculation:(27)
u
i
∈
U
calculate  the  shared-key  as  follows
K
j
1
≤
j
≠
i
≤
n
⟵
D
K
s
C
i
∣
1
≤
j
≠
i
≤
n
,
K
z
⟵
D
m
K
E
M
s
k
i
,
C
z
,
sid
⟵
C
1
∥
⋯
∥
C
n
∥
C
1
∥
⋯
∥
C
n
∥
C
z
∥
U
∥
u
z
,
K
⟵
f
K
1
s
i
d
⊕
⋯
⊕
f
K
n
s
i
d
⊕
f
K
z
s
i
d
.It should be noted that in reexecuting the GAKE protocol from scratch each member needs to execute the associatedmKEM protocol with public-keys of all existing and new members. However, with the help of the proposed framework, each of existing members of U executes the associatedmKEM protocol, in the joining of new member(s), only with public-key(s) of that (those) member(s) and does not include the public-keys of other existing members U∖ui. Considering the expensive computational cost ofmKEM schemes which is dependent on the number of inputted public-keys, this framework can significantly reduce the associated computational overhead in dynamic group environments. While this construction results in better efficiency compared to rerunning the algorithm in joining a new member, the security of this scheme solely depends on the security of the employed symmetric encryption scheme and security of the genericmKEM-based GAKE model (Section 2.4). The joining new peer of uz executes themKEM-based GAKE model with the existing members; thus, the security of the calculated key with this node is the same as the generic framework. Furthermore, other nodes of ui∈U execute themKEM-based GAKE model with the new peer of uz and, in the meantime, distribute their ephemeral values among themselves through a CCA2 symmetric encryption scheme; thus, the security of calculated session key with these peers relies on the security of themKEM-based GAKE framework and employed symmetric encryption scheme, combined.


## 5. Efficiency Comparison of Instantiating GAKE Model from Different KEMs

In Table1 we compare the efficiency of instantiating themkGAKE model from existing provably securemKEM schemes. The table compares the computation cost of such constructions in terms of number of associated EC point scalar multiplications which is denoted by SM. The SM calculation refers to computing kP where k is an integer and P is an EC point. The multiscalar multiplication denoted by MSM refers to computing ∑kiPi. We found it easier and more consistent to represent the computational efficiency of different schemes by a single element of SM. However, since many factors contribute to computation of various MSM cases, then it is very difficult to precisely describe the computation cost of MSM in terms of calculation cost of SM. One approach to roughly estimate this relation, as described in [23], is by considering the unsigned binary representation of scalars and calculate MSM with a sliding window technique. An estimation from this approach is described in [24] and in windows size of 2 and bit-length of 256 it is assumed that one MSM calculation is roughly equal to 1.39 SM calculation. It should be noted that this optimistic estimation enables us to conveniently compare the computation efficiency of different EC-based schemes in a unified system.Table 1
Efficiency comparison of GAKE construction from differentmKEMs.
Scheme
Assumption
Initiation
Key exchange performance forn participants
SM
MSM
Key sizepk/sk
Computation
Key calculation
Total≈SM
Total KDF/Hash
SM
MSM
KDF/Hash
SM
MSM
KDF/Hash
PSEC [7]
CDH
1
—
2/1
n
—
n
+
1
/
—
2
n
-
2
—
2
n
-
2
/
—
3
n
-
2
3
n
-
1
/
—
ELGamal [5]
CDH
1
—
2/1
n
—
1
/
1
2
n
-
2
—
n
-
1
/
n
-
1
3
n
-
2
n
/
n
CS98 [8]
DDH
1
2
5/5
n
+
1
n
-
1
1
/
n
-
1
n
-
1
n
-
1
n
-
1
/
n
-
1
4.78
n
-
2.78
n
/
2
n
-
2
HK07 [9]
HDDH
3
—
4/3
2
n
-
1
—
/
1
—
n
-
1
—
/
n
-
1
2.78
n
-
0.78
—
/
n
HTAS-CKS [10]
HDDH
—
3
5/5
2
2
n
-
2
—
/
2
2
n
-
2
2
n
-
2
—
/
2
n
-
2
7.56
n
-
5.56
—
/
2
n
HTAS-HK [10]
HDDH
2
—
4/4
2
n
-
1
—
/
2
—
n
-
1
—
/
2
n
-
2
2.78
n
-
0.78
—
/
2
n


## 6. Conclusion

Through this contribution, we propose an efficient and practical generic framework to convert staticmKEM-based GAKE construction into a partially dynamic scheme. Our framework provides a more efficient solution for the join operation rather than the naive approach of reexecuting the original GAKE model with updated memberships. Furthermore, in order to enrich existingmKEM-based GAKE framework, we propose two variants of this generic model which can also provide a means of forward secrecy at the cost of an extra communication round. Finally, to evaluate the computational cost of deploying this generic model in elliptic curve cryptosystem, we compared the associated EC-related calculation cost of possible instantiations of this model from existingmKEM algorithms.



---

*Source: 275496-2015-09-16.xml*