# A Certificateless Noninteractive Key Exchange Protocol with Provable Security

Authors: Xuefei Cao; Lanjun Dang; Yingzi Luan; Wei You
Journal: Security and Communication Networks
 (2020)

---

## Abstract

In this paper, we propose a certificateless noninteractive key exchange protocol. No message exchange is required in the protocol, and this feature will facilitate the applications where the communication overhead matters, for example, the communications between the satellites and the earth. The public key certificate is removed as well as the key escrow problem using the certificateless public key cryptosystem. The security of the protocol rests on the bilinear Diffie–Hellman problem, and it could be proved in the random oracle model. Compared with previous protocols, the new protocol reduces the running time by at least 33.0%.


---

## Body

## 1. Introduction

Noninteractive key exchange (NIKE) protocols enable two users to establish a shared key without any interactions. In a NIKE, every user puts up his public key in a public directory, and two users can set up a shared key with the other’s public key and his own private key [1]. The earliest example of NIKE is Diffie–Hellman key exchange proposed in the seminal paper of [2]. In the protocol, Alice and Bob share a common group G of order q with generator g. Alice’s public key is of the form gx∈G, and Bob’s public key is of the form gy∈G. Then, Alice and Bob can establish a shared key gxy without any communications. NIKE is very useful to secure the communications where the communication delay matters, for example, the communications in the wireless networks where two terminals are far away from each other. Another example is the communication between the satellite and the earth. The distance between the satellite and the earth will increase the running time of a security protocol dramatically, and a NIKE protocol will reduce the protocol delay to the minimum because no interaction is needed between the earth and the satellite [3]. With NIKE protocols, two participants can establish a key and sends encrypted message to its peer right away [4, 5].Similar to NIKE protocols, public key encryption can also realize noninteractive communications. However, there are differences between the two. In a public key encryption system, anyone who wants to send the receiver Alice an encrypted message, only needs to know Alice’s public key and the system parameters. In a NIKE system, both parties should be enrolled in the system and have their private keys in order to establish a shared key. Furthermore, the encryption algorithm in a public key system is much slower than the encryption algorithm in a NIKE system because the latter could use the symmetric encryption algorithm once the shared key is set up.In this paper, we propose a noninteractive key exchange protocol based on certificateless public key cryptosystem. The security of the protocol is based on the bilinear Diffie–Hellman problem. Our contributions are mainly as follows:(1)
A noninteractive key agreement protocol is proposed based on the certificateless public key cryptosystem.(2)
The security model of NIKE protocols in the setting of certificateless public key cryptosystem is studied.(3)
The security of the proposed protocol is proved formally using the security model of NIKE protocols.(4)
The computation efficiency of the proposed protocol is improved compared with the available NIKE protocols.The remaining part of this paper is organized as follows: Section2 provides a research on the related work of NIKE protocols; Section 3 introduces the preliminaries, security definition, and security model; in Section 4, we introduce our scheme; Section 5 gives the security proof of our scheme. Section 6 gives the performance comparison; and Section 7 concludes the paper.


## 2. Related Works

According to the cryptosystems underlined, available NIKE protocols can be divided into three categories, i.e., certificate-based ones, identity-based ones, and certificateless ones. Certificate-based NIKE protocols employ the traditional certificate-based cryptography. Diffie–Hellman’s noninteractive key exchange scheme falls into this category. In 2006, a certificate-based NIKE protocol was proposed using an elliptic curve [6], and a PKI-based security model was given. Later, Cash et al. proposed a stronger security model for NIKE, and a NIKE protocol using the twin Diffie–Hellman problem was also proposed [7]. In 2013, Freire et al. provided different security models for NIKE and studied the relationship between different security models. They also gave two NIKE constructions with provable security [8]. Hesse et al. proposed a NIKE with tight security reduction in [9].In 1991, Maurer and Yacobi proposed an identity-based NIKE protocol based on a one-way trapdoor function [10]. However, it was pointed out that Maurer and Yacobi’s scheme was weak in security [11]. Later, Maurer and Yacobi improved their protocol [12], but the scheme was still proven insecure [13]. In 2000, Sakai et al. [14] proposed an ID-based NIKE protocol by introducing the bilinear pairings, but there were no formal security proofs. Dupont and Enge extended Sakai et al.’s scheme to a more general case and provided a security model for ID-based NIKE [15]. Paterson and Sirinivasan studied the relationship between ID-based NIKE and ID-based encryption and proposed an ID-NIKE scheme [16] and a security model stronger than Dupont and Enge’s model. An improved ID-NIKE with forward secrecy is proposed in [17].To remove the inborn issue of key escrow with ID-based cryptosystem, Al-Riyami and Paterson proposed the certificateless cryptography [18]. In certificateless cryptography, a user’s private key is generated both by the key generation center (KGC) and the user. Since, in the private key, there is a portion which is unknown to KGC, certificateless cryptography removes the key escrow problem. Compared with ID-based cryptosystem, certificateless cryptosystem maintains the former’s strength of lightweight public key management while achieves an improved level of security. Even the security authority is unable to know the secret established. In 2014, Sang et al. proposed a certificateless NIKE (CL-NIKE) protocol [19]. Later, Fu and Liu proposed another CL-NIKE protocol [20]. However, neither of the two protocols provided integrated security proof.


## 3. Preliminaries and Security Models

### 3.1. Preliminaries

LetG1 be an additive group of order q, where q is a large prime, and G2 be a multiplicative group of the same order. Let P be an arbitrary generator of G1; then, a bilinear pairing e is a map e:G1×G1⟶G2 satisfying the following properties:(1)
Bilinearity: givenP∈G1 and a,b∈ℤq∗, we have eaP,bP=eP,Pab.(2)
Nondegeneracy: givenP a generator of G1, then Q=eP,P is a generator of G2.(3)
Computability:eP1,P2 is efficiently computable for all P1,P2∈G1.The following problem is assumed intractable in polynomial time [18]: bilinear Diffie–Hellman problem (BDHP): given aP,bP,cP∈G13 for unknown a,b,c∈ℤq∗, compute eP,Pabc.


### 3.2. Security Definition

In this section, we present the definition of CL-NIKE. A CL-NIKE scheme is defined by the following six algorithms:(1)
Setup: this algorithm is run by the KGC once at the beginning to set up a certificateless key agreement system. It takes security parameterk and returns system parameters params and the master key of KGC master-key. params are publicly authentically available, but the master-key is known only to the KGC.(2)
Partial-private-key-extract: the algorithm generates the partial private key for system users. It is run by the KGC. It takesparam, master key, an entity A’s identifier IDA, and outputs A’s partial private key DA. KGC sends DA to A via a secret channel.(3)
Set-secret-value: the algorithm is run by an entityA. The algorithm returns A’s secret value xA.(4)
Set-private-key: the algorithm is run byA. It takes xA and DA and returns A’s private key SA.(5)
Set-public-key: the algorithm is run byA. It takes params and xA and returns A’s public key PA.(6)
Shared-key: on inputparams, A’s identifier IDA and private key SA, and entity B’s identifier IDB and public key PB, this algorithm outputs a shared key KAB between A and B.


### 3.3. Security Model

CK model [21] and eCK model [22] are the most widely used security models for authenticated key exchange (KE) protocols. However, they are not suitable for noninteractive key exchange protocols because CK model and eCK model provide security analysis to ephemeral secrets [23] but no ephemeral secrets are used in NIKE protocols. Therefore, a NIKE protocol needs its own security model.Bernstein [6] and Cash et al. [7] first proposed the security models for NIKE protocols, respectively. Later, Dupont and Enge [15] and Paterson and Srinivasan [16] extended the security models in [6, 7] from the certificate-based cryptosystem to the ID-based cryptosystem. Paterson’s security model is stronger than Dupont’s security model because Paterson’s model considers the security against the known session key attack by allowing the reveal query in the security model. Our security model follows Paterson’s model in [16]. Furthermore, we extend Paterson’s security model from ID-based cryptosystem to certificateless cryptosystem. Our security model considers the particular public/private key setting in the certificateless public key cryptosystem, and the case where an attacker replaces the legal user’s public key, and the case where the malicious KGC wants to break the shared key.Now we define our security model of CL-NIKE protocols.There are two types of adversaries to a CL-NIKE protocol, i.e., type I adversaryAI and type II adversary AII. Type I adversary simulates the ordinary attacker who is not able to get a user’s partial private key but is able to replace a legal user’s public key. AI is able to do this because there is no public key certificate in a CL-NIKE. Type II adversary simulates the malicious KGC who owns the system master key and hence knows every user’s partial private key but cannot replace the legal user’s public key because that is easily detected and could destroy KGC’s reputation. Consider two games, game I and game II between a challenger C and AI and AII, respectively. The security of a CL-NIKE protocol is defined via the two games:Game I: the game is betweenAI and C.Setup phase: in this phase, given security parameterk, challenger C obtains the system parameters params and master key. C gives params to AI while keeps the master key secretly.Query phase: in this phase, the adversaryAI can carry out the following queries in any order, and C will answer the queries.(1)
Partial private key extraction:AI chooses an entity with identifier IDI and queries user I’s partial private key. C runs the Partial-Private-Key-Extract to generate the partial private key DI and returns it to AI.(2)
Secret value extraction: after receiving the query,C runs the Set-Secret-Value algorithm and returns xI to AI.(3)
Private key extraction:C will call Partial-Private-Key-Extract and Set-Secret-Value in this query to obtain DI and xI, and then, C runs Set-Private-Key on DI and xI to generate the private key SI.(4)
Public key request:C first runs Set-Secret-Value and keeps xI for itself. Then, C runs Set-Public-Key to generate IDI’s public key PI and returns it to AI.(5)
Public key replacement:AI will replace the public key of an entity with any value of its choice.(6)
Shared key revealing: suppose the query is onIDA and IDB, C obtains SA and PB, then runs Shared Key to obtain the KAB between IDA and IDB and returns it to AI.Test phase: given a pair of identitiesIDM and IDN, C obtains KMN as above. Then, C selects at random b←0,1 and returns KMN when b=0 and 0,1l when b=1. l is the length of the shared key.Finally,AI outputs its guess b′, and AI will win the game if b′=b. AI’s advantage in the game is(1)AdvAIGame I=Prb=b′−12.We say the CL-NIKE scheme is secure againstAI if AdvAIGame I is negligible.Game II: the game is betweenAII and C.Setup phase: in this phase, given security parameterk, challenger C obtains the system parameters params and master key. C gives both params and master key to AII.Query phase: sinceAII has master key, it can compute the partial private key of any user. Then, in this phase, AII does not make the partial private key extraction query. Also, since AII is not allowed to replace the user’s public key, it does not make the public key replacement query. In game II, AII makes the queries and C answers as follows:(1)
Secret value extraction: on receiving the query onIDI, C runs the Set-Secret-Value and returns xI to AII.(2)
Private key extraction: if userI’s partial private key has not been computed, C first computes I’s partial private key using master key, then it calls the Set-Secret-Value to obtain xI. At last, C runs the Set-Private-Key to obtain user I’s private key and returns it to AII.(3)
Public key request: on receiving this query,C first runs Set-Secret-Value to obtain xI and then it runs Set-Public-Key to obtain the public key and returns it to AII.(4)
Shared key revealing: suppose this query is made onIDA and IDB. C runs corresponding algorithms to obtain the SA and PB, and then, it computes KAB by running the SharedKey and returns KAB to AII.Test phase: given a pair of identitiesIDM and IDN, C obtains KMN as above. Then, C selects at random b⟵0,1 and returns KMN when b=0 and 0,1l when b=1. l is the length of the shared key.Finally,AII outputs its guess b′, and AII will win the game if b′=b. AII’s advantage in the game is(2)AdvAIIGame II=Prb=b′−12.We say the CL-NIKE scheme is secure againstAII if AdvAIIGame II is negligible.A CL-NIKE scheme is secure if it is secure both againstAI and AII.


## 3.1. Preliminaries

LetG1 be an additive group of order q, where q is a large prime, and G2 be a multiplicative group of the same order. Let P be an arbitrary generator of G1; then, a bilinear pairing e is a map e:G1×G1⟶G2 satisfying the following properties:(1)
Bilinearity: givenP∈G1 and a,b∈ℤq∗, we have eaP,bP=eP,Pab.(2)
Nondegeneracy: givenP a generator of G1, then Q=eP,P is a generator of G2.(3)
Computability:eP1,P2 is efficiently computable for all P1,P2∈G1.The following problem is assumed intractable in polynomial time [18]: bilinear Diffie–Hellman problem (BDHP): given aP,bP,cP∈G13 for unknown a,b,c∈ℤq∗, compute eP,Pabc.


## 3.2. Security Definition

In this section, we present the definition of CL-NIKE. A CL-NIKE scheme is defined by the following six algorithms:(1)
Setup: this algorithm is run by the KGC once at the beginning to set up a certificateless key agreement system. It takes security parameterk and returns system parameters params and the master key of KGC master-key. params are publicly authentically available, but the master-key is known only to the KGC.(2)
Partial-private-key-extract: the algorithm generates the partial private key for system users. It is run by the KGC. It takesparam, master key, an entity A’s identifier IDA, and outputs A’s partial private key DA. KGC sends DA to A via a secret channel.(3)
Set-secret-value: the algorithm is run by an entityA. The algorithm returns A’s secret value xA.(4)
Set-private-key: the algorithm is run byA. It takes xA and DA and returns A’s private key SA.(5)
Set-public-key: the algorithm is run byA. It takes params and xA and returns A’s public key PA.(6)
Shared-key: on inputparams, A’s identifier IDA and private key SA, and entity B’s identifier IDB and public key PB, this algorithm outputs a shared key KAB between A and B.


## 3.3. Security Model

CK model [21] and eCK model [22] are the most widely used security models for authenticated key exchange (KE) protocols. However, they are not suitable for noninteractive key exchange protocols because CK model and eCK model provide security analysis to ephemeral secrets [23] but no ephemeral secrets are used in NIKE protocols. Therefore, a NIKE protocol needs its own security model.Bernstein [6] and Cash et al. [7] first proposed the security models for NIKE protocols, respectively. Later, Dupont and Enge [15] and Paterson and Srinivasan [16] extended the security models in [6, 7] from the certificate-based cryptosystem to the ID-based cryptosystem. Paterson’s security model is stronger than Dupont’s security model because Paterson’s model considers the security against the known session key attack by allowing the reveal query in the security model. Our security model follows Paterson’s model in [16]. Furthermore, we extend Paterson’s security model from ID-based cryptosystem to certificateless cryptosystem. Our security model considers the particular public/private key setting in the certificateless public key cryptosystem, and the case where an attacker replaces the legal user’s public key, and the case where the malicious KGC wants to break the shared key.Now we define our security model of CL-NIKE protocols.There are two types of adversaries to a CL-NIKE protocol, i.e., type I adversaryAI and type II adversary AII. Type I adversary simulates the ordinary attacker who is not able to get a user’s partial private key but is able to replace a legal user’s public key. AI is able to do this because there is no public key certificate in a CL-NIKE. Type II adversary simulates the malicious KGC who owns the system master key and hence knows every user’s partial private key but cannot replace the legal user’s public key because that is easily detected and could destroy KGC’s reputation. Consider two games, game I and game II between a challenger C and AI and AII, respectively. The security of a CL-NIKE protocol is defined via the two games:Game I: the game is betweenAI and C.Setup phase: in this phase, given security parameterk, challenger C obtains the system parameters params and master key. C gives params to AI while keeps the master key secretly.Query phase: in this phase, the adversaryAI can carry out the following queries in any order, and C will answer the queries.(1)
Partial private key extraction:AI chooses an entity with identifier IDI and queries user I’s partial private key. C runs the Partial-Private-Key-Extract to generate the partial private key DI and returns it to AI.(2)
Secret value extraction: after receiving the query,C runs the Set-Secret-Value algorithm and returns xI to AI.(3)
Private key extraction:C will call Partial-Private-Key-Extract and Set-Secret-Value in this query to obtain DI and xI, and then, C runs Set-Private-Key on DI and xI to generate the private key SI.(4)
Public key request:C first runs Set-Secret-Value and keeps xI for itself. Then, C runs Set-Public-Key to generate IDI’s public key PI and returns it to AI.(5)
Public key replacement:AI will replace the public key of an entity with any value of its choice.(6)
Shared key revealing: suppose the query is onIDA and IDB, C obtains SA and PB, then runs Shared Key to obtain the KAB between IDA and IDB and returns it to AI.Test phase: given a pair of identitiesIDM and IDN, C obtains KMN as above. Then, C selects at random b←0,1 and returns KMN when b=0 and 0,1l when b=1. l is the length of the shared key.Finally,AI outputs its guess b′, and AI will win the game if b′=b. AI’s advantage in the game is(1)AdvAIGame I=Prb=b′−12.We say the CL-NIKE scheme is secure againstAI if AdvAIGame I is negligible.Game II: the game is betweenAII and C.Setup phase: in this phase, given security parameterk, challenger C obtains the system parameters params and master key. C gives both params and master key to AII.Query phase: sinceAII has master key, it can compute the partial private key of any user. Then, in this phase, AII does not make the partial private key extraction query. Also, since AII is not allowed to replace the user’s public key, it does not make the public key replacement query. In game II, AII makes the queries and C answers as follows:(1)
Secret value extraction: on receiving the query onIDI, C runs the Set-Secret-Value and returns xI to AII.(2)
Private key extraction: if userI’s partial private key has not been computed, C first computes I’s partial private key using master key, then it calls the Set-Secret-Value to obtain xI. At last, C runs the Set-Private-Key to obtain user I’s private key and returns it to AII.(3)
Public key request: on receiving this query,C first runs Set-Secret-Value to obtain xI and then it runs Set-Public-Key to obtain the public key and returns it to AII.(4)
Shared key revealing: suppose this query is made onIDA and IDB. C runs corresponding algorithms to obtain the SA and PB, and then, it computes KAB by running the SharedKey and returns KAB to AII.Test phase: given a pair of identitiesIDM and IDN, C obtains KMN as above. Then, C selects at random b⟵0,1 and returns KMN when b=0 and 0,1l when b=1. l is the length of the shared key.Finally,AII outputs its guess b′, and AII will win the game if b′=b. AII’s advantage in the game is(2)AdvAIIGame II=Prb=b′−12.We say the CL-NIKE scheme is secure againstAII if AdvAIIGame II is negligible.A CL-NIKE scheme is secure if it is secure both againstAI and AII.


## 4. Protocol Description

In this section, we propose a new CL-NIKE protocol. The new protocol includes six algorithms, as described in Section3.2, and each algorithm is as follows:(i)
Setup: given system security parameterk, KGC does the following:(1)
OutputsG1andG2ande satisfying the definitions in Section 3.1.(2)
Chooses an arbitrary generatorP of G1.(3)
Selects the master keys∈Rℤq∗ at random and computes the system public key P0=sP.(4)
Selects two hash functionsH1:0,1∗⟶G1 and H2:0,1∗⟶0,1l.(5)
PublishesG1,G2,q,e,P,P0,H1,H2 as system parameters and keeps s secretly.(i)
Partial-Private-Key-Extract: given a userA’s identifier IDA, KGC computes QA=H1IDA and DA=sQA. DA is A’s partial private key. KGC returns DA to A via a secure channel.(iii)
Set-Secret-Value:A selects at random xA∈Rℤq∗ and sets xA as his secret value.(iv)
Set-Private-Key:A’s private key is SA=xA,DA=xA,sH1IDA.(v)
Set-Public-Key:A computes XA=xAP and YA=xAP0 and his public key is PA=XA,YA.(vi)
SharedKey: to set up a shared key withB, A first verifies whether B’s public key is of the correct form, i.e., A verifies if the equation eXB,P0=eYB,P holds. If the verification is correct, A computes the shared secrets:(3)KA1=eDA+xAYB,QB,KA2=xAYB.The shared key is(4)KAB=H2IDA,IDB,KA1,KA2.To compute the shared key,B first verifies A’s public key by checking if the equation eXA,P0=eYA,P holds. If the verification is correct, B computes the shared secrets:(5)KB1=eQA+xBXA,DB,KB2=xBYA.The shared key is(6)KBA=H2IDA,IDB,KB1,KB2.The correctness of the protocol could be guaranteed because(7)KA1=eDA+xAYB,QB=eQA+xAxBP,sQB=eQA+xBXA,DB=KB1,KA2=xAYB=xAxBP0=xBYA=KB2,(8)KAB=H2IDA,IDB,KA1,KA2=H2IDA,IDB,KB1,KB2=KBA.The procedure of the SharedKey algorithm is illustrated in Figure1.Figure 1
Procedure of SharedKey algorithm.


## 5. Security Proof

In this section, we prove the security of our protocol in the random oracle model based on the security model in Section3. We have the following theorem:Theorem 1.
If BDH problem is hard, our CL-NIKE protocol is secure in the random oracle model.The theorem can be proven via Lemma1 and Lemma 2.Lemma 1.
If there exists a type I adversaryAI which wins game I against our CL-NIKE protocol, then BDH problem can be solved with nonnegligible probability in the random oracle model.Proof.
Suppose a challengerC is given an instance of aP,bP,cP∈G13 and is tasked to compute eP,Pabc. If there is a type I adversary AI which wins the game I against the proposed protocol, then C can solve the BDH problem by controlling the queries with AI.
In the setup phase,C chooses the system parameters G1,G2,q,e,P,H1,H2, and C sets the system public key P0=cP with the master-key c unknown to C.
In the query phase, hash functionsH1 and H2 are modeled as random oracles. Without generality, we suppose that there are n1 users in the system, and AI chooses IDA and IDB in the test phase. We also suppose AI is allowed to ask n2H2 queries. During this phase, C answers every query as follows:(1)
H1 query: AI’s H1 query is of the form IDi. C maintains an H1-list with each entry of the form IDi,hi1,hi1P. On receiving AI’s query, C first searches H1-list whether there is an entry indexed by IDi. If there is, C returns hi1P to AI. If there is not, the following holds:(a)
IfIDi=IDA, C inserts IDA,⊥,aP in the list and returns aP to AI.(b)
IfIDi=IDB, C inserts IDB,⊥,bP in the list and returns bP to AI.(c)
IfIDi∉IDA,IDB, C chooses at random hi1∈Rℤq∗, returns hi1P to AI, and inserts IDi,hi1,hi1P to the H1-list.(2)
H2 query: AI’s H2 query is of the form IDi,IDj,Kij1,Kij2. C maintains an H2-list with each entry the form IDi,IDj,Kij1,Kij2,hij2. On receiving AI’s query, C first searches H2-list whether there is an entry indexed by IDi,IDj. If there is an item indexed by IDi,IDj, C returns the corresponding hij2 to AI. Or else C chooses at random hij2∈0,1l, returns hij2 to AI, and inserts IDi,IDj,Kij1,Kij2,hij2 to H2-list.(3)
Partial private key extraction:C maintains a K-list of user’s keys. K-list is of the form IDi,xi,Di,Xi,Yi,tag. xi,Di are IDi’s private key, and Xi,Yi are IDi’s public key. If tag=0, it means that IDi’s public key has not been replaced. If tag=1, it means that IDi’s public key has been replaced, and the corresponding Xi,Yi is the replaced ones.On receivingAI’s query on IDi, C checks K-list; if there is an entry indexed by IDi and Di≠−, C returns the corresponding Di. If no entry indexed by IDi or Di=−, C does the following:(a)
IfIDi∉IDA,IDB, C checks H1-list with IDi for hi1. If there is no entry indexed by IDi in H1-list, C first makes H1 query. Then, C computes Di=hi1cP. If no entry is indexed by IDi in K-list, C inserts IDi,−,Di,−,−,− to it; if there is an entry indexed by IDi but Di=− in K-list, C only inserts Di. Finally, C returns Di to AI.(b)
IfIDi∈IDA,IDB, C aborts the game.(4)
Secret value extraction: on receiving such a query onIDi, C checks the K-list. If there is an item indexed by IDi and xi≠−, C returns xi to AI. If there is not an item indexed by IDi or xi=−, C runs the Set-Secret-Value algorithm to obtain xi. If there is not an entry indexed by IDi, C adds IDi,xi,−,−,−,− in the K-list. If there is an entry indexed by IDi but xi=−, C only adds xi to the entry. Finally, C returns xi to AI.(5)
Private key extraction: the query is onIDi. If IDi∈IDA,IDB, C aborts the game. Otherwise, C checks the K-list. If there is an item indexed by IDi, xi≠−, and Di≠−, C returns xi,Di to AI. If there is not such an item or if there is an item indexed by IDi, but at least one value of xi and Di equals −, according to the value needed, C runs Set-Secret-Value to obtain xi and queries the partial private key extraction oracle to obtain Di. If there is no item indexed by IDi, C adds IDi,xi,Di,−,−,− to the K-list. If there is an item indexed by IDi, but xi,Di in the item is incomplete, C adds the missed value(s) to the item. Finally, C returns xi,Di to AI.(6)
Public key request: on receiving such a query onIDi, C checks the K-list. If there is an item indexed by IDi and Xi,Yi≠−, C returns Xi,Yi. If there is not an item indexed by IDi, C runs the Set-Secret-Value to obtain xi, computes Xi,Yi, and then adds IDi,xi,−,Xi,Yi,0 to the K-list. If there is an item indexed by IDi, but Xi,Yi=−, C first checks if xi=−. If xi=−, C runs the Set-Secret-Value algorithm to obtain xi, computes Xi,Yi, and adds xi, Xi,Yi, tag=0 to the item. If xi≠−, C computes Xi,Yi, inserts Xi,Yi, tag=0 in the item. Finally, C returns Xi,Yi to AI.(7)
Public key replacement: without generality, we assume that the query is of the formIDi,Xi′,Yi′, where eXi′,cP=eYi′,P. On receiving such a query, C sets the entry indexed by IDi as IDi,⊥,Di,Xi′,Yi′,1 in the K-list.(8)
Shared key revealing:AI’ query is on IDi,IDj. C aborts the game if IDi,IDj=IDA,IDB. Otherwise, C queries IDi’s private key and IDj’s public key, computes the shared key according to the protocol description, and returns Kij to AI.
In the test phase,AI’s query is on IDi,IDj. If IDi,IDj≠IDA,IDB, C aborts the game. Else, C chooses uniformly 0,1l and returns it to AI.
IfAI makes the correct guess, then he must have queried H2 oracle. C searches the H2 list for the entry IDA,IDB,KAB1,KAB2,hAB2. Suppose B’s public key has been replaced with XB′,YB′, then we have that(9)KAB1=eDA+xAYB′,QB=eacP+xAYB′,bP=eacP,bPeKAB2,bP,so eP,Pabc=KAB1⋅eKAB2,−bP.
SupposeAI’s probability of success is AdvAIGame I, then C’s probability of success is at least AdvAIGame I/n12n2.Lemma 2.
SupposeH1 and H2 are random oracles. If a type II adversary AII can win the game II against the proposed CL-NIKE protocol, then the BDH problem can be solved with nonnegligible probability.Proof.
Suppose there is a challengerC who is given an instance of aP,bP,cP∈G13 and is tasked to compute eP,Pabc. If there is a type II adversary AII, then C can solve the BDH problem by controlling the queries with AII.
In the setup phase,C chooses the system parameters G1,G2,q,e,P,H1,H2 and the master key s and computes the system public key P0=sP. C gives the system parameters G1,G2,q,e,P,H1,H2 as well as the master key s to AII.
In the query phase, hash functionsH1 and H2 are modeled as random oracles. Without generality, we suppose that there are n1 users in the system, and AII chooses IDA and IDB to ask the test query. We also suppose AII is allowed to ask n2H2 queries. The ways that C answers AII’s queries are as follows:(1)
H1 query: AII’s H1 query is of the form IDi. C maintains an H1-list with each entry of the form IDi,hi1,hi1P. On receiving AII’s query, C first searches H1-list. If there is an item indexed with IDi, C returns the corresponding hi1P to AI. If there is not such an item, the following holds:(a)
IfIDi=IDB, C inserts IDB,⊥,bP in the list and returns bP.(b)
IfIDi≠IDB, C chooses uniformly hi1∈Rℤq∗, returns hi1P, and inserts IDi,hi1,hi1P to the H1-list.(2)
H2 query: AII’s H2 query is of the form IDi,IDj,Kij1,Kij2. C maintains an H2-list with each entry the form IDi,IDj,Kij1,Kij2,hij2. On receiving AII’s H2 query, C first searches H2-list. If there is an item indexed with IDi,IDj,Kij1,Kij2, then C returns the corresponding hij2. Else, C chooses hij2∈R0,1l, returns hij2 to AII, and inserts IDi,IDj,Kij1,Kij2,hij2 to H2-list.(3)
Secret value extraction:C maintains a K-list of the form IDi,xi,Di,Xi,Yi. On receiving AII’s query on IDi, C first checks whether there is an entry indexed by IDi in the K-list. If there is, C returns xi. Otherwise, C runs the Set-Secret-Value algorithm to obtain xi, adds IDi,xi,−,−,− to the K-list, and returns xi to IDi. We note here that it is impossible that there is an item indexed by IDi but xi=− because Di is known by AII and the entry must be generated by asking xi.(4)
Private key extraction:AII’s private key extraction query is on IDi. If IDi∈IDA,IDB, C aborts the game. Else C searches the K-list, if there is an item indexed by IDi, and xi≠−, Di≠−, and C returns xi,Di. If there is not an item indexed by IDi, C runs the Set-Secret-Value to get xi and computes Di using s, then C inserts IDi,xi,Di,−,− to the K-list. If there is an item indexed by IDi, but Di is missing, C computes Di using s and adds Di to the K-list. Finally, C returns xi,Di to AII.(5)
Public key request: on receiving such a query onIDi, C checks the K-list. If there is an entry listed by IDi and Xi,Yi≠−, C returns Xi,Yi. Otherwise, C does the following:(a)
IfIDi∉IDA,IDB and there is not an item indexed by IDi, C runs the Set-Secret-Value to obtain xi and computes Xi=xiP and Yi=xisP, then C adds IDi,xi,−,Xi,Yi to the K−list. If IDi∉IDA,IDB and there is an entry indexed by IDi, then the entry must be generated when AII queries IDi’s private key. C obtains xi from the entry, computes Xi=xiP and Yi=xisP, and adds Xi,Yi to the entry.(b)
IfIDi=IDA, C sets XA=aP and computes YA=saP. Then, C adds IDA,⊥,⊥,XA,YA to the K−list.(c)
IfIDi=IDB, C sets XB=cP and computes YA=scP. Then, C adds IDB,⊥,⊥,XB,YB to the K−list.Finally,C returns Xi,Yi to AII.(6)
Shared key revealing:AII’ query is on IDi,IDj. If IDi,IDj=IDA,IDB, then C aborts the game. Else, C queries IDi’s private key and IDj’s public key, computes the shared key according to the protocol description, and returns Kij to AI.
In the test phase,AII chooses IDi,IDj as query. If IDi,IDj≠IDA,IDB, C aborts the game. Else, C chooses uniformly 0,1l and returns it to AII.
IfAII makes the correct guess, then he must have queried H2 oracle. C searches the H2 list for the entry IDA,IDB,KAB1,KAB2,hAB2. We have that KAB1=eDA+xAYB,QB=eshA1P+sacP,bP=eshA1P,bPesacP,bP, and then, C can output eP,Pabc=KAB11/s⋅ehA1P,−bP.
SupposeAII’s probability of success is AdvAIIGame II, then C’s probability of success is at least AdvAIIGame II/n12n2.
We also note here that, in a CL-NIKE protocol, a participantIDA has the private key or long-term secret of the form xA,DA, where xA is IDA’s secret number, and DA is IDA’s partial private key. A CL-NIKE protocol allows the leakage of xA or DA.
In the above security proof, the security against a leakedxA is modeled by game I, which allows an attacker to obtain xA via the public key replacement query. The security against a leaked DA is modeled by game II, which gives the attacker the master key or the partial private key of every participant in the system.
A CL-NIKE protocol does not allow the leakage of bothxA and DA or the private key. This is very different from authenticated KE protocols because authenticated KE protocols use ephemeral keys [24, 25], and the security of the shared key could be guaranteed by the ephemeral keys even if both participants’ private keys are lost. In order to realize the noninteractive key establishment, there is no ephemeral keys used in NIKE protocols; thus, the leakage of private keys is not allowed in NIKE protocols. However, compared with certificate-based NIKE protocols [7] or identity-based NIKE protocols [15, 16], our CL-NIKE protocol allows the leakage of part of the private key, and this results in the improved security.


## 6. Performance Analysis

In this section, we compare our protocol with Sang et al.’s protocol [19] and Fu and Liu’s protocol [20] in terms of computation complexity and running time.The computation complexity is compared in terms of complex operations including pairing, scalar multiplication, and hash toG1 point. We neglect operations including ordinary hash functions, point addition, and integer computations because the running time of these operations is trivial compared with those complex operations. We compare how many complex operations are employed in every protocol. In the comparison, P stands for a pairing operation, S stands for a scalar multiplication, and H stands for a map to G1 point hash. To evaluate the running time of a protocol, we first implement the complex cryptographic operations and then add up to get the overall running time.We implement the complex operations with Miracle Version 7.0 [26]. We use the Tate pairing defined over supersingular elliptic curve E/Fp:y2=x3+x with embedding degree 2. q is a 160-bit Solinas prime q=2159+217+1 and p a 512-bit prime satisfying p+1=12qr. The evaluation is carried out in a PC with Intel Core i7-6700 CPU at 2.8 GHZ and 8.0 GB memory. The operation system is Windows 10. The operation time of every complex operation is listed in Table 1.Table 1
Operation time on different cryptographic operations (in milliseconds).
OperationPairingScalar multiplicationHash toG1 pointTime19.635.932.98The comparison results are given in Table2. From the comparison, we can see that our protocol reduces the running time by limiting the pairing operation times. Compared with Sang et al.’s protocol, the running time is reduced by 34.75%; compared with Fu-Liu’s protocol, the running time is reduced by 33.00%.Table 2
Efficiency comparison of different protocols.
ProtocolComputation complexityRunning time (in milliseconds)Sang et al.’s [19]5P + 2S + 1H112.99Fu and Liu’s [20]5P + S + 2H110.04Our protocol3P + 2S + H73.73


## 7. Conclusion

In this paper, we propose a certificateless noninteractive key exchange protocol. The protocol requires no interaction; thus, the communication delay is minimized. Moreover, the computation efficiency is improved because the pairing operation times are reduced. Compared with existing CL-NIKE protocols, our protocol improves the computation efficiency by at least 33.00%. The security of the protocol is based on the bilinear Diffie–Hellman problem and could be proved in the random oracle model.



---

*Source: 8862476-2020-08-28.xml*