# Certificateless Cross-Domain Group Authentication Key Agreement Scheme Based on ECC

Authors: Liling Cao; Mei Liang; Zheng Zhang; Shouqi Cao
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Focusing on the problem that existing traditional cross-domain group authentication schemes have a high complexity, a certificateless cross-domain group authentication key agreement scheme based on ECC is proposed. The protocol provides scalability and can meet the requirements of cross-domain key negotiation by multiple participants in different domains. Security analysis shows that the proposed scheme is secure in the random oracle security model, it can resist some attacks under the extended Canetti-Krawczyk (eCK) security model. Performance analysis shows that the proposed scheme is of strong practical application value with high efficiency; it costs relatively low amount of calculation and communication.


---

## Body

## 1. Introduction

The development of technologies such as wireless networks, multicast, and distributed computing has brought new demands for group-oriented network applications, such as multiparty video conferencing, remote video teaching, and online games. As a typical application scenario in the above applications, cross-domain group communication can realize information exchange and transmission between remote cross-domain group members and will provide users with richer services and maximize the use of resources. However, the increase in the size of group members and the heterogeneous network access caused by cross-domains have also brought new security challenges to the design of user identity authentication systems. A secure cross-domain group authentication key agreement protocol will establish a shared key for remote cross-domain group members, establish a secure cross-domain communication channel, ensure the confidentiality and integrity of cross-domain group communication data, and effectively prevents attackers from stealing, tampering, and forging communication data [1–4].The design of the existing cross-domain group authentication key agreement protocol mainly relies on three types of cryptosystems: public key infrastructure, identity-based cryptosystems, and certificateless public key cryptosystems.Public key infrastructure (PKI) is an important practical cryptographic technology to ensure network security. In PKI-based identity authentication, the certificate service system binds the digital certificate to the public key of the communicating entity, and the communicating entities verify the authenticity of the certificate to perform identity authentication. Wf et al. [5] adopted elliptic curve cryptosystem based on threshold scheme to construct enterprise cross-domain authentication system with the help of virtual bridge CA model. However, due to the high interaction cost caused by the threshold scheme by splitting key factors, the expansibility of joining and withdrawing members is not strong. Bin [6] improved the existing certificate revocation mechanism, but the certificate verification needs to detect from the book to be verified to the root certificate, so that the verification path is too long and the path verification efficiency is low, which greatly affects the application scope of the cross-domain identity authentication technology. Basin et al. proposed a new PKI architecture, ARPKI [7], which was designed by using formal models to ensure the transparency and reliability of certification-related operations (such as certificate issuance, update, revocation, and verification) and effectively deal with security events such as key loss or disclosure. Zhicheng et al. improved the traditional PKI-based cross-domain authentication by using the alliance chain technology [8] and used the alliance chain to manage the license domain, which simplified the authentication signature steps between entities and had high scalability. Dong et al. proposed a cross-domain authentication scheme that can enhance trust between hospitals [9], which solves the problem of fragmentation and isolation caused by traditional hospitals maintaining their own PKI-based information systems and provides better privacy protection services while realizing the sharing of medical data. Chen et al. used blockchain to replace part of CA functions [10]; the scheme has sufficient scalability and can meet the trust transmission requirements of multiple PKI systems. As the number of legitimate users increases, the calculation and communication overhead of the certificate maintenance process increases. Cross-domain identity authentication has problems such as long trust paths, low certificate verification efficiency, and complex interdomain trust path construction. It is not suitable for cross-domain identity authentication of large-scale group members.In identity-based cryptosystems, there is no need for PKI to verify users’ public keys and identities. Private key generator (PKG) is trusted to generate private keys for users, which can effectively solve the problems such as the overhead of public key certificate management [11]. Changyuan et al. [12] proposed an identity-based signature algorithm to achieve cross-domain authentication by using elliptic curve additive group, avoiding complex bilinear pairings. However, the scheme only analyzes the certification process between the entity and the certification authority and does not consider the extra cost of the certification authority and local resources to verify each other’s legitimacy. The identity-based authenticated key agreement protocol without bilinear pairs proposed by Farash and Attari [13] sets multiple independent PKG, and each PKG sets the private key for the user under its jurisdiction. However, this protocol cannot resist temporary key leakage attack and impersonation attack, and it cannot realize implicit key authentication and key confirmation. Cao et al. [14] proposed a key agreement protocol for identity-based authentication with hierarchical PKG, which uses bilinear pair operation in its design, but the operation is not efficient and it is difficult to resist basic impersonation attacks. Kefei et al. [15] proposed an improved scheme on the basis of the literature [14], but this scheme is difficult to resist the temporary key disclosure attacks, and the operation efficiency was low due to the use of bilinear pair operation in the scheme. Since the user’s private key is completely determined by the key generation center, PKG can decrypt any user’s information and forge any user’s signature. There are key escrowing problems, and user identity multiplicity occurs when cross-domain, making cross-domain identity authentication extremely complicated.Based on the certificateless public key cryptosystem, the user’s private key is composed of two parts, that is, the partial private key provided by KGC and the secret value selected by the user. Neither KGC nor the user can generate a complete private key independently, which solves the key escrow problem in the identity-based cryptosystem. Literature [16, 17] proposed a cloud user identity authentication scheme based on certificateless password system, but there was no relevant research on cross-domain authentication. Li et al. [18] proposed a cross-domain authentication key exchange protocol in a wireless grid environment, but the use of too much symmetric encryption causes a large amount of computational overhead. In 2015, Sun et al. [19] proposed a certificateless scheme, but it involves the calculation of linear pairs, so the amount of calculation is huge. In 2016, Cheng et al. [20] proposed a one-round certificateless authenticated group key agreement protocol for mobile ad hoc networks, but Luo et al. [21] indicated that their protocol could not achieve user anonymity that was an important aspect of user privacy protection and could not resist known temporary key attack. In 2018, Yang et al. [22] proposed a cross-domain certificateless key agreement protocol for electronic health systems. Although it achieved the security guarantees of dynamic user management, authentication, and session keys, it did not achieve the real cross-domain and could not resist known temporary key attack indicated by Luo et al. [21]. In 2018, Semal et al. [23] proposed a certificateless group authenticated key agreement protocol for secure communication in untrusted UAV networks, and in 2020, Luo et al. [21] proposed a cross-domain certificateless authenticated group key agreement protocol for 5G network slicings. However, in 2022, Ren et al. [24] indicated that the protocol proposed by Semal et al. could not resist public key replacement attack and protocol proposed by Luo only had a secondary security level; the malicious KGC could collude with some malicious users to attack the protocol.To sum up, the current cross-domain group communication solutions are mainly focused on the security issues of users’ cross-domain communication between two domains. Such solutions not only cannot meet the security requirements of users’ cross-domain group communication, but also the communication process is too cumbersome and requires relatively high communication capabilities and computing capabilities, so it cannot provide good guarantees for the security of cross-domain group communication. Therefore, an efficient and scalable key agreement scheme for cross-domain group authentication is urgently needed to solve and realize the communication security problem of efficient cross-domain group authentication. Focusing on the characteristics and requirements of the existing cross-domain group communication, this paper proposes a certificateless cross-domain group key agreement scheme based on ECC.


## 2. Preliminaries

### 2.1. Notation

The symbols and their meanings involved in the cross-domain group key negotiation scheme are shown in Table1.Table 1
Notation used in this paper.
NotationDescriptionUA collection of all cross-domain participantsDiTheith domainRAThe registryPpubPublic key of the systemKGCiKey generation center for domainDiSKi=ki,μiThe private key ofKGCiPKi=PpubiThe public key ofKGCiujiThejth participant of the ith domainDiIDjiThe identity ofujiskji=sji,xjiThe private key of the userujipkji=PjiThe public key of the userujiskiIntragroup key negotiated by the user of theith domain DiSKCross-domain group key⊥Represents no message or an unknown value


### 2.2. Security Model

In our proposed protocol, a novel eCK security model presented by Lippold et al. [25] is adopted. In the subsections, detailed descriptions about the security model including the adversary model, attack game, and security definition are explained.


#### 2.2.1. Adversary Model

There are two types of adversaries. As a dishonest participant, adversaryA1 has no idea of the master key of KGC but has the capability to replace the public key of any participant, which means A1 can replace the secret value xi of the participant with a value of his choice. As a malicious KGC, adversary A2 cannot replace the public key of any participant but can obtain the master key of KGC, which means si is easily accessible for A2.The security model is defined by an attack game between a challenger∁ and an adversary A∈A1,A2. The adversary asks the challenger for a polynomial number of queries, while the challenger issues the replies using simulators and random oracles owned by him. Let Πi,jm represent a simulator of the challenger, which simulates the behavior of participant i in the mth session with intended participant j. Then, simulated as participant i, the simulator Πi,jm executes all the steps that participant i should do in the protocol session. That is, the simulator Πi,jm takes private key of participant i and messages transmitted from participant j (or pseudo-j personated by the adversary) as inputs and sends the corresponding outputs to the adversary.Definition 1 (accepted session).
The sessionΠi,jm is accepted when it can generate the session key skijm.Definition 2 (session identity).
The session identity (sID) is denoted as the concatenation of the participants’ identities and messages in the session. For instance, sID∏i,jm=IDi,IDj,M1,M2, where M1 is the message transmitted from Πi,jm and M2 is the message received by Πi,jmDefinition 3 (matched session).
Honest participantsi and j are involved in the protocol session. The session Πi,jm matches Πj,in when they have the same session identity.


#### 2.2.2. Attack Game

Steps of the attack game are described as follows:(1)
The challenger∁ executes the SETUP algorithm:(1)s,systemparams⟵challengerSETUPkFor adversaryA1, the challenger ∁ sends system params to A1 but keeps s in secret. For adversary A2, the challenger ∁ sends system params and s to A2(2)
The adversary asks the challenger∁ for a polynomial number of the following queries:
(i)
CreateIDi: ∁ generates private key/public key pair ski,pki of participant i(ii)
Rsi: ∁ reveals to A the partial private key si of participant i(iii)
Rxi: ∁ reveals to A the secret value xi of participant i(iv)
Rti∏i,jm: ∁ reveals to A the ephemeral private key ti of participant i in the session Πi,jm(v)
Rs: ∁ reveals to A the master key of KGC. Then, A can obtain the partial private keys of all participants(vi)
Rpki: ∁ replaces the public key of participant i with the value chosen by A, which means that the secret values of all participants can be set by A(vii)
Rskij∏i,jm: ∁ reveals to A the accepted session key skij if Πi,jm is accepted. Otherwise, ∁ returns ⊥to A(viii)
Send (Πi,jm,M): A (pseudoparticipant j) sends the message M to the session Πi,jm (simulated participant i) and gets a reply according to the protocol. If M=⊥, simulated participant i of the session Πi,jm is an initiator. Otherwise, it is a responder(3)
When deciding to end aforementioned queries,A chooses a fresh session (defined later) Πi,jm and asks a test (Πi,jm) query. By tossing a fair coin with b∈0,1, ∁ replies the session key held by Πi,jm if b=1, or a random string if b=0(4)
The adversary asks the challenger∁ for a polynomial number of the above queries about fresh session Πi,jm(5)
When terminating the game,A makes a guess bit b′. If b′=b, A wins the game. The advantage of A for winning the game is defined as AdvAk=prb=b′−1/2Definition 4 (fresh session againstA1).
The accepted sessionΠi,jm is fresh if none of the following condition holds:
(i)
A1 raises the query RskijΠi,jm or RskjiΠj,in (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A1 either inquires both Rsi (or Rs) and RtiΠi,jm or both Rsj (or Rs) and RtjΠj,in(iii)
Not matching: if there is no session matched toΠi,jm, A1 either inquires both Rsi and RtiΠi,jm or Rsj (or Rs)Definition 5 (fresh session againstA2).
(i)
A2 raises the query Rskij∏i,jm or Rskji∏i,jn (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A2 either inquires both Rxi (or Rpki) and Rti∏i,jm or both Rxj (or Rpki) and Rtj∏i,jn(iii)
Not matching: if there is no session matched toΠi,jm, A2 either inquires both Rxi and Rti∏i,jm or Rxj (or Rpki)According to the adversary model stated in Section2.2.1, xi and si are deemed to be knowable for A1 and A2 by Rpki query and Rs query, respectively. Supposing that participant A and B want to establish a session key, the session is not fresh in seven cases for A1 and A2, respectively, which is shown in Table 2. Then, the fresh session can appear in seven cases for A1 and A2, respectively, as shown in Table 3. As a case of fresh sessions, type FI1′ can be regarded as FI1 and type FII1′ can be regarded as FII1.Table 2
Cases of not fresh session.
ConditionTypeQueriesKnownType I adversaryA1MatchingAI1RsA (or Rs)RtAxAxBAI2RsB (or Rs)RtBxAxBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RsARtAxAxBAI6RsB (or Rs)xAxBAI7RskA,B∏A,BmType II adversaryA2MatchingAI1RxA (or Rpki)RtAsAsBAI2RxB (or Rpki)RtBsAsBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RxARtAsAsBAI6RxB (or Rpki)sAsBAI7RskA,B∏A,BmTable 3
Cases of fresh session.
ConditionType I adversaryA1Type II adversaryA2TypeQueriesKnownTypeKnownQueriesMatchingFI1RsARsBxAxBFII1sAsBRxARxBFI2RtARtBxAxBFII2sAsBRtARtBFI3RsARtBxAxBFII3sAsBRxARtBFI4RtARsBxAxBFII4sAsBRtARxBFI1’RsxAxBFII1’sAsBRpkiNot matchingFI5RsAxAxBFII5sAsBRxAFI6RtAxAxBFII6sAsBRtA


#### 2.2.3. Security Definition

A certificateless cross-domain group key agreement protocol is deemed authenticated key agreement (AKA) secure if no adversary except the protocol participants can get the session key. Detailed and accurate definition is as follows.Definition 6.
A protocol is secure when the following set of conditions is assumed:(1)
In the presence of an adversaryA∈A1,A2, sessions Πi,jm and Πj,in always agree on the same session key that distributed uniformly at random(2)
For any adversaryA∈A1,A2, AdvAk is negligible


## 2.1. Notation

The symbols and their meanings involved in the cross-domain group key negotiation scheme are shown in Table1.Table 1
Notation used in this paper.
NotationDescriptionUA collection of all cross-domain participantsDiTheith domainRAThe registryPpubPublic key of the systemKGCiKey generation center for domainDiSKi=ki,μiThe private key ofKGCiPKi=PpubiThe public key ofKGCiujiThejth participant of the ith domainDiIDjiThe identity ofujiskji=sji,xjiThe private key of the userujipkji=PjiThe public key of the userujiskiIntragroup key negotiated by the user of theith domain DiSKCross-domain group key⊥Represents no message or an unknown value


## 2.2. Security Model

In our proposed protocol, a novel eCK security model presented by Lippold et al. [25] is adopted. In the subsections, detailed descriptions about the security model including the adversary model, attack game, and security definition are explained.


### 2.2.1. Adversary Model

There are two types of adversaries. As a dishonest participant, adversaryA1 has no idea of the master key of KGC but has the capability to replace the public key of any participant, which means A1 can replace the secret value xi of the participant with a value of his choice. As a malicious KGC, adversary A2 cannot replace the public key of any participant but can obtain the master key of KGC, which means si is easily accessible for A2.The security model is defined by an attack game between a challenger∁ and an adversary A∈A1,A2. The adversary asks the challenger for a polynomial number of queries, while the challenger issues the replies using simulators and random oracles owned by him. Let Πi,jm represent a simulator of the challenger, which simulates the behavior of participant i in the mth session with intended participant j. Then, simulated as participant i, the simulator Πi,jm executes all the steps that participant i should do in the protocol session. That is, the simulator Πi,jm takes private key of participant i and messages transmitted from participant j (or pseudo-j personated by the adversary) as inputs and sends the corresponding outputs to the adversary.Definition 1 (accepted session).
The sessionΠi,jm is accepted when it can generate the session key skijm.Definition 2 (session identity).
The session identity (sID) is denoted as the concatenation of the participants’ identities and messages in the session. For instance, sID∏i,jm=IDi,IDj,M1,M2, where M1 is the message transmitted from Πi,jm and M2 is the message received by Πi,jmDefinition 3 (matched session).
Honest participantsi and j are involved in the protocol session. The session Πi,jm matches Πj,in when they have the same session identity.


### 2.2.2. Attack Game

Steps of the attack game are described as follows:(1)
The challenger∁ executes the SETUP algorithm:(1)s,systemparams⟵challengerSETUPkFor adversaryA1, the challenger ∁ sends system params to A1 but keeps s in secret. For adversary A2, the challenger ∁ sends system params and s to A2(2)
The adversary asks the challenger∁ for a polynomial number of the following queries:
(i)
CreateIDi: ∁ generates private key/public key pair ski,pki of participant i(ii)
Rsi: ∁ reveals to A the partial private key si of participant i(iii)
Rxi: ∁ reveals to A the secret value xi of participant i(iv)
Rti∏i,jm: ∁ reveals to A the ephemeral private key ti of participant i in the session Πi,jm(v)
Rs: ∁ reveals to A the master key of KGC. Then, A can obtain the partial private keys of all participants(vi)
Rpki: ∁ replaces the public key of participant i with the value chosen by A, which means that the secret values of all participants can be set by A(vii)
Rskij∏i,jm: ∁ reveals to A the accepted session key skij if Πi,jm is accepted. Otherwise, ∁ returns ⊥to A(viii)
Send (Πi,jm,M): A (pseudoparticipant j) sends the message M to the session Πi,jm (simulated participant i) and gets a reply according to the protocol. If M=⊥, simulated participant i of the session Πi,jm is an initiator. Otherwise, it is a responder(3)
When deciding to end aforementioned queries,A chooses a fresh session (defined later) Πi,jm and asks a test (Πi,jm) query. By tossing a fair coin with b∈0,1, ∁ replies the session key held by Πi,jm if b=1, or a random string if b=0(4)
The adversary asks the challenger∁ for a polynomial number of the above queries about fresh session Πi,jm(5)
When terminating the game,A makes a guess bit b′. If b′=b, A wins the game. The advantage of A for winning the game is defined as AdvAk=prb=b′−1/2Definition 4 (fresh session againstA1).
The accepted sessionΠi,jm is fresh if none of the following condition holds:
(i)
A1 raises the query RskijΠi,jm or RskjiΠj,in (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A1 either inquires both Rsi (or Rs) and RtiΠi,jm or both Rsj (or Rs) and RtjΠj,in(iii)
Not matching: if there is no session matched toΠi,jm, A1 either inquires both Rsi and RtiΠi,jm or Rsj (or Rs)Definition 5 (fresh session againstA2).
(i)
A2 raises the query Rskij∏i,jm or Rskji∏i,jn (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A2 either inquires both Rxi (or Rpki) and Rti∏i,jm or both Rxj (or Rpki) and Rtj∏i,jn(iii)
Not matching: if there is no session matched toΠi,jm, A2 either inquires both Rxi and Rti∏i,jm or Rxj (or Rpki)According to the adversary model stated in Section2.2.1, xi and si are deemed to be knowable for A1 and A2 by Rpki query and Rs query, respectively. Supposing that participant A and B want to establish a session key, the session is not fresh in seven cases for A1 and A2, respectively, which is shown in Table 2. Then, the fresh session can appear in seven cases for A1 and A2, respectively, as shown in Table 3. As a case of fresh sessions, type FI1′ can be regarded as FI1 and type FII1′ can be regarded as FII1.Table 2
Cases of not fresh session.
ConditionTypeQueriesKnownType I adversaryA1MatchingAI1RsA (or Rs)RtAxAxBAI2RsB (or Rs)RtBxAxBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RsARtAxAxBAI6RsB (or Rs)xAxBAI7RskA,B∏A,BmType II adversaryA2MatchingAI1RxA (or Rpki)RtAsAsBAI2RxB (or Rpki)RtBsAsBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RxARtAsAsBAI6RxB (or Rpki)sAsBAI7RskA,B∏A,BmTable 3
Cases of fresh session.
ConditionType I adversaryA1Type II adversaryA2TypeQueriesKnownTypeKnownQueriesMatchingFI1RsARsBxAxBFII1sAsBRxARxBFI2RtARtBxAxBFII2sAsBRtARtBFI3RsARtBxAxBFII3sAsBRxARtBFI4RtARsBxAxBFII4sAsBRtARxBFI1’RsxAxBFII1’sAsBRpkiNot matchingFI5RsAxAxBFII5sAsBRxAFI6RtAxAxBFII6sAsBRtA


### 2.2.3. Security Definition

A certificateless cross-domain group key agreement protocol is deemed authenticated key agreement (AKA) secure if no adversary except the protocol participants can get the session key. Detailed and accurate definition is as follows.Definition 6.
A protocol is secure when the following set of conditions is assumed:(1)
In the presence of an adversaryA∈A1,A2, sessions Πi,jm and Πj,in always agree on the same session key that distributed uniformly at random(2)
For any adversaryA∈A1,A2, AdvAk is negligible


## 2.2.1. Adversary Model

There are two types of adversaries. As a dishonest participant, adversaryA1 has no idea of the master key of KGC but has the capability to replace the public key of any participant, which means A1 can replace the secret value xi of the participant with a value of his choice. As a malicious KGC, adversary A2 cannot replace the public key of any participant but can obtain the master key of KGC, which means si is easily accessible for A2.The security model is defined by an attack game between a challenger∁ and an adversary A∈A1,A2. The adversary asks the challenger for a polynomial number of queries, while the challenger issues the replies using simulators and random oracles owned by him. Let Πi,jm represent a simulator of the challenger, which simulates the behavior of participant i in the mth session with intended participant j. Then, simulated as participant i, the simulator Πi,jm executes all the steps that participant i should do in the protocol session. That is, the simulator Πi,jm takes private key of participant i and messages transmitted from participant j (or pseudo-j personated by the adversary) as inputs and sends the corresponding outputs to the adversary.Definition 1 (accepted session).
The sessionΠi,jm is accepted when it can generate the session key skijm.Definition 2 (session identity).
The session identity (sID) is denoted as the concatenation of the participants’ identities and messages in the session. For instance, sID∏i,jm=IDi,IDj,M1,M2, where M1 is the message transmitted from Πi,jm and M2 is the message received by Πi,jmDefinition 3 (matched session).
Honest participantsi and j are involved in the protocol session. The session Πi,jm matches Πj,in when they have the same session identity.


## 2.2.2. Attack Game

Steps of the attack game are described as follows:(1)
The challenger∁ executes the SETUP algorithm:(1)s,systemparams⟵challengerSETUPkFor adversaryA1, the challenger ∁ sends system params to A1 but keeps s in secret. For adversary A2, the challenger ∁ sends system params and s to A2(2)
The adversary asks the challenger∁ for a polynomial number of the following queries:
(i)
CreateIDi: ∁ generates private key/public key pair ski,pki of participant i(ii)
Rsi: ∁ reveals to A the partial private key si of participant i(iii)
Rxi: ∁ reveals to A the secret value xi of participant i(iv)
Rti∏i,jm: ∁ reveals to A the ephemeral private key ti of participant i in the session Πi,jm(v)
Rs: ∁ reveals to A the master key of KGC. Then, A can obtain the partial private keys of all participants(vi)
Rpki: ∁ replaces the public key of participant i with the value chosen by A, which means that the secret values of all participants can be set by A(vii)
Rskij∏i,jm: ∁ reveals to A the accepted session key skij if Πi,jm is accepted. Otherwise, ∁ returns ⊥to A(viii)
Send (Πi,jm,M): A (pseudoparticipant j) sends the message M to the session Πi,jm (simulated participant i) and gets a reply according to the protocol. If M=⊥, simulated participant i of the session Πi,jm is an initiator. Otherwise, it is a responder(3)
When deciding to end aforementioned queries,A chooses a fresh session (defined later) Πi,jm and asks a test (Πi,jm) query. By tossing a fair coin with b∈0,1, ∁ replies the session key held by Πi,jm if b=1, or a random string if b=0(4)
The adversary asks the challenger∁ for a polynomial number of the above queries about fresh session Πi,jm(5)
When terminating the game,A makes a guess bit b′. If b′=b, A wins the game. The advantage of A for winning the game is defined as AdvAk=prb=b′−1/2Definition 4 (fresh session againstA1).
The accepted sessionΠi,jm is fresh if none of the following condition holds:
(i)
A1 raises the query RskijΠi,jm or RskjiΠj,in (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A1 either inquires both Rsi (or Rs) and RtiΠi,jm or both Rsj (or Rs) and RtjΠj,in(iii)
Not matching: if there is no session matched toΠi,jm, A1 either inquires both Rsi and RtiΠi,jm or Rsj (or Rs)Definition 5 (fresh session againstA2).
(i)
A2 raises the query Rskij∏i,jm or Rskji∏i,jn (if the matched session Πj,in of Πi,jm exists)(ii)
Matching: if honest participantj is engaged in Πj,in that matches Πi,jm, A2 either inquires both Rxi (or Rpki) and Rti∏i,jm or both Rxj (or Rpki) and Rtj∏i,jn(iii)
Not matching: if there is no session matched toΠi,jm, A2 either inquires both Rxi and Rti∏i,jm or Rxj (or Rpki)According to the adversary model stated in Section2.2.1, xi and si are deemed to be knowable for A1 and A2 by Rpki query and Rs query, respectively. Supposing that participant A and B want to establish a session key, the session is not fresh in seven cases for A1 and A2, respectively, which is shown in Table 2. Then, the fresh session can appear in seven cases for A1 and A2, respectively, as shown in Table 3. As a case of fresh sessions, type FI1′ can be regarded as FI1 and type FII1′ can be regarded as FII1.Table 2
Cases of not fresh session.
ConditionTypeQueriesKnownType I adversaryA1MatchingAI1RsA (or Rs)RtAxAxBAI2RsB (or Rs)RtBxAxBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RsARtAxAxBAI6RsB (or Rs)xAxBAI7RskA,B∏A,BmType II adversaryA2MatchingAI1RxA (or Rpki)RtAsAsBAI2RxB (or Rpki)RtBsAsBAI3RskA,B∏A,BmAI4RskB,A∏B,AnNot matchingAI5RxARtAsAsBAI6RxB (or Rpki)sAsBAI7RskA,B∏A,BmTable 3
Cases of fresh session.
ConditionType I adversaryA1Type II adversaryA2TypeQueriesKnownTypeKnownQueriesMatchingFI1RsARsBxAxBFII1sAsBRxARxBFI2RtARtBxAxBFII2sAsBRtARtBFI3RsARtBxAxBFII3sAsBRxARtBFI4RtARsBxAxBFII4sAsBRtARxBFI1’RsxAxBFII1’sAsBRpkiNot matchingFI5RsAxAxBFII5sAsBRxAFI6RtAxAxBFII6sAsBRtA


## 2.2.3. Security Definition

A certificateless cross-domain group key agreement protocol is deemed authenticated key agreement (AKA) secure if no adversary except the protocol participants can get the session key. Detailed and accurate definition is as follows.Definition 6.
A protocol is secure when the following set of conditions is assumed:(1)
In the presence of an adversaryA∈A1,A2, sessions Πi,jm and Πj,in always agree on the same session key that distributed uniformly at random(2)
For any adversaryA∈A1,A2, AdvAk is negligible


## 3. Key Agreement Scheme for Cross-Domain Group Authentication

Figure1 shows the member structure of cross-domain group authentication in the scheme. Suppose there are n domains, each with m members participating in cross-domain authentication, where uji1≤i≤n,1≤j≤m represents any participant and let U=uji represent the collection of remote participants scattered across domains Di1≤i≤n that intend to negotiate a shared session key. Let the symbol Ui=u1i,u2i,⋯,umi represent the set of all participants in the same service domain Di. The protocol consists of two phases: intradomain key negotiation and interdomain key negotiation.Figure 1
The proposed group member structure of the cross-domain group authentication key agreement scheme.


### 3.1. System Initialization

This algorithm takes a security parameterk∈Zn∗ as input, and the RA performs the following steps to generate a master secret key s and a set of public parameter param.
(i)
RA generates a group with prime order p and determines a point P of order p as a generator of G(ii)
RA chooses a master secret key s∈Zn∗ and computes the corresponding public key Ppub=sP(iii)
RA chooses seven cryptographic secure hash functions: H1∗,H3∗,H4∗,H5∗,H6∗∈Zn∗, H2∗∈0,1k, and H7:0,1∗×0,1∗×⋯×0,1∗×Zn×Zn⟶Zn∗(iv)
RA publishes the system generated parameters Fp,EFp,G,P,Ppub,n,H1,H2,H3,H4,H5,H6,H7 while keeping the master key (s) secret


### 3.2. Registration Phase

The registration phase consists ofKGCi registration and user registration.


#### 3.2.1.KGCi registration

WhenKGCi applies to RA as the key generation center of domain Di, it needs to register with RA. The algorithm is as follows:
(1)
Set secret value:KGCi randomly chooses μi∈Zq∗, calculates Ppubi=μi⋅P, and sets μi as a secret value(2)
Extract partial private key: key generation centerKGCi sends identity information IDi to RA, and RA picks a random number λi∈Zn∗ for KGCi; calculates Wi=λi⋅P, li=H3IDi,Wi,Ppubi, and ki=λi+li⋅smodn; and issues ki,Wi to KGCi by secure channel(3)
Set private key:KGCi sets SKi=ki,μi as his private key(4)
Set public key:KGCi sets PKi=Ppubi=μi⋅P as his public key


#### 3.2.2. User Registration

When useruji applies to KGCi for joining the domain as the jth member, the registration needs to be completed at KGCi. The algorithm is as follows:
(1)
Set secret value:uji randomly chooses xj∈Zn∗, calculates Pji=xji⋅P, and sets xj as a secret value(2)
Extract partial private key: useruji sends identity information IDji to KGCi, and KGCi picks a random number rj∈Zn∗ for uji; calculates Rj=rj⋅P, hj=H3IDji,Rj,Pji, and sji=rj+hj⋅μimodn; and issues sji,Rj to uji by secure channel(3)
Set private key:uji sets skji=sji,xji as his private key(4)
Set public key:uji sets pkji=Pji=xji⋅P as his public key


### 3.3. Intradomain Key Negotiation

As shown in Figure2, in the key negotiation phases of intradomain, all participants in set U negotiate the session key of the intradomain group (no negotiation is required if there is only one user in the domain). Pick a participant randomly from all participants in domain Di as the domain head Hi. If user umi is selected as domain header Hi, users of domain Di are classified into common user uji1≤j≤m−1 and domain header umi.
(1)
By exchanging messages with domain headerumi, each common user uji1≤j≤m−1 proves that they are legitimate members of the same domain DiFigure 2
Key negotiation phases of intradomain.Step 1:uji randomly chooses tj,aj∈Zn∗ and calculates Tj=tjP and then sends message M1=IDji,Tj,Rj to umi.Step2:umi randomly chooses tm,am∈Zn∗ and calculates Tm=tmP and then sends message M2=IDmi,Tm,Rm to uji.Step 3:uji calculates kjm=H3IDji,Tj,Pjtj+sj+xj⋅H3IDmi,Tm,PmTm+Rm+H3IDmi,Tm,PmPpubi+Pm and kbj=aj⋅P and then sends the signature message σj=kbj,kjm to umi.Step 4:umi calculates kmj=H3IDmi,Tm,Pmtm+sm+xm⋅H3IDji,Tj,PjTj+Rj+H3IDji,Tj,PjPpubi+Pj. If kmj=kjm, uji is a legitimate member of domain Di.
(2)
Domain headerumi calculates the session key ski of domain Di based on the information received from the negotiation members and sends it to the negotiation members in encrypted form. The legitimate members who in the domain can calculate the session keyStep 1: At first,umi calculates kbm=am⋅P, skjm=H2IDjiIDmiTjTmkjm, qm=H4xmismi, bmj=H1IDjiIDmiam⋅kbj⊕qm, dm=xm+sm⋅H1IDjiIDmiqm⋅P, zam=am+dm⋅bmj, hm=H5kbm,qm, fm=H6sk1m+sk2m+⋯+skm−1m+amxmP, and keyj=H5am⋅kbj,qm⊕fm, then calculates the session key ski=H7ID1iID2i⋯IDmifmhm of domain Di, and finally sends ID1i,ID2i,⋯,IDmi,keyj,hm,σm to uji.Step 2:uji receives the message ID1i,ID2i,⋯,IDmi,keyj,hm,σm sent by umi and then calculates q′m=bmj⊕H1IDjiIDmiaj⋅kbm and k′bm=zam⋅P−bmjPmi+Rm+H3IDmi,Rm,PmiPpubi⋅H1IDjiIDmiq′m⋅P. If H5k′bm,q′m=hm, uji calculates f′m=keyj⊕H5k′bm⋅aj,q′m. Finally, the intradomain session key ski=H7ID1iID2i⋯IDmif′mhm=H7ID1iID2i⋯IDmifmhm of the domain Di is calculated.


### 3.4. Interdomain Key Negotiation

As shown in Figure3, in the key negotiation phase of interdomain, remote participants scattered in each domain Di1≤i≤n who intend to negotiate the shared session key randomly choose user umi1≤i≤n as domain head Hi in their respective domains, and the key negotiation between domain heads is carried out. Assume that the domain header is divided into Hiumi,1≤i≤n−1 and Hnumn, and the process of interdomain key negotiation is as follows:
(1)
To prove that domain headsHi1≤i≤n−1 and domain head Hn are legitimate members of the same system, they should send messages to each otherFigure 3
Key negotiation phase of interdomain.Step 1:Hi randomly chooses ti,bi∈Zn∗ and calculates Tj=tjP and then sends message M1=IDji,Tj,Rj to umi.Step2:umi randomly chooses tm,am∈Zn∗ and calculates Tm=tmP and then sends message M2=IDmi,Tm,Rm to uji.Step 3:Hi calculates Kin=H3IDmi,Ti,Pmiti+smi+xmi⋅H3IDmn,Tn,PmnTn+Rn+H3IDmn,Tn,PmnPpub+Pmn and Kbi=bi⋅P and then sends the signature message σi=Kbi,Kin to Hn.Step 4:Hn calculates Kni=H3IDmn,Ti,Pmnti+smn+xmn⋅H3IDmi,Tn,PmiTn+Rn+H3IDmi,Tn,PmiPpub+Pmi. If Kni=Kin, Hiumi,1≤i≤n−1 and Hnumn are legitimate members of the same system.
(2)
Domain headHn calculates the interdomain session key SK for interdomain negotiation based on the information received from domain head member Hiumi,1≤i≤n−1 that participates in the negotiation in each domain and sends the key SK to other members in the negotiation in encrypted form. Legitimate members who in the system can calculate the interzone session keyStep 1: At first,Hn calculates Kbn=bn⋅P, SKin=H2IDmiIDmnTiTnKin, Qn=H4xmnsmn, Bni=H1IDmiIDmnbn⋅Kbi⊕Qn, Dn=xmn+smn⋅H1IDmiIDmnQn⋅P, Zan=bn+Dn⋅Bni, Hn=H5Kbn,Qn, Fn=H6SK1n+SK2n+⋯+SKn−1n+bnxmnP, and KEYi=H5bn⋅Kbi,Qn⊕Fn, then calculates the interdomain session key SK=H7IDm1IDm2⋯IDmnFnhn, and finally sends IDm1,IDm2,⋯,IDmn,KEYi,Hn,σn to Hi.Step 2:Hi receives the message IDm1,IDm2,⋯,IDmn,KEYi,Hn,σn sent by Hn and then calculates Q′n=Bni⊕H1IDmiIDmnbi⋅Kbn and K′bn=Zan⋅P−BniPmn+Rn+H3IDmn,Rm,PmnPpub⋅H1IDmiIDmnQ′n⋅P. If H5K′bn,Q′n=Hn, Hi calculates F′n=KEYi⊕H5K′bn⋅bi,Q′n. Finally, the interdomain session key SK=H7IDm1IDm2⋯IDmnF′nHn=H7IDm1IDm2⋯IDmnFnhn is calculated.


### 3.5. Join Phase

Assume that userum+1 wants to join the protocol, obtains the system parameters of KGCi, generates its own public key pkji=Pji=xji⋅P and private key skji=sji,xji, and performs the key negotiation again. The procedure is the same as steps (1) to (2) in intradomain key negotiation.


### 3.6. Removal Phase

(1)
If the domain head leave, the remaining members will reselect a computationally powerful member as the domain head, and intradomain key negotiation and interdomain key negotiation are restarted. Perform steps (1) to (2) in intradomain key negotiation, and perform steps (1) to (2) in interdomain key negotiation(2)
If it is a common intradomain member that leaves, the intradomain member initiates key negotiation again. The procedure is the same as steps (1) to (2) in intradomain key negotiation


## 3.1. System Initialization

This algorithm takes a security parameterk∈Zn∗ as input, and the RA performs the following steps to generate a master secret key s and a set of public parameter param.
(i)
RA generates a group with prime order p and determines a point P of order p as a generator of G(ii)
RA chooses a master secret key s∈Zn∗ and computes the corresponding public key Ppub=sP(iii)
RA chooses seven cryptographic secure hash functions: H1∗,H3∗,H4∗,H5∗,H6∗∈Zn∗, H2∗∈0,1k, and H7:0,1∗×0,1∗×⋯×0,1∗×Zn×Zn⟶Zn∗(iv)
RA publishes the system generated parameters Fp,EFp,G,P,Ppub,n,H1,H2,H3,H4,H5,H6,H7 while keeping the master key (s) secret


## 3.2. Registration Phase

The registration phase consists ofKGCi registration and user registration.


### 3.2.1.KGCi registration

WhenKGCi applies to RA as the key generation center of domain Di, it needs to register with RA. The algorithm is as follows:
(1)
Set secret value:KGCi randomly chooses μi∈Zq∗, calculates Ppubi=μi⋅P, and sets μi as a secret value(2)
Extract partial private key: key generation centerKGCi sends identity information IDi to RA, and RA picks a random number λi∈Zn∗ for KGCi; calculates Wi=λi⋅P, li=H3IDi,Wi,Ppubi, and ki=λi+li⋅smodn; and issues ki,Wi to KGCi by secure channel(3)
Set private key:KGCi sets SKi=ki,μi as his private key(4)
Set public key:KGCi sets PKi=Ppubi=μi⋅P as his public key


### 3.2.2. User Registration

When useruji applies to KGCi for joining the domain as the jth member, the registration needs to be completed at KGCi. The algorithm is as follows:
(1)
Set secret value:uji randomly chooses xj∈Zn∗, calculates Pji=xji⋅P, and sets xj as a secret value(2)
Extract partial private key: useruji sends identity information IDji to KGCi, and KGCi picks a random number rj∈Zn∗ for uji; calculates Rj=rj⋅P, hj=H3IDji,Rj,Pji, and sji=rj+hj⋅μimodn; and issues sji,Rj to uji by secure channel(3)
Set private key:uji sets skji=sji,xji as his private key(4)
Set public key:uji sets pkji=Pji=xji⋅P as his public key


## 3.2.1.KGCi registration

WhenKGCi applies to RA as the key generation center of domain Di, it needs to register with RA. The algorithm is as follows:
(1)
Set secret value:KGCi randomly chooses μi∈Zq∗, calculates Ppubi=μi⋅P, and sets μi as a secret value(2)
Extract partial private key: key generation centerKGCi sends identity information IDi to RA, and RA picks a random number λi∈Zn∗ for KGCi; calculates Wi=λi⋅P, li=H3IDi,Wi,Ppubi, and ki=λi+li⋅smodn; and issues ki,Wi to KGCi by secure channel(3)
Set private key:KGCi sets SKi=ki,μi as his private key(4)
Set public key:KGCi sets PKi=Ppubi=μi⋅P as his public key


## 3.2.2. User Registration

When useruji applies to KGCi for joining the domain as the jth member, the registration needs to be completed at KGCi. The algorithm is as follows:
(1)
Set secret value:uji randomly chooses xj∈Zn∗, calculates Pji=xji⋅P, and sets xj as a secret value(2)
Extract partial private key: useruji sends identity information IDji to KGCi, and KGCi picks a random number rj∈Zn∗ for uji; calculates Rj=rj⋅P, hj=H3IDji,Rj,Pji, and sji=rj+hj⋅μimodn; and issues sji,Rj to uji by secure channel(3)
Set private key:uji sets skji=sji,xji as his private key(4)
Set public key:uji sets pkji=Pji=xji⋅P as his public key


## 3.3. Intradomain Key Negotiation

As shown in Figure2, in the key negotiation phases of intradomain, all participants in set U negotiate the session key of the intradomain group (no negotiation is required if there is only one user in the domain). Pick a participant randomly from all participants in domain Di as the domain head Hi. If user umi is selected as domain header Hi, users of domain Di are classified into common user uji1≤j≤m−1 and domain header umi.
(1)
By exchanging messages with domain headerumi, each common user uji1≤j≤m−1 proves that they are legitimate members of the same domain DiFigure 2
Key negotiation phases of intradomain.Step 1:uji randomly chooses tj,aj∈Zn∗ and calculates Tj=tjP and then sends message M1=IDji,Tj,Rj to umi.Step2:umi randomly chooses tm,am∈Zn∗ and calculates Tm=tmP and then sends message M2=IDmi,Tm,Rm to uji.Step 3:uji calculates kjm=H3IDji,Tj,Pjtj+sj+xj⋅H3IDmi,Tm,PmTm+Rm+H3IDmi,Tm,PmPpubi+Pm and kbj=aj⋅P and then sends the signature message σj=kbj,kjm to umi.Step 4:umi calculates kmj=H3IDmi,Tm,Pmtm+sm+xm⋅H3IDji,Tj,PjTj+Rj+H3IDji,Tj,PjPpubi+Pj. If kmj=kjm, uji is a legitimate member of domain Di.
(2)
Domain headerumi calculates the session key ski of domain Di based on the information received from the negotiation members and sends it to the negotiation members in encrypted form. The legitimate members who in the domain can calculate the session keyStep 1: At first,umi calculates kbm=am⋅P, skjm=H2IDjiIDmiTjTmkjm, qm=H4xmismi, bmj=H1IDjiIDmiam⋅kbj⊕qm, dm=xm+sm⋅H1IDjiIDmiqm⋅P, zam=am+dm⋅bmj, hm=H5kbm,qm, fm=H6sk1m+sk2m+⋯+skm−1m+amxmP, and keyj=H5am⋅kbj,qm⊕fm, then calculates the session key ski=H7ID1iID2i⋯IDmifmhm of domain Di, and finally sends ID1i,ID2i,⋯,IDmi,keyj,hm,σm to uji.Step 2:uji receives the message ID1i,ID2i,⋯,IDmi,keyj,hm,σm sent by umi and then calculates q′m=bmj⊕H1IDjiIDmiaj⋅kbm and k′bm=zam⋅P−bmjPmi+Rm+H3IDmi,Rm,PmiPpubi⋅H1IDjiIDmiq′m⋅P. If H5k′bm,q′m=hm, uji calculates f′m=keyj⊕H5k′bm⋅aj,q′m. Finally, the intradomain session key ski=H7ID1iID2i⋯IDmif′mhm=H7ID1iID2i⋯IDmifmhm of the domain Di is calculated.


## 3.4. Interdomain Key Negotiation

As shown in Figure3, in the key negotiation phase of interdomain, remote participants scattered in each domain Di1≤i≤n who intend to negotiate the shared session key randomly choose user umi1≤i≤n as domain head Hi in their respective domains, and the key negotiation between domain heads is carried out. Assume that the domain header is divided into Hiumi,1≤i≤n−1 and Hnumn, and the process of interdomain key negotiation is as follows:
(1)
To prove that domain headsHi1≤i≤n−1 and domain head Hn are legitimate members of the same system, they should send messages to each otherFigure 3
Key negotiation phase of interdomain.Step 1:Hi randomly chooses ti,bi∈Zn∗ and calculates Tj=tjP and then sends message M1=IDji,Tj,Rj to umi.Step2:umi randomly chooses tm,am∈Zn∗ and calculates Tm=tmP and then sends message M2=IDmi,Tm,Rm to uji.Step 3:Hi calculates Kin=H3IDmi,Ti,Pmiti+smi+xmi⋅H3IDmn,Tn,PmnTn+Rn+H3IDmn,Tn,PmnPpub+Pmn and Kbi=bi⋅P and then sends the signature message σi=Kbi,Kin to Hn.Step 4:Hn calculates Kni=H3IDmn,Ti,Pmnti+smn+xmn⋅H3IDmi,Tn,PmiTn+Rn+H3IDmi,Tn,PmiPpub+Pmi. If Kni=Kin, Hiumi,1≤i≤n−1 and Hnumn are legitimate members of the same system.
(2)
Domain headHn calculates the interdomain session key SK for interdomain negotiation based on the information received from domain head member Hiumi,1≤i≤n−1 that participates in the negotiation in each domain and sends the key SK to other members in the negotiation in encrypted form. Legitimate members who in the system can calculate the interzone session keyStep 1: At first,Hn calculates Kbn=bn⋅P, SKin=H2IDmiIDmnTiTnKin, Qn=H4xmnsmn, Bni=H1IDmiIDmnbn⋅Kbi⊕Qn, Dn=xmn+smn⋅H1IDmiIDmnQn⋅P, Zan=bn+Dn⋅Bni, Hn=H5Kbn,Qn, Fn=H6SK1n+SK2n+⋯+SKn−1n+bnxmnP, and KEYi=H5bn⋅Kbi,Qn⊕Fn, then calculates the interdomain session key SK=H7IDm1IDm2⋯IDmnFnhn, and finally sends IDm1,IDm2,⋯,IDmn,KEYi,Hn,σn to Hi.Step 2:Hi receives the message IDm1,IDm2,⋯,IDmn,KEYi,Hn,σn sent by Hn and then calculates Q′n=Bni⊕H1IDmiIDmnbi⋅Kbn and K′bn=Zan⋅P−BniPmn+Rn+H3IDmn,Rm,PmnPpub⋅H1IDmiIDmnQ′n⋅P. If H5K′bn,Q′n=Hn, Hi calculates F′n=KEYi⊕H5K′bn⋅bi,Q′n. Finally, the interdomain session key SK=H7IDm1IDm2⋯IDmnF′nHn=H7IDm1IDm2⋯IDmnFnhn is calculated.


## 3.5. Join Phase

Assume that userum+1 wants to join the protocol, obtains the system parameters of KGCi, generates its own public key pkji=Pji=xji⋅P and private key skji=sji,xji, and performs the key negotiation again. The procedure is the same as steps (1) to (2) in intradomain key negotiation.


## 3.6. Removal Phase

(1)
If the domain head leave, the remaining members will reselect a computationally powerful member as the domain head, and intradomain key negotiation and interdomain key negotiation are restarted. Perform steps (1) to (2) in intradomain key negotiation, and perform steps (1) to (2) in interdomain key negotiation(2)
If it is a common intradomain member that leaves, the intradomain member initiates key negotiation again. The procedure is the same as steps (1) to (2) in intradomain key negotiation


## 4. Security Analysis

Take intradomain key negotiation as an example. The intradomain session key isski=H7ID1iID2i⋯IDmifmhm, where fm=H6sk1m+sk2m+⋯+skm−1m+amxmiP. Hence, we can prove the security of the protocol by proving the security of skjm1≤j≤m−1.For ease of understanding, the negotiation process ofskjm in the protocol is assumed to be the negotiation process of A and B in domain Di to generate skAB.SupposeH1∗, H2∗, and H3∗ are treated as random oracles owned by ∁. RDDHaP,bP,cP is a DDH oracle, which outputs 1 if abP=cP, otherwise 0. Assume that A makes at most qi queries to Hi(2≤i≤3), qcqueriestoCreateIDi, qsi queries to RsiIDi, qx queries to RxiIDi, qt queries to RtiΠi,jf, qsk queries to RskijΠi,jf, qsd queries to SendΠi,jf,M, qs queries to Rs, qpki queries to Rpkixi′, and qrddh queries to RDDHaP,bP,cP. Assume also that bounded running time of query Hi (0≤i≤3) is ti, CreateIDi is tc, RsiIDi is tsi, RxiIDi is tx, RtiΠi,jf is tt, RskijΠi,jf is tsk, SendΠi,jf,M is tsd, Rs is ts, Rpkixi′ is tpki, and RDDH is trddh.The challenger∁ maintains the query lists as follows:LRH3−1: a tuple of (IDi,Ri,Pi,hi)LRH2: a tuple of IDi,IDj,TiΠi,jm,TjΠj,in,Kij,h2ijLRH3−2: a tuple of IDi,Ti,Pi,hTPiLC: a tuple of IDi,si,xi,Pi,RiLt(Πi,jf): a tuple of (Πi,jf,ti,Ti)Given an instance of the GDH problem, for unknownA,B∈Zn∗, by giving P,AP,BP,P∈E/Fq and an oracle DDH, compute CP=ABP.Lemma 7.
SupposeA1 win the game in case FI1 with advantage ε and running time t, with the help of A1; an algorithm Γ can be constructed to solve the above instance of the GDH problem with advantage ε′ and running time τ by interacting with A1.
(2)ε′=4qcqsdqtqc−1qt−1∙ε,τ≤∑i=23qiti+qctc+qsts+qttt+qsktsk+qsdtsd+qsts+qpkitpki+qrddhtrddh+t+tCP.Proof.
To interact withA1, a GDH slover Γ simulates as ∁ and runs the following steps to solve the above instance of the GDH problem with the help of A1:
(C1)Γ executes the SETUP algorithm and sends system params to A1.
(C2) Suppose thatA1 will choose ΠA,Bm for challenge in the next step. A1 asks the Γ for a polynomial number of the queries.
CreateIDi: on receiving IDi, Γ performs as follows:
(1)
IfLC contains a tuple of IDi,si,xi,Pi,Ri, Γ returns all the elements of the tuple to A1(2)
Otherwise,Γ randomly chooses xi,si,hi and then computes Pi=xiP and Ri=siP−hiPpub; Γ inserts IDi,si,xi,Pi,Ri to LC and (IDi,Ri,Pi,hi) to LRH3−1 and returns IDi,si,xi,Pi,Ri to A1
All the following queries should be asked afterCreateIDi.
H3−1query: on receiving IDi,Ri,Pi, after query CreateIDi, there must be a tuple of (IDi,Ri,Pi,hi) in LRH3−1; Γ returns hi to A1.
H3−2query: on receiving IDi,Ti,Pi, if LRH3−2 contains a tuple of IDi,Ti,Pi,hTPi, Γ returns hTPi to A1. Otherwise, Γ randomly chooses hTPi that has not been chosen by Γ and inserts IDi,Ti,Pi,hTPi to LRH3−2 and returns hTPi to A1.
RsiIDi: on receiving IDi, Γ returns si to A1 from LC.
RxiIDi: on receiving IDi, Γ returns xi to A1 from LC.
Rs: Γ returns ⊥ to A1.
Rpkixi′: on receiving xi′, Γ computes Pi′=xi′P and updates all the tuples with xi=xi′, Pi=Pi′
RtiΠi,jf:
(1)
Ifi=A, j=B, f=m or i=B, j=A, and f=n(a)
Ifi=A, j=B, and f=m, Γ sets TA=AP, inserts ΠA,Bm,⊥,AP to LtΠi,jf, and returns TA=AP to A1(b)
Ifi=B, j=A, andf=n, Γ sets TB=BP, inserts ΠB,An,⊥,BP to LtΠi,jf, and returns TB=BP to A1(2)
Otherwise,(a)
ifLt(Πi,jf) contains a tuple of (Πi,jf,ti,Ti), Γ returns ti,Tito A1(b)
Γ randomly chooses ti, computes Ti=tiP, inserts Πi,jf,ti,Ti to LtΠi,jf, and returns ti,Ti to A1
SendΠi,jf,M: If the matched session Πj,in of Πi,jm exists, this query should be asked after CreateIDi and RtiΠi,jf when A1 gets Ti and Ri.
(1)
A1 gets IDi,Ti,Ri from LC and LtΠi,jf and sets M=IDi,Ti,Ri, and Γ returns IDj,Tj,Rj from LC and Lt(Πi,jf). That is, A1 initiates the session Πi,jm with message IDi,Ti,Ri and gets respond with IDj,Tj,Rj of the matched session Πj,in(2)
IfM=⊥, Γ gets Ti, Tj, Ri, and Rj from LC and LtΠi,jf and initiates the session Πi,jm with IDi,Ti,Ri. Then, A1 gets IDj,Tj,Rj from Γ as the message of the matched session Πj,in
H2query: on receiving IDi,IDj,TiΠi,jm,TjΠj,in,Kij,⊥(1)
IfLRH2 contains a tuple of IDi,IDj,TiΠi,jm,TjΠj,in,Kij,h2ij, Γ returns h2ij to A1(2)
Otherwise,Γ randomly chooses h2ij that has not been chosen by Γ and inserts IDi,IDj,TiΠi,jm,TjΠj,in,Kij,h2ij to LRH2 and returns h2ij to A1
RskijΠi,jm/RskjiΠj,in:
(1)
Ifi≠A and j≠B, Γ gets Kij from LRH2; gets si, sj, xi, xj, ti, tj, hTPi, and hTPj from LC, LtΠi,jf, and LRH3−2; computes Kij∗=hTPihTPjtitjP+hTPitisjP+hTPitixjP+hTPjsitjP+sisjP+sixjP+hTPjxitjP+xisjP+xixjP; and checks whether Kij=Kij∗ or not. If they are equal, Γ returns h2ij from LRH2. Otherwise, Γ sets Kij=Kij∗, randomly chooses h2ij that has not been chosen by Γ and inserts IDi,IDj,TiΠi,jm,TjΠj,in,Kij,h2ij to LRH2, and returns h2ij to A1(2)
Otherwise,Γ returns ⊥ to A1
(C3)A1 asks a test (ΠA,Bm) query; the challenger ∁ performs as follows:
(1)
∁gets sA, sB, xA, xB, TA, TB, hTPA, and hTPB from LC, LRH3−2, and Lt (Πi,jf) where TA=AP,TB=BP(2)
∁ computes KAB∗ with the candidate solution of ABP and gets h2AB∗ from LRH2 with IDA,IDB,TAΠA,Bm,TBΠB,An,KAB∗(3)
∁ picks randomly b∈0,1. If b=1, ∁ replies h2AB=h2AB∗ to A1; otherwise, ∁ replies h2AB as a random string to A1
(C4)A1 asks the Γ for a polynomial number of the queries about fresh session Πi,jm.
(C5)A1 makes a guess bit b′.
A1 wins the game in case FI1 by guessing b′=b. After the test (ΠA,Bm) query, A1 asks H2 query with IDA,IDB,TAΠA,Bm,TBΠB,An,⊥,h2AB. Γ gets KAB in LRH2 and asks RDDH oracle with RDDHH3IDA,TA,PATA+RA+H3IDA,RA,PAPpub+PA,H3IDB,TB,PBTB+RB+H3IDB,RB,PBPpub+PB,KAB). If b′=b=1 with the probability of 1/2, the above RDDH oracle will return 1; then, Γ can get KAB=KAB∗ and compute C∙P with
(3)C∙P=tAtB∙P=hTPAhTPB−1KAB∗−sBhTPATA−xBhTPATA−sAhTPBTB−sAsBP−sAxBP−xAhTPBTB−xAsBP−xAxBP.
LetTmul be the time for one scalar multiplication operation and Tadd be the point addition operation over elliptic curve. The time to compute CP is tCP=8Tmul+8Tadd.
Then, ifA1 win the game in case FI1 with advantage ε and running time t, then an algorithm Γ can be constructed to solve the GDH problem with advantage ε′ and running time τ by interacting with A1 only if the game is completed, where events E1 and E2 occur.
E1: A1 chooses ΠA,Bm for challenge.
E2: b′=b=1.
Meanwhile, eventE1 occurs which means all of the events E1−1, E1−2, and E1−3 occur.
E1−1:A1 chooses participants A and B for the challenge with CreateIDA and CreateIDB query.
E1−2: A1 makes query SendΠA,Bm,IDA,TA,RA orSendΠA,Bm,⊥.
E1−3: A1 makes RtAΠA,Bm query and RtBΠB,An query.
(4)ε′=PrE1−1∙PrE1−2∙PrE1−3∙PrE2∙ε=1Cqc2C21Cqsd11Cqt2∙12∙ε=4qcqsdqtqc−1qt−1∙ε,τ≤∑i=23qiti+qctc+qsts+qttt+qsktsk+qsdtsd+qsts+qpkitpki+qrddhtrddh+t+tCP.Lemma 8.
The same as Lemma7 but in case FI2.Proof.
To interact withA1, a GDH slover Γ runs the same steps as that in Lemma 7 to solve the instance of the GDH problem. A1 asks the Γ for a polynomial number of the queries as shown in Lemma 7; Γ answers the following queries differently:
CreateIDi: on receiving IDi, Γ performs as follows:
(1)
IfLC contains a tuple of IDi,si,xi,Pi,Ri(a)
Ifi≠A,B, Γ returns all the elements of the tuple to A1(b)
Otherwise,Γ returns IDi,⊥,xi,Pi,Ri to A1(2)
Otherwise,(a)
ifi≠A,B, Γ randomly chooses xi,si,hi and then computes Pi=xiP and Ri=siP−hiPpub; Γ inserts IDi,si,xi,Pi,Ri to LC and (IDi,Ri,Pi,hi) to LRH3−1 and returns IDi,si,xi,Pi,Ri to A1(b)
Γ randomly chooses xi,hi and computes Pi=xiP and Ri=IP−hiPpub (I = A when i=A; I=B when i=B); Γ inserts IDi,⊥,xi,Pi,Ri to LC and (IDi,Ri,Pi,hi) to LRH3−1 and returns IDi,⊥,xi,Pi,Ri to A1
RsiIDi: on receiving IDi, Γ performs as follows:
(1)
Ifi≠A,B, Γ returns si from LC to A1(2)
Otherwise,Γ returns ⊥ to A1
RtiΠi,jf:
(1)
IfLtΠi,jf contains a tuple of (Πi,jf,ti,Ti), Γ returns ti,Ti to A1(2)
Otherwise,Γ randomly chooses ti, computes Ti=tiP, inserts Πi,jf,ti,Ti to Lt (Πi,jf), and returns ti,Ti to A1
Moreover, the first step of (C3) is also different with that of Lemma7.
(C3)A1 asks a test (ΠA,Bm) query; the challenger ∁ performs as follows:
(1)
∁gets xA, xB, tA, tB, RA, RB, PA, PB, hA, hB, TA, TB, hTPA, and hTPB from LC, LRH3−1, LRH3−2, and Lt (Πi,jf) where RA+hAPpub=AP,RB+hBPpub=BP
Γ gets C∙P with
(5)C∙P=sAsB∙P=KAB∗−hTPAhTPBtAtB∙P−hTPAtARB+hBPpub−xBhTPATA−hTPBtBRA+hAPpub−xBRA+hAPpub−xAhTPBTB−xARB+hBPpub−xAxBP.Lemma 9.
The same as Lemma7 but in case FI3.Proof.
To interact withA1, a GDH slover Γ runs the same steps as that in Lemma 7 to solve the instance of the GDH problem. A1 asks the Γ for a polynomial number of the queries as shown in Lemma 7; Γ answers the following queries differently:
CreateIDi: on receiving IDi, Γ performs as follows:
(1)
IfLC contains a tuple of IDi,si,xi,Pi,Ri(a)
Ifi≠B, Γ returns all the elements of the tuple to A1(b)
Otherwise,Γ returns IDi,⊥,xi,Pi,Ri to A1(1)
Otherwise,(a)
ifi≠B, Γ randomly chooses xi,si,hi and then computes Pi=xiP and Ri=siP−hiPpub; Γ inserts IDi,si,xi,Pi,Ri to LC and (IDi,Ri,Pi,hi) to LRH3−1 and returns IDi,si,xi,Pi,Ri to A1(b)
Γ randomly chooses xi, hi and computes Pi=xiP and Ri=BP−hiPpub; Γ inserts IDi,⊥,xi,Pi,Ri to LC and (IDi,Ri,Pi,hi) to LRH3−1 and returns IDi,⊥,xi,Pi,Ri to A1
RsiIDi: on receiving IDi, Γ performs as follows:
(1)
Ifi≠B, Γ returns si from LC to A1(2)
Otherwise,Γ returns ⊥ to A1
RtiΠi,jf:
(1)
Ifi=A, j=B, and f=m, Γ sets TA=AP, inserts ΠA,Bm,⊥,AP to LtΠi,jf, and returns TA=AP to A1(2)
Otherwise,(a)
ifLt(Πi,jf) contains a tuple of (Πi,jf,ti,Ti), Γ returns ti,Ti to A1(b)
Γ randomly chooses ti, computes Ti=tiP, inserts Πi,jf,ti,Ti to LtΠi,jf, and returns ti,Ti to A1
Moreover, the first step of (C3) is also different with that of Lemma7.
(C3)A1 asks a test (ΠA,Bm) query; the challenger ∁ performs as follows:
(1)
∁ gets sA, xA, xB, tB, RA, RB, PA, PB, TA, TB, hA, hB, hTPA, and hTPB from LC, LRH3−1, LRH3−2, and LtΠi,jf where TA=AP,RB+hBPpub=BP
Γ gets C∙P with
(6)C∙P=tAsB∙P=hTPA−1KAB∗−hTPAhTPBtBTA−xBhTPATA−hTPBtBRA+hAPpub−sARB+hBPpub−xBRA+hAPpub−xAhTPBTB−xARB+hBPpub−xAxBP.Lemma 10.
The same as Lemma7 but in case FI4.Proof.
Case FI4 has no essential difference with case FI3; theproof can be omitted.
Γ gets C∙P with
(7)C∙P=sAtB∙P=hTPB−1KAB∗−hTPAhTPBtATB−hTPAtARB+hBPpub−xBhTPATA−sBRA+hAPpub−xBRA+hAPpub−xAhTPBTB−xARB+hBPpub−xAxBP.Lemma 11.
The same as Lemma7 but in case FI5 and with different ε′. ε′=1/qcqsdqtqc−1∙εProof.
To interact withA1, a GDH slover Γ runs the same steps as that in Lemma 7 to solve the instance of the GDH problem. A1 asks the Γ for a polynomial number of the queries as shown in Lemma 9; Γ answers the following queries differently:
RtiΠi,jf:
(1)
Ifi=A, j=B, f=m or j=A, i=B, and f=n(a)
Ifi=A, j=B, and f=m, Γ sets TA=AP, inserts ΠA,Bm,⊥,AP to LtΠi,jf, and returns TA=AP to A1(b)
Otherwise,Γ returns ⊥ to A1(2)
Otherwise,(a)
ifLt(Πi,jf) contains a tuple of (Πi,jf,ti,Ti), Γ returns ti,Ti to A1(b)
Γ randomly chooses ti, computes Ti=tiP, inserts Πi,jf,ti,Ti to LtΠi,jf, and returns ti,Ti to A1
SendΠi,jf,M:
The matched sessionΠj,in of Πi,jm does not exist.
(1)
This query should be asked afterCreateIDi and RtiΠi,jf when A1 gets Ti and Ri. A1 gets IDi,Ti,Ri from LC and LtΠi,jf and sets M=IDi,Ti,Ri; Γ returns IDj,⊥,Rj to A1 as response(2)
IfM=⊥, Γ initiates the session Πi,jmwithIDi,Ti,Ri(a)
Ifi=A, j=B, and f=m, this query should be asked after CreateIDB. A1 gets xB,PB from LC, sets tB′=xB, and sets TB′=PB, which responds with IDB,TB′,RB(b)
Otherwise,A1 responds with IDj,⊥,Rj
Moreover, the first two steps of (C3) is also different with that of Lemma9.
(C3)A1 asks a test (ΠA,Bm) query; the challenger ∁ performs as follows:
(1)
∁ gets sA, xA, xB, RA, RB, PA, PB, TA, hA, hB, hTPA, and hTPB from LC, LRH3−1, LRH3−2, and Lt (Πi,jf) where TA=AP,RB+hBPpub=BP. ∁ gets TB′ from the response message from A1(2)
LetTB′=B′P; ∁ computes KAB∗ with the candidate solution of ABP and AB′P and gets h2AB∗ from LRH2 with IDA,IDB,TAΠA,Bm,TBΠB,An,KAB∗
As theproof in Lemma 7, if A1 win the game in case FI5, an algorithm Γ can be constructed to solve the GDH problem only if the game is completed, where events E1 and E2 occur. In case FI5, event E1 occurs which means all of the events E1−1, E1−4, and E1−5 occur.
E1−1:A1 chooses participant A and B for challenge with CreateIDA and CreateIDB query
E1−4: A1 makes query SendΠA,Bm,⊥
E1−5: A1 makes RtAΠA,Bm query
(8)ε′=PrE1−1∙PrE1−4∙PrE1−5∙PrE2ε=1Cqc21Cqsd11Cqt1∙12∙ε=1qcqsdqtqc−1∙ε.
AsΓ gets the response with IDB,TB′,RB in query SendΠA,Bm,⊥, in which tB′=xB and TB′=PB; then, Γ computes C∙P with
(9)C∙P=tAsB∙P=hTPA−1KAB∗−hTPAhTPBtB′TA−xBhTPATA−hTPBtB′RA+hAPpub−sARB+hBPpub−xBRA+hAPpub−xAhTPBTB′−xARB+hBPpub−xAxBP=hTPA−1KAB∗−hTPAhTPBxBTA−xBhTPATA−hTPBxBRA+hAPpub−sARB+hBPpub−xBRA+hAPpub−xAhTPBPB−xARB+hBPpub−xAxBP.Lemma 12.
The same as Lemma11 but in case FI5.Proof.
To interact withA1, a GDH slover Γ runs the same steps as that in Lemma 7 to solve the instance of the GDH problem. A1 asks the Γ for a polynomial number of the queries as shown in Lemma 8; Γ answers the following queries differently:
RtiΠi,jf:
(1)
Ifj=A, i=B, and f=n, Γ returns ⊥ to A1(2)
Otherwise,(a)
ifLt (Πi,jf) contains a tuple of (Πi,jf,ti,Ti), Γ returns ti,Ti to A1(b)
Γ randomly chooses ti, computes Ti=tiP, inserts Πi,jf,ti,Ti to LtΠi,jf, and returns ti,Ti to A1
SendΠi,jf,M: the same as that of Lemma 11.
Moreover, the first two steps of (C3) is also different with that of Lemma8.
(C3)A1 asks a test (ΠA,Bm) query; the challenger ∁ performs as follows:
(1)
∁ gets xA, xB, tA, RA, RB, PA, PB, hA, hB, TA, hTPA, and hTPB from LC, LRH3−1, LRH3−2, and Lt(Πi,jf) where RA+hAPpub=AP,RB+hBPpub=BP. ∁ gets TB′ from the response message from A1(2)
LetTB′=B′P; ∁ computes KAB∗ with the candidate solution of ABP and AB′P and gets h2AB∗ from LRH2 with IDA,IDB,TAΠA,Bm,TBΠB,An,KAB∗
Γ gets C∙P with
(10)C∙P=sAsB∙P=KAB∗−hTPAhTPBtAtB′∙P−hTPAtARB+hBPpub−xBhTPATA−hTPBtB′RA+hAPpub−xBRA+hAPpub−xAhTPBTB′−xARB+hBPpub−xAxBP=sAsB∙P=KAB∗−hTPAhTPBtAxB∙P−hTPAtARB+hBPpub−xBhTPATA−hTPBxBRA+hAPpub−xBRA+hAPpub−xAhTPBPB−xARB+hBPpub−xAxBP.
With the similar proof, Lemma 13 to 18 can be derived for case FII1-FII6, which need not be given in this paper. Then, according to Lemma7 to 18, if A win the game in polynomial time, Γ can solve the GDH problem, which is contradictory with the security assumption of GDH problem. Then, we conclude that A cannot win the Game and AdvAk is negligible. Therefore, our protocol is secure under the eCK security model with the GDH assumption.


## 5. Performance Analysis

According to the research work in literatures [26, 27], the calculation time of relevant operation in protocol execution is shown in Table 4. The cross-domain authentication scheme proposed in this paper is compared and analyzed with existing schemes of the same type, and the cost comparison of scheme calculation is shown in Table 5. The parameters used in the table are as follows:Table 4
Calculation time of password operation.
SymbolMeaningTimeTmulA dot product operation time on an elliptic curve7.3529 msThHash function operation time0.0004 msTmModular multiplication operation time0.0147 msTexpModular exponential operation time18.38225 msTaddOne point plus operation time on an elliptic curve0.0613 msTable 5
Computation of overhead comparison.
ProtocolsNumber of roundsLow-power mobile nodePowerful nodeJoin phaseRemoval phaseTotal computation costChuang and Tseng [28]32Texp+3Thm+1Texp+2m+1Th2Texp+2m+3Th2m+2Thm+5Texp+6m+9ThWu et al. [29]22Texp+2Thm+1Texp+m+1Th2Texp+m+4Thm+4Thm+5Texp+3m+11ThIslam et al. [30]24Tmul+4Th3m+2Tmul+2m+2Th2m+5Tmul+6Th2m+4Tmul+5Th7m+15Tmul+2m+17ThMandal et al. [31]25Tmul+9Th4m+2Tmul+5m+7Th3m+4Tmul+2m+11Th3m+4Tmul+2m+11Th10m+15Tmul+9m+38ThLuo et al. [21]15Tmul+Tadd+4Th5m+1Tmul+3mTadd+4mTh3m+10Tmul+m+5Tadd+m+8Th3m−1Tmul+m+2Tadd+mTh11m+15Tmul+5m+8Tadd+6m+12ThProposed scheme25Tmul+3Th4m−1Tmul+6m−1Th4m+5Tmul+6m+3Th4m−3Tmul+6m−9Th12m+3Tmul+18m−9Thm: number of participants in each domain Din: the number of domains for cross-domain key negotiationN: the number of participants in a negotiationIn this scheme, we use the dot product of elliptic curve operation and hash function to encryption scheme. Chuang and Tseng and Wu et al.’s scheme [28, 29] used modular exponential operation. Table 4 shows that the operation time of modular finger is longer than a dot product operation time on elliptic curve. Compared with that, our calculation cost is smaller and the number of rounds negotiated is also less. Though the computation cost of [30] is lower than our proposed model, however Tan’s scheme lacks perfect forward secrecy [32], and the schemes do not have a signature mechanism that supports confidentiality, integrity, authentication, and nonrepudiation in a logical step. Mandal et al.’s scheme [31] used signature verification with a signature verification time of 2.005 s, but they did not include the signature verification time into the calculation cost. So compared with Mandal et al.’s scheme, our computational cost is still lower. Although in Luo et al.’s scheme [21], the group session key is calculated in one-round communication and the total computation cost is lower than our proposed protocol when m is large, our proposed protocol has lower computation cost for low-power mobile node and powerful node when there is no member joining or removing from the group. In addition, Luo et al.’s scheme only had a secondary security level, the malicious KGC could collude with some malicious users to attack the protocol indicated by Ren et al. [24].


## 6. The Conclusion

In view of the shortage and complexity of cross-domain group authentication communication schemes, this paper proposes a certificateless cross-domain group key management scheme based on ECC. In the proposed scheme, key negotiation is divided into two parts: intradomain key negotiation and interdomain key negotiation. On the basis of ensuring security, group cross-domain communication is realized. It avoids the complex certification path construction and verification process and reduces the length of the trust path. The scheme is proved to be secure in random oracle model with low computational cost and is suitable for users’ group communication requirements across multiple domains.



---

*Source: 7519688-2022-12-05.xml*