# An Efficient Pairing-Free Certificateless Searchable Public Key Encryption for Cloud-Based IIoT

Authors: Mimi Ma; Min Luo; Shuqin Fan; Dengguo Feng
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

The Industrial Internet of Things (IIoT), as a special form of Internet of Things (IoT), has great potential in realizing intelligent transformation and industrial resource utilization. However, there are security and privacy concerns about industrial data, which is shared on an open channel via sensor devices. To address these issues, many searchable encryption schemes have been presented to provide both data privacy-protection and data searchability. However, due to the use of expensive pairing operations, most previous schemes were inefficient. Recently, a certificateless searchable public-key encryption (CLSPE) scheme was designed by Lu et al. to remove the pairing operation. Unfortunately, we find that Lu et al.’s scheme is vulnerable to user impersonation attacks. To enhance the security, a new pairing-free dual-server CLSPE (DS-CLSPE) scheme for cloud-based IIoT deployment is designed in this paper. In addition, we provide security and efficiency analysis for DS-CLSPE. The analysis results show that DS-CLSPE can resist chosen keyword attacks (CKA) and has better efficiency than other related schemes.


---

## Body

## 1. Introduction

The gradual maturity of communication technology, especially the emergence of the 5-th generation wireless systems, has greatly promoted the popularization of IoT, which connects everything to the Internet for intelligent identification, tracking, monitoring, etc. [1–3]. Industrial IoT (IIoT) is one of the main application directions of IoT. It can collect the industrial data in real-time via various sensing devices (e.g., global positioning system and radio frequency identification), realize the optimal utilization of resources, improve the quality, and reduce the cost of the product through further analyzing those collected data [4].IIoT provides new technological guidance for the development of industry and has great application potential. Nowadays, the IIoT market is expanding rapidly [5]. Meanwhile, the number of IIoT devices will also grow several times, inevitably leading to an explosion of the collected industrial data. In order to effectively manage and utilize these big data, users are more willing to outsource the data to the cloud server provider (CSP), which has powerful data storage and analytical capabilities [6]. In a cloud-based IIoT setting, as presented in Figure 1, massive industrial data is collected through sensor devices and transmitted to the CSP in real-time via the Internet. The CSP further analyzes and mines these data to provide better intelligent services for industrial sectors such as intelligent logistics and manufacturing.Figure 1
Cloud-based IIoT architecture.Users enjoy various convenient services offered by CSP; however, their data security and privacy are seriously threatened [7–10]. One reason is that their data is transmitted on an open channel, so an adversary can eavesdrop on the transmitted data to obtain information about an enterprise’s production or operations [11]. The other reason is that they will not be able to physically control the outsourced data nor will they be able to fully trust the CSP. For example, the CSP may exploit users’ outsourced data to make illegal profits or carry out other malicious acts, such as tampering and deleting. Once the confidential data is eavesdropped or destroyed, it may cause unpredictable damage to an enterprise (e.g., huge economic losses). Overall, it is urgent to establish a practical mechanism with security and privacy preservation for IIoT data utilization and management.Encryption is the most direct approach to guarantee data privacy. Users can first encrypt the confidential data and then submit the ciphertext to CSP. Although traditional encryption is effective in preserving the privacy of IIoT data, it also incurs some troubles in data utilizations, especially the problem of searching over encrypted data. Since the original data structure will be changed once it is encrypted, the search algorithms for plaintext will not be feasible for the encrypted data. To address this issue, the searchable encryption (SE) technology has emerged, which supports search over ciphertext according to keywords [12, 13]. The first symmetric SE (SSE) scheme was presented in [12]. However, SSE suffers from the troublesome key distribution. To resolve this problem, a SE scheme based on a public-key cryptosystem (SPE) was designed in [13]. Since then, various SPE schemes have been designed [14–17]. However, these SPE schemes face cumbersome certificate management or key escrow burden since the inherent designing structure based on public key infrastructure (PKI) and identity-based cryptosystem. The CLSPE schemes [18–20] can overcome these cumbersome burdens. However, most of the previous CLSPE schemes were computationally expensive since the use of many complex pairing operations. Recently, Lu and Li [21] presented a new CLSPE scheme without pairing operation. Unfortunately, we analyze their scheme suffer from user impersonation attack. To improve the security, we design a new DS-CLSPE scheme without pairing for cloud-based IIoT deployment.


### 1.1. Related Work

The SE technology provides the functionality of searching over ciphertext without losing the confidentiality of original data. The first concrete SE scheme was presented in [12], which was built on a symmetric cryptosystem. Later, various SSE schemes have been designed. A SSE scheme with verifiable functionality (VSSE) was presented in [22], which can both protect data privacy and provide the verifiability. Recently, Zuo et al. [23] gave two dynamic SSE schemes (i.e., Scheme-A and Scheme-B), which support range queries. The former scheme has forward security property but imposes a heavy storage cost on the client, and the latter scheme reduces the client’s storage but loses the forward security. Later, a novel VSSE scheme with forward security was presented in [24]. However, all SSE schemes face the complex key management issue.To avoid the key management issue, the concept of SPE was introduced in [13]. A SPE system contains three participants: cloud server (CS), data sender (DS), and data receiver (DR). DS uses DR’s public key to encrypt his/her own data, including files and keywords extracted from files, and sends the encrypted data to CS. DR uses its own private key to produce a trapdoor for the keyword to be retrieved and submits the trapdoor to CS. Then, CS verifies whether the trapdoor matches the ciphertext and returns the successfully matched files to DR. Later, a SPE scheme with a designated server (dSPE) was constructed, in which only the specified server can run the test algorithm [14]. Lin et al. [25] designed a novel blockchain-based system for the secure outsourcing of bilinear pairings to remove the secure channel and the trusted server. To resist inside keyword guessing attack (IKGA), an authenticated SPE scheme was constructed in [15]. Recently, a SPE scheme with forward security was designed in [16] to resist file-injection attacks [26]. However, the above-proposed schemes are built on PKI cryptosystem; they inevitably face the complicated certificate management problem.To reduce the overhead of managing certificate, an ID-based cryptosystem was introduced, in which the participant’s public key is set to some public information (e.g., name and office number), and the private key is created by a key generation center (KGC) based on the public information [27]. A general framework for transforming a two-level anonymous ID-based encryption (IBE) scheme to an ID-based SPE (IBSPE) scheme was presented in [17]. Recently, Lu et al. [28] constructed an IBSPE with a designated server (dIBSPE), which supports conjunctive keyword search. Li et al. [29] designed two-authenticated dIBSPE schemes based on symmetric bilinear pairing and asymmetric bilinear pairing, respectively. In their schemes, any adversary cannot run the encryption algorithm to get a valid ciphertext unless it can capture the data sender’s private key, and no adversary can perform the test algorithm correctly unless it has the ability to access the specified server’s private key. Zhang et al. [30] constructed a proxy-oriented IBSPE scheme based on lattices to resist quantum computer attacks, in which the original data sender delegates his/her own data to a proxy for encryption in order to lower the computation cost of himself. However, all ID-based SPE schemes are plagued by key escrow issues.In certificateless cryptosystem (CLC), the private key of the participant is jointly created by KGC and the participant itself, which resolves the burden of key escrow and certificate management existing in PKI-based and ID-based cryptosystem [31]. Peng et al. [18] introduced SE technology into the CLC system and proposed a CLSPE scheme with a designated server (dCLSPE). To lower computation overhead in [18], Islam et al. [19] designed a new dCLSPE scheme based on the problems of CDH and BDH. He et al. [20] constructed a novel-authenticated CLSPE scheme against IKGA attacks. However, all previous CLSPE schemes involve bilinear pairing operations, which require high computation overhead. Recently, a CLSPE scheme without pairing operation is designed in [21]. Unfortunately, we analyze scheme [21] cannot resist user impersonation attacks, thus, we develop a new pairing-free CLSPE scheme.


### 1.2. Research Contributions

An efficient pairing-free DS-CLSPE scheme for cloud-based IIoT is designed in this paper. The main research contributions are listed below:(i)
First, we analyze Lu et al.’s scheme is subject to user impersonation attack, and their scheme requires a secure channel for trapdoor transmission(ii)
Second, we give the system model for DS-CLSPE and construct a new DS-CLSPE scheme, which not only eliminates the need for bilinear pairings but also removes the use of secure channel(iii)
Finally, we present a security analysis for DS-CLSPE and show it can resist the CKA attack. Furthermore, we evaluate the efficiency of DS-CLSPE in terms of computation and communication costs


### 1.3. Organization of the Paper

The following sections are arranged as below. Section2 presents some preliminary knowledge. Section 3 shows the analysis of Lu et al.’s scheme. Section 4 gives the detailed construction of our DS-CLSPE scheme. Section 5 and Section 6 show the security proof and the performance analysis of DS-CLSPE, respectively. The last section is mainly to summarize the full paper.


## 1.1. Related Work

The SE technology provides the functionality of searching over ciphertext without losing the confidentiality of original data. The first concrete SE scheme was presented in [12], which was built on a symmetric cryptosystem. Later, various SSE schemes have been designed. A SSE scheme with verifiable functionality (VSSE) was presented in [22], which can both protect data privacy and provide the verifiability. Recently, Zuo et al. [23] gave two dynamic SSE schemes (i.e., Scheme-A and Scheme-B), which support range queries. The former scheme has forward security property but imposes a heavy storage cost on the client, and the latter scheme reduces the client’s storage but loses the forward security. Later, a novel VSSE scheme with forward security was presented in [24]. However, all SSE schemes face the complex key management issue.To avoid the key management issue, the concept of SPE was introduced in [13]. A SPE system contains three participants: cloud server (CS), data sender (DS), and data receiver (DR). DS uses DR’s public key to encrypt his/her own data, including files and keywords extracted from files, and sends the encrypted data to CS. DR uses its own private key to produce a trapdoor for the keyword to be retrieved and submits the trapdoor to CS. Then, CS verifies whether the trapdoor matches the ciphertext and returns the successfully matched files to DR. Later, a SPE scheme with a designated server (dSPE) was constructed, in which only the specified server can run the test algorithm [14]. Lin et al. [25] designed a novel blockchain-based system for the secure outsourcing of bilinear pairings to remove the secure channel and the trusted server. To resist inside keyword guessing attack (IKGA), an authenticated SPE scheme was constructed in [15]. Recently, a SPE scheme with forward security was designed in [16] to resist file-injection attacks [26]. However, the above-proposed schemes are built on PKI cryptosystem; they inevitably face the complicated certificate management problem.To reduce the overhead of managing certificate, an ID-based cryptosystem was introduced, in which the participant’s public key is set to some public information (e.g., name and office number), and the private key is created by a key generation center (KGC) based on the public information [27]. A general framework for transforming a two-level anonymous ID-based encryption (IBE) scheme to an ID-based SPE (IBSPE) scheme was presented in [17]. Recently, Lu et al. [28] constructed an IBSPE with a designated server (dIBSPE), which supports conjunctive keyword search. Li et al. [29] designed two-authenticated dIBSPE schemes based on symmetric bilinear pairing and asymmetric bilinear pairing, respectively. In their schemes, any adversary cannot run the encryption algorithm to get a valid ciphertext unless it can capture the data sender’s private key, and no adversary can perform the test algorithm correctly unless it has the ability to access the specified server’s private key. Zhang et al. [30] constructed a proxy-oriented IBSPE scheme based on lattices to resist quantum computer attacks, in which the original data sender delegates his/her own data to a proxy for encryption in order to lower the computation cost of himself. However, all ID-based SPE schemes are plagued by key escrow issues.In certificateless cryptosystem (CLC), the private key of the participant is jointly created by KGC and the participant itself, which resolves the burden of key escrow and certificate management existing in PKI-based and ID-based cryptosystem [31]. Peng et al. [18] introduced SE technology into the CLC system and proposed a CLSPE scheme with a designated server (dCLSPE). To lower computation overhead in [18], Islam et al. [19] designed a new dCLSPE scheme based on the problems of CDH and BDH. He et al. [20] constructed a novel-authenticated CLSPE scheme against IKGA attacks. However, all previous CLSPE schemes involve bilinear pairing operations, which require high computation overhead. Recently, a CLSPE scheme without pairing operation is designed in [21]. Unfortunately, we analyze scheme [21] cannot resist user impersonation attacks, thus, we develop a new pairing-free CLSPE scheme.


## 1.2. Research Contributions

An efficient pairing-free DS-CLSPE scheme for cloud-based IIoT is designed in this paper. The main research contributions are listed below:(i)
First, we analyze Lu et al.’s scheme is subject to user impersonation attack, and their scheme requires a secure channel for trapdoor transmission(ii)
Second, we give the system model for DS-CLSPE and construct a new DS-CLSPE scheme, which not only eliminates the need for bilinear pairings but also removes the use of secure channel(iii)
Finally, we present a security analysis for DS-CLSPE and show it can resist the CKA attack. Furthermore, we evaluate the efficiency of DS-CLSPE in terms of computation and communication costs


## 1.3. Organization of the Paper

The following sections are arranged as below. Section2 presents some preliminary knowledge. Section 3 shows the analysis of Lu et al.’s scheme. Section 4 gives the detailed construction of our DS-CLSPE scheme. Section 5 and Section 6 show the security proof and the performance analysis of DS-CLSPE, respectively. The last section is mainly to summarize the full paper.


## 2. Preliminaries

We first present the complexity assumptions used in this paper and then give the system model and formal definition of DS-CLSPE.


### 2.1. Complexity Assumptions

SupposeG denotes a q-order cyclic group, and the point P∈G denotes a generator.


#### 2.1.1. Computational Diffie-Hellman (CDH) Assumption

Given three pointsP, aP, bP∈G (a, b∈ℤq∗ are unknown numbers), to figure out abP.


### 2.2. System Model

As presented in Figure2, a DS-CLSPE system contains five participants: data sender (DS), data receiver (DR), KGC, front server (FS), and back server (BS). The responsibilities of each participant are described below.
(i)
KGC is responsible for generating system parameters and participants’ partial keys(ii)
DS encrypts his/her own data and then outsources the encrypted data to FS and BS(iii)
DR submits a trapdoor to FS for querying the encrypted data(iv)
FS generates an intermediate testing-state ciphertextCITS according to the received trapdoor and submits CITS to BS(v)
BS generates the final test results according toCITS and returns the test results to DRFigure 2
The system model for DS-CLSPE.


### 2.3. Formal Definition

A DS-CLSPE scheme contains the following algorithms.(i)
Setup(λ): this algorithm is implemented by KGC. Inputs a security parameter λ, returns the system master key s and public parameters parm(ii)
PartialKeyGen(parm,s,IDi): this algorithm is performed by KGC. Inputs parm, s, and the identity IDii∈DR,FS,BS, outputs the partial key pair Ti,di for the corresponding participant(iii)
KeyGen(parm,IDi,Ti,di): each participant generates its own full public/private keys PKi/SKi by performing this algorithm(iv)
Encrypt(parm,w,IDi,PKi): DS executes this algorithm to generate the ciphertext Cw for keyword w(v)
Trapdoor(parm,w′,SKDR,PKFS,PKBS): DR performs this algorithm to obtain the trapdoor Tw′ for w′.(vi)
FrontTest(parm,Cw,Tw′,SKFS): FS performs this algorithm to generate an intermediate testing-state CITS(vii)
BackTest(parm,CITS,SKBS): this algorithm is performed by BS. Inputs parm, CITS, SKBS, outputs “1” if the test succeeds and “0” otherwise


## 2.1. Complexity Assumptions

SupposeG denotes a q-order cyclic group, and the point P∈G denotes a generator.


### 2.1.1. Computational Diffie-Hellman (CDH) Assumption

Given three pointsP, aP, bP∈G (a, b∈ℤq∗ are unknown numbers), to figure out abP.


## 2.1.1. Computational Diffie-Hellman (CDH) Assumption

Given three pointsP, aP, bP∈G (a, b∈ℤq∗ are unknown numbers), to figure out abP.


## 2.2. System Model

As presented in Figure2, a DS-CLSPE system contains five participants: data sender (DS), data receiver (DR), KGC, front server (FS), and back server (BS). The responsibilities of each participant are described below.
(i)
KGC is responsible for generating system parameters and participants’ partial keys(ii)
DS encrypts his/her own data and then outsources the encrypted data to FS and BS(iii)
DR submits a trapdoor to FS for querying the encrypted data(iv)
FS generates an intermediate testing-state ciphertextCITS according to the received trapdoor and submits CITS to BS(v)
BS generates the final test results according toCITS and returns the test results to DRFigure 2
The system model for DS-CLSPE.


## 2.3. Formal Definition

A DS-CLSPE scheme contains the following algorithms.(i)
Setup(λ): this algorithm is implemented by KGC. Inputs a security parameter λ, returns the system master key s and public parameters parm(ii)
PartialKeyGen(parm,s,IDi): this algorithm is performed by KGC. Inputs parm, s, and the identity IDii∈DR,FS,BS, outputs the partial key pair Ti,di for the corresponding participant(iii)
KeyGen(parm,IDi,Ti,di): each participant generates its own full public/private keys PKi/SKi by performing this algorithm(iv)
Encrypt(parm,w,IDi,PKi): DS executes this algorithm to generate the ciphertext Cw for keyword w(v)
Trapdoor(parm,w′,SKDR,PKFS,PKBS): DR performs this algorithm to obtain the trapdoor Tw′ for w′.(vi)
FrontTest(parm,Cw,Tw′,SKFS): FS performs this algorithm to generate an intermediate testing-state CITS(vii)
BackTest(parm,CITS,SKBS): this algorithm is performed by BS. Inputs parm, CITS, SKBS, outputs “1” if the test succeeds and “0” otherwise


## 3. Weakness of Lu et al.’s Scheme

We first present Lu et al.’s scheme and then analyze its security weakness.


### 3.1. Review of Lu et al.’s Scheme

The detailed construction of Lu et al.’s scheme is as follows.(i)
Setup(λ): suppose q is a large prime number and G is a group with order q. P denotes a generator selected from G, and h1:0,1∗⟶ℤq∗, h2:0,1∗⟶ℤq∗, and h3:G⟶ℤq∗ denote three different hash functions. KGC performs this algorithm as follows
(1)
Selectss∈ℤq∗ at random(2)
CalculatesPpub=sP(3)
Publishesparm=G,P,Ppub,q,h1,h2,h3 and keeps s in secret(ii)
PartialKeyGen(parm,s,IDDR): KGC selects tDR∈ℤq∗, computes TDR=tDRP, dDR=tDR+sh1IDDR, and sends the partial key pair TDR,dDR to the receiver(iii)
KeyGen(parm,IDDR,TDR,dDR): the receiver picks xDR∈ℤq∗, calculates PDR=xDRP, and sets PKDR=TDR,PDR, SKDR=dDR,xDR as his/her own public/private keys(iv)
Encrypt(parm,w,PKDR): the sender randomly chooses r∈ℤq∗, calculates Cw1=rP and
(1)Cw2=h3rh2wQDR,here QDR=TDR+PDR+h1IDDRPpub, and sets the ciphertext Cw=Cw1,Cw2.(v)
Trapdoor(parm,w′,SKDR): the receiver computes
(2)Tw′=dDR+xDRh2w′.(vi)
Test(parm,Cw,Tw′): given Cw and Tw′, the server checks
(3)Cw2=?h3Tw′Cw1.If this equation holds, returns “1”; Otherwise, returns “0”.


### 3.2. Attack on Lu et al.’s Scheme

Lu et al.’s scheme cannot prevent user impersonation attack launched byTypeI adversary A1. During the attack, A1 can first forge the private key of the receiver IDDR and then impersonate IDDR to calculate a trapdoor Tw for a challenge keyword w using the forged private key. The detail attack is presented below.
(i)
Setup: the challenger C generates parm,s by performing the Setup algorithm(ii)
Queries: A1 with identity IDA1 can ask the following queries
(1)
Extract Partial Private Key Query: if A1 submits this query, then C returns dA1,TA1 to A1, where dA1=tA1+sh1IDA1 and TA1=tA1PUpon receivingdA1,TA1, A1 can forge the partial key pair dDR,TDR of the receiver IDDR as follows:
(4)TDR∗=TA1·h1IDDR·h1IDA1−1,(5)dDR∗=dA1·h1IDDR·h1IDA1−1.(2)
Replace Public Key Query: A1 selects xDR∗∈ℤq∗ randomly and computes PDR∗=xDR∗P. Then, A1 submits this query with IDDR,PKDR∗, here PKDR∗=TDR∗,PDR∗. C will set PKDR⟵PKDR∗(iii)
Forge Trapdoor: once A1 has successfully forged dDR∗ and replaced PKDR, it can forge a trapdoor Tw0 for a keyword w0 with respect to the identity IDDR as below:
(6)Tw0=dDR∗+xDR∗h2w0.(iv)
Challenge: A1 returns the keywords w0,w1 and the identity IDDR as challenge target. Then C picks up μ∈0,1 randomly and returns Cwμ⟵Encryptparm,wμ,PKDR to A1Upon receivingCwμ, A1 performs Test algorithm and gets τ⟵Testparm,Cwμ,Tw0∈0,1.(v)
Guess: A1 returns μ′=0 if τ=1; otherwise, A1 returns μ′=1. It is easy to see that μ′=μ, i.e., the advantage of A1 is always 1


## 3.1. Review of Lu et al.’s Scheme

The detailed construction of Lu et al.’s scheme is as follows.(i)
Setup(λ): suppose q is a large prime number and G is a group with order q. P denotes a generator selected from G, and h1:0,1∗⟶ℤq∗, h2:0,1∗⟶ℤq∗, and h3:G⟶ℤq∗ denote three different hash functions. KGC performs this algorithm as follows
(1)
Selectss∈ℤq∗ at random(2)
CalculatesPpub=sP(3)
Publishesparm=G,P,Ppub,q,h1,h2,h3 and keeps s in secret(ii)
PartialKeyGen(parm,s,IDDR): KGC selects tDR∈ℤq∗, computes TDR=tDRP, dDR=tDR+sh1IDDR, and sends the partial key pair TDR,dDR to the receiver(iii)
KeyGen(parm,IDDR,TDR,dDR): the receiver picks xDR∈ℤq∗, calculates PDR=xDRP, and sets PKDR=TDR,PDR, SKDR=dDR,xDR as his/her own public/private keys(iv)
Encrypt(parm,w,PKDR): the sender randomly chooses r∈ℤq∗, calculates Cw1=rP and
(1)Cw2=h3rh2wQDR,here QDR=TDR+PDR+h1IDDRPpub, and sets the ciphertext Cw=Cw1,Cw2.(v)
Trapdoor(parm,w′,SKDR): the receiver computes
(2)Tw′=dDR+xDRh2w′.(vi)
Test(parm,Cw,Tw′): given Cw and Tw′, the server checks
(3)Cw2=?h3Tw′Cw1.If this equation holds, returns “1”; Otherwise, returns “0”.


## 3.2. Attack on Lu et al.’s Scheme

Lu et al.’s scheme cannot prevent user impersonation attack launched byTypeI adversary A1. During the attack, A1 can first forge the private key of the receiver IDDR and then impersonate IDDR to calculate a trapdoor Tw for a challenge keyword w using the forged private key. The detail attack is presented below.
(i)
Setup: the challenger C generates parm,s by performing the Setup algorithm(ii)
Queries: A1 with identity IDA1 can ask the following queries
(1)
Extract Partial Private Key Query: if A1 submits this query, then C returns dA1,TA1 to A1, where dA1=tA1+sh1IDA1 and TA1=tA1PUpon receivingdA1,TA1, A1 can forge the partial key pair dDR,TDR of the receiver IDDR as follows:
(4)TDR∗=TA1·h1IDDR·h1IDA1−1,(5)dDR∗=dA1·h1IDDR·h1IDA1−1.(2)
Replace Public Key Query: A1 selects xDR∗∈ℤq∗ randomly and computes PDR∗=xDR∗P. Then, A1 submits this query with IDDR,PKDR∗, here PKDR∗=TDR∗,PDR∗. C will set PKDR⟵PKDR∗(iii)
Forge Trapdoor: once A1 has successfully forged dDR∗ and replaced PKDR, it can forge a trapdoor Tw0 for a keyword w0 with respect to the identity IDDR as below:
(6)Tw0=dDR∗+xDR∗h2w0.(iv)
Challenge: A1 returns the keywords w0,w1 and the identity IDDR as challenge target. Then C picks up μ∈0,1 randomly and returns Cwμ⟵Encryptparm,wμ,PKDR to A1Upon receivingCwμ, A1 performs Test algorithm and gets τ⟵Testparm,Cwμ,Tw0∈0,1.(v)
Guess: A1 returns μ′=0 if τ=1; otherwise, A1 returns μ′=1. It is easy to see that μ′=μ, i.e., the advantage of A1 is always 1


## 4. The Proposed DS-CLSPE Scheme

To overcome the weakness of Lu et al.’s scheme and avoid the use of bilinear pairing, we develop a new dual-server CLSPE scheme. The details are described as follows.(i)
Setup(λ): suppose q is a large prime number, G is a group with order q. Let P denote a generator of G, and h0:0,1∗×G⟶ℤq∗, h1:0,1∗×G×G⟶ℤq∗, and h2:0,1∗×0,1∗⟶ℤq∗ denote three different hash functions. KGC performs the following steps
(1)
Choosess∈ℤq∗ randomly(2)
CalculatesPpub=sP(3)
Publishesparm=P,Ppub,G,h0,h1,h2 and keeps s secretly(ii)
PartialKeyGen(parm,s,IDi): takes parm, s, and the identity IDii∈DR,FS,BS as inputs, KGC performs this algorithm as follows
(1)
Selectsti∈ℤq∗(2)
CalculatesTi=tiP, di=ti+sαimodq, where αi=h0IDi,Ti.(3)
SendsTi,di to the corresponding participant(iii)
KeyGen(parm,IDi,Ti,di): this algorithm is performed by the participant i∈DR,FS,BS as follows
(1)
Choosesxi∈ℤq∗ randomly(2)
CalculatesPi=xiP(3)
SetsPKi=Ti,Pi and SKi=di,xi(iv)
Encrypt(parm,w,IDi,PKi): given IDi, PKi=Ti,Pii∈DR,FS,BS and keyword w. DR performs the steps below to produce ciphertext Cw(1)
Selectsr∈ℤq∗ randomly(2)
CalculatesCw1=rP(3)
Calculates(7)Cw2=rQFS+rQBS+h2w,IDDRQDR,where
(8)Qi=Ti+βiPi+αiPpub,(9)αi=h0IDi,Ti,(10)βi=h1IDi,Ti,Pi.(4)
SetsCw=Cw1,Cw2The parametersQi,αi,βi can be published publicly.(v)
Trapdoor(parm,w′,SKDR,PKFS,PKBS): the receiver generates the trapdoor Tw′ of keyword w′ as below
(1)
Selectsl∈ℤq∗ randomly(2)
ComputesTw′1=lP(3)
Computes(11)Tw′2=dDR+βDRxDRh2w′,IDDRQFS+lQBS,where Qi and βi are computed as above.(4)
SendsTw′=Tw′1,Tw′2 to the front server(vi)
FrontTest(parm,Cw,Tw′,SKFS): given the ciphertext Cw and a trapdoor Tw′, the front server FS performs the following steps to generate intermediate testing-state CITS(1)
Selectsγ∈ℤq∗ randomly(2)
CalculatesC∗=dFS+βFSxFSCw1(3)
Calculates(12)C1∗=γC∗−Tw′1,(13)C2∗=γdFS+βFSxFSCw2−C∗−Tw′2.(4)
SendsCITS=C1∗,C2∗ to the back server BS(vii)
BackTest(parm,CITS,SKBS): the back server checks
(14)C2∗=?dBS+βBSxBSC1∗.If this equation holds, BS returns “1”; otherwise, returns “0”.Correctness. Suppose that w=w′, then we have
(15)C∗=dFS+βFSxFSCw1=rQFS,(16)C1∗=γC∗−Tw′1=γrQFS−lP,(17)C2∗=γdFS+βFSxFSCw2−C∗−Tw′2=γdFS+βFSxFSrQBS+h2w,IDDRQDR−Tw′2=γrdFS+βFSxFSQBS−lQBS=γrdBS+βBSxBSQFS−lQBS=γdBS+βBSxBSrQFS−lP=dBS+βBSxBSC1∗.


## 5. Security Analysis

This section first presents the security model of DS-CLSPE and then gives the formal proof of DS-CLSPE.


### 5.1. Security Model

Two types of adversaries should be considered in a certificateless cryptosystem [31, 32].Type 1.
This adversary is denoted asA1, who has no master key but can replace anyone’s public key.Type II.
This adversary is denoted asA2, who holds the master key but cannot replace anyone’s public key.As defined in scheme [33], assume that both BS and FS are honest-but-curious, and that they cannot collude. The security model of DS-CLSPE is defined by the following game, i.e., indistinguishability against CKA attack (IND-CKA), which is the interaction between an adversary A∈A1,A2 and a challenger C.Definition 1 (IND-CKA).
The DS-CLSPE scheme is said IND-CKA secure ifA’s advantage of winning in the following game is negligible.Game. This game is interacted between A and C.
(i)
Setup: C generates parm,s by executing Setup algorithm. If A=A1, C returns parm to A; otherwise (A=A2), returns both parm and s(ii)
Phase1: the following oracles can be queried by A(a)
CreateUser Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C outputs PKi directly. Otherwise, C performs the algorithm KeyGen to produce the key pair PKi,SKi and returns PKi(b)
PrivateKey Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C returns SKi; otherwise, returns ⊥(c)
PatialPrivateKey Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C returns partial private key di; otherwise, returns ⊥(d)
ReplacePublicKey Queries: if A=A1, then it can perform these queries. Upon receiving A’s query for IDi with a false public key PKi∗, C sets PKi⟵PKi∗(e)
Trapdoor Queries: if A submits this query for IDi,w, then C returns the corresponding trapdoor Tw if IDi has been created; otherwise, returns ⊥(iii)
Challenge: A selects identity IDch and keywords w0,w1 as challenge targets. C picks up σ∈0,1 at random and returns Cwσ⟵Encryptparm,wσ,IDch,PKch,PKFS,PKBS to A(iv)
Phase2: the oracles defined as in phase 1 can be continuously queried by A(v)
Guess: A returns σ′∈0,1. We say A wins the above game if σ′=σ and below conditions hold: (1) Trapdoor queries for w0 and w1 have never been submitted by A; (2) If A=A1, it has never made PrivateKey and PartialPrivateKey queries for IDch; if A=A2, it has never made PrivateKey queries for IDch (note that A2 can calculate partial private key as it knows master key).LetAdvAλ=Prσ′=σ−1/2 express A’s advantage in the above-defined game.


### 5.2. Provable Security

Theorem 2.
The DS-CLSPE scheme can achieve IND-CKA secure if the CDH problem is difficult to solve.
Theorem2 can be proofed by the two lemmas below.Lemma 3.
Let the advantage ofA1 winning the IND-CKA game be ε. Then, we can construct an algorithm C to calculate the CDH problem with advantage
(18)ε′≥εqT+qSK+qPSK+1e,where e is Euler number and qSK, qPSK, qT denote the maximum number of PrivateKey queries, PartialPrivateKey queries, and Trapdoor queries, respectively.Proof.
Letq be a large prime number. Given P,aP,bP, C’s goal is to output abP.
(i)
Setup: C generates the public parameters parm=G,P,Ppub,h0,h1,h2,q, here Ppub=aP. C selects xFS,xBS,tFS,tBS∈ℤq∗, computes PFS=xFSP, PBS=xBSP, TFS=tFSP, and TBS=tBSP, and sets PKFS=TFS,PFS, PKBS=TBS,PBS. Finally, C sends parm,PKFS,PKBS to A1(ii)
Phase1: the following oracles can be queried by A1(a)
h0Queries: a h0-list with tuples IDi,Ti,αi is maintained by C. When A1 performs h0 query for IDi,Ti, C first checks whether IDi,Ti,αi is already in h0-list. If so, C returns αi; otherwise, C selects αi∈ℤq∗ at random, adds IDi,Ti,αi into h0-list, and returns αi(b)
h1Queries: C maintains a h1-list with tuples IDi,Ti,Pi,βi. Upon receiving A1’s query for IDi,Ti,Pi, C searches IDi,Ti,Pi,βi from h1-list. If h1-list already contains the searched tuple, C outputs βi directly; otherwise, C chooses βi∈ℤq∗ at random, adds IDi,Ti,Pi,βi into h1-list, and returns βi(c)
h2Queries: C maintains a h2-list with tuples wi,IDi,h2i. Upon receiving this query for wi,IDi, C searches wi,IDi,h2i from h2-list and returns h2i directly if wi,IDi,h2i already exists in h2-list; otherwise, C selects h2i∈ℤq∗ at random, adds wi,IDi,h2i into h2-list, and returns h2i(d)
CreateUserQueries: C maintains a user-list with tuples IDi,PKi,SKi,ti,xi,coini. Upon receiving A1’s query for IDi, C searches user-list for IDi,PKi,SKi,ti,xi,coini. C outputs PKi directly if user-list already includes the searched tuple; otherwise, C tosses a coini∈0,1 at random such that Prcoini=1=δ (δ will be computed later) and executes the following steps
(1)
Ifcoini=1, C selects two random numbers ti, xi from ℤq∗, sets PKi=Ti,Pi, where Ti=tiP, Pi=xiP. C adds IDi,PKi,⊥,ti,xi,1 into user-list and returns PKi(2)
Otherwise (coini=0), C selects three numbers xi,di,αi from ℤq∗, sets SKi=di,xi and PKi=Ti,Pi, where Ti=diP−αiPpub, Pi=xiP. C adds IDi,PKi,SKi,⊥,⊥,0 into user-list, adds IDi,Ti,αi into h0-list, and returns PKi(e)
PrivateKeyQueries: when A1 submits this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If coini=0, C outputs SKi; otherwise, C aborts the game (this event is denoted as Event1).(f)
PartialPrivateKeyQueries: when A1 submits this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If coini=0, C outputs the first part of SKi, i.e., di; otherwise, C aborts the game (this event is denoted as Event2).(g)
ReplacePublicKeyQueries: when A1 submits this query with a value PKi∗, C replaces PKi with PKi∗. Note that this query implies A1 must also submit the corresponding private key SKi∗(h)
TrapdoorQueries: when A1 submits this query for w,IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list and recovers IDi,Ti,Pi,βi and wi,IDi,h2i from h1-list and h2-list, respectively. If coini=0, C chooses l∈ℤq∗ and computes Tw1=lP, Tw2=di+βixih2iQFS+lQBS, where QFS and QBS are computed as in the proposed scheme. C returns Tw=Tw1,Tw2. Otherwise, C aborts the game (this event is denoted as Event3).(iii)
Challenge: A1 outputs IDch and w0,w1. C recovers IDch,PKch,SKch,tch,xch,coinch and IDch,Tch,Pch,βch from user-list and h1-list, respectively. If coinch=1, C randomly selects σ∈0,1, Cwσ2∈G, recovers wσ,IDch,h2σ from h2-list, sets Cwσ1=bP, and returns Cwσ=Cwσ1,Cwσ2 to A1. Otherwise, C ends the game (this event is denoted as Event4).Note thatCwσ2 is implicitly defined as bQFS+bQBS+h2σQch=bTFS+βFSPFS+αFSPpub+bTBS+βBSPBS+αBSPpub+h2σTch+βchPch+αchPpub.(iv)
Phase 2: The oracles defined in phase1 can be asked continuously by A1(v)
Guess: A1 outputs σ′. If σ′=σ, then C wins in the above game
At this point,C can compute the value abP as follows: Z=αFS+αBS−1Cwσ2−h2σTch+βchPch+αchPpub−tFS+tBS+βFSxFS+βBSxBSbP=abP.Analysis.
The advantage ofC winning the game is analyzed below. C wins in above game if none of the events Eventi (i=1,2,3,4) occur.
From the above proof of Lemma3,
(19)PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=δ1−δqSK+qPSK+qT,when δ=1/qSK+qPSK+qT+1, this value is at its maximum value
(20)PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=1qSK+qPSK+qT+11−1qSK+qPSK+qT+1qSK+qPSK+qT≈1qT+qSK+qPSK+1e.
Thus,(21)ε′≥ε·PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=εqT+qSK+qPSK+1e.Lemma 4.
Letε denote the advantage of A2 winning in IND-CKA game. Then, the algorithm C can be constructed to solve the CDH problem with advantage
(22)ε′≥εqSK+qT+1e,where e, qSK, and qT are defined as Lemma 3.Proof.
Given a CDH instance, i.e.,P,aP,bP, C will try to output abP.
(i)
Setup: C selects s∈ℤq∗, calculates Ppub=sP and generates parm=q,G,P,Ppub,h0,h1,h2. Then, C selects xFS, xBS, tFS, and tBS∈ℤq∗, sets PFS=xFSP, PBS=xBSP, TFS=tFSaP, and TBS=tBSaP, and lets PKFS=TFS,PFS and PKBS=TBS,PBS. Finally, C sends parm,s,PKFS,PKBS to A2(ii)
Phase1: the following oracles can be queried by A2(a)
h0, h1, h2Queries: when A2 submits these oracle queries, C responds as defined in Lemma 3(b)
CreateUserQueries: C maintains a user-list with IDi,PKi,SKi,ti,xi,coini. Upon receiving this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If this tuple is already in user-list, C returns PKi; otherwise, C tosses coini∈0,1 randomly such that Prcoini=1=δ (δ will be computed later) and executes the following steps
(1)
Ifcoini=1, C selects ti, xi from ℤq∗, computes Ti=tiaP, Pi=xiP, and sets PKi=Ti,Pi. C adds IDi,PKi,⊥,⊥,xi,1 into user-list and returns PKi(2)
Otherwise,C selects xi,ti,αi from ℤq∗ at random, computes di=ti+sαimodq, Ti=tiP, Pi=xiP, and sets SKi=di,xi, PKi=Ti,Pi. C adds IDi,PKi,SKi,⊥,⊥,0 into user-list, adds IDi,Ti,αi into h0-list, and returns PKi(c)
PrivateKeyQueries: Upon receiving this query for IDi, C searches user-list to find IDi,PKi,SKi,ti,xi,coini. If coini=0, C outputs SKi; otherwise, C aborts the game (this event is denoted as Event1)(d)
TrapdoorQueries: when A2 submits the query for w,IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list and recovers IDi,Ti,Pi,βi and wi,IDi,h2i from h1-list and h2-list, respectively. If coini=0, C chooses l∈ℤq∗, computes Tw1=lP, Tw2=di+βixih2iQFS+lQBS, and returns Tw=Tw1,Tw2 to A2, where QFS and QBS are computed as in the proposed scheme; otherwise, C aborts the game (this event is denoted as Event2)(iii)
Challenge: A2 outputs IDch and w0,w1. C recovers IDch,PKch,SKch,tch,xch,coinch from user-list. If coinch=1, C randomly selects σ∈0,1, Cwσ2∈G and recovers wσ,IDch,h2σ from h2-list. C sets Cwσ1=bP and returns Cwσ=Cwσ1,Cwσ2 to A2. Otherwise, C aborts the game (this event is denoted as Event3)
Note thatCwσ2 is implicitly defined as bQFS+bQBS+h2σQch=bTFS+βFSPFS+αFSPpub+bTBS+βBSPBS+αBSPpub+h2σTch+βchPch+αchPpub.
(iv)
Phase2: the oracles defined in phase 1 can be continuously accessed by A2(v)
Guess: A2 returns σ′. If σ′=σ, then C wins in the game
At this point,C can compute abP as below: Z=tFS+tBS−1·Cwσ2−h2σTch+βchPch+αchPpub−βFSxFS+βBSxBS+αFSs+αBSsbP=abP.Analysis.
Now let us analyzeC’s advantage in winning the above game. C will win the game if Event1, Event2, and Event3 do not occur.
From the above proof of Lemma4,
(23)PrEvent1¯∧Event2¯∧Event3¯=δ·1−δqSK+qT,when δ=1/qSK+qT+1, PrEvent1¯∧Event2¯∧Event3¯ takes its maximum value
(24)PrEvent1¯∧Event2¯∧Event3¯=1qSK+qT+11−1qSK+qT+1qSK+qT≈1qSK+qT+1e.
Then, we have(25)ε′≥ε·PrEvent1¯∧Event2¯∧Event3¯=εqSK+qT+1e.


## 5.1. Security Model

Two types of adversaries should be considered in a certificateless cryptosystem [31, 32].Type 1.
This adversary is denoted asA1, who has no master key but can replace anyone’s public key.Type II.
This adversary is denoted asA2, who holds the master key but cannot replace anyone’s public key.As defined in scheme [33], assume that both BS and FS are honest-but-curious, and that they cannot collude. The security model of DS-CLSPE is defined by the following game, i.e., indistinguishability against CKA attack (IND-CKA), which is the interaction between an adversary A∈A1,A2 and a challenger C.Definition 1 (IND-CKA).
The DS-CLSPE scheme is said IND-CKA secure ifA’s advantage of winning in the following game is negligible.Game. This game is interacted between A and C.
(i)
Setup: C generates parm,s by executing Setup algorithm. If A=A1, C returns parm to A; otherwise (A=A2), returns both parm and s(ii)
Phase1: the following oracles can be queried by A(a)
CreateUser Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C outputs PKi directly. Otherwise, C performs the algorithm KeyGen to produce the key pair PKi,SKi and returns PKi(b)
PrivateKey Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C returns SKi; otherwise, returns ⊥(c)
PatialPrivateKey Queries: upon receiving this query for IDi, C checks whether IDi has been created. If so, C returns partial private key di; otherwise, returns ⊥(d)
ReplacePublicKey Queries: if A=A1, then it can perform these queries. Upon receiving A’s query for IDi with a false public key PKi∗, C sets PKi⟵PKi∗(e)
Trapdoor Queries: if A submits this query for IDi,w, then C returns the corresponding trapdoor Tw if IDi has been created; otherwise, returns ⊥(iii)
Challenge: A selects identity IDch and keywords w0,w1 as challenge targets. C picks up σ∈0,1 at random and returns Cwσ⟵Encryptparm,wσ,IDch,PKch,PKFS,PKBS to A(iv)
Phase2: the oracles defined as in phase 1 can be continuously queried by A(v)
Guess: A returns σ′∈0,1. We say A wins the above game if σ′=σ and below conditions hold: (1) Trapdoor queries for w0 and w1 have never been submitted by A; (2) If A=A1, it has never made PrivateKey and PartialPrivateKey queries for IDch; if A=A2, it has never made PrivateKey queries for IDch (note that A2 can calculate partial private key as it knows master key).LetAdvAλ=Prσ′=σ−1/2 express A’s advantage in the above-defined game.


## 5.2. Provable Security

Theorem 2.
The DS-CLSPE scheme can achieve IND-CKA secure if the CDH problem is difficult to solve.
Theorem2 can be proofed by the two lemmas below.Lemma 3.
Let the advantage ofA1 winning the IND-CKA game be ε. Then, we can construct an algorithm C to calculate the CDH problem with advantage
(18)ε′≥εqT+qSK+qPSK+1e,where e is Euler number and qSK, qPSK, qT denote the maximum number of PrivateKey queries, PartialPrivateKey queries, and Trapdoor queries, respectively.Proof.
Letq be a large prime number. Given P,aP,bP, C’s goal is to output abP.
(i)
Setup: C generates the public parameters parm=G,P,Ppub,h0,h1,h2,q, here Ppub=aP. C selects xFS,xBS,tFS,tBS∈ℤq∗, computes PFS=xFSP, PBS=xBSP, TFS=tFSP, and TBS=tBSP, and sets PKFS=TFS,PFS, PKBS=TBS,PBS. Finally, C sends parm,PKFS,PKBS to A1(ii)
Phase1: the following oracles can be queried by A1(a)
h0Queries: a h0-list with tuples IDi,Ti,αi is maintained by C. When A1 performs h0 query for IDi,Ti, C first checks whether IDi,Ti,αi is already in h0-list. If so, C returns αi; otherwise, C selects αi∈ℤq∗ at random, adds IDi,Ti,αi into h0-list, and returns αi(b)
h1Queries: C maintains a h1-list with tuples IDi,Ti,Pi,βi. Upon receiving A1’s query for IDi,Ti,Pi, C searches IDi,Ti,Pi,βi from h1-list. If h1-list already contains the searched tuple, C outputs βi directly; otherwise, C chooses βi∈ℤq∗ at random, adds IDi,Ti,Pi,βi into h1-list, and returns βi(c)
h2Queries: C maintains a h2-list with tuples wi,IDi,h2i. Upon receiving this query for wi,IDi, C searches wi,IDi,h2i from h2-list and returns h2i directly if wi,IDi,h2i already exists in h2-list; otherwise, C selects h2i∈ℤq∗ at random, adds wi,IDi,h2i into h2-list, and returns h2i(d)
CreateUserQueries: C maintains a user-list with tuples IDi,PKi,SKi,ti,xi,coini. Upon receiving A1’s query for IDi, C searches user-list for IDi,PKi,SKi,ti,xi,coini. C outputs PKi directly if user-list already includes the searched tuple; otherwise, C tosses a coini∈0,1 at random such that Prcoini=1=δ (δ will be computed later) and executes the following steps
(1)
Ifcoini=1, C selects two random numbers ti, xi from ℤq∗, sets PKi=Ti,Pi, where Ti=tiP, Pi=xiP. C adds IDi,PKi,⊥,ti,xi,1 into user-list and returns PKi(2)
Otherwise (coini=0), C selects three numbers xi,di,αi from ℤq∗, sets SKi=di,xi and PKi=Ti,Pi, where Ti=diP−αiPpub, Pi=xiP. C adds IDi,PKi,SKi,⊥,⊥,0 into user-list, adds IDi,Ti,αi into h0-list, and returns PKi(e)
PrivateKeyQueries: when A1 submits this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If coini=0, C outputs SKi; otherwise, C aborts the game (this event is denoted as Event1).(f)
PartialPrivateKeyQueries: when A1 submits this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If coini=0, C outputs the first part of SKi, i.e., di; otherwise, C aborts the game (this event is denoted as Event2).(g)
ReplacePublicKeyQueries: when A1 submits this query with a value PKi∗, C replaces PKi with PKi∗. Note that this query implies A1 must also submit the corresponding private key SKi∗(h)
TrapdoorQueries: when A1 submits this query for w,IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list and recovers IDi,Ti,Pi,βi and wi,IDi,h2i from h1-list and h2-list, respectively. If coini=0, C chooses l∈ℤq∗ and computes Tw1=lP, Tw2=di+βixih2iQFS+lQBS, where QFS and QBS are computed as in the proposed scheme. C returns Tw=Tw1,Tw2. Otherwise, C aborts the game (this event is denoted as Event3).(iii)
Challenge: A1 outputs IDch and w0,w1. C recovers IDch,PKch,SKch,tch,xch,coinch and IDch,Tch,Pch,βch from user-list and h1-list, respectively. If coinch=1, C randomly selects σ∈0,1, Cwσ2∈G, recovers wσ,IDch,h2σ from h2-list, sets Cwσ1=bP, and returns Cwσ=Cwσ1,Cwσ2 to A1. Otherwise, C ends the game (this event is denoted as Event4).Note thatCwσ2 is implicitly defined as bQFS+bQBS+h2σQch=bTFS+βFSPFS+αFSPpub+bTBS+βBSPBS+αBSPpub+h2σTch+βchPch+αchPpub.(iv)
Phase 2: The oracles defined in phase1 can be asked continuously by A1(v)
Guess: A1 outputs σ′. If σ′=σ, then C wins in the above game
At this point,C can compute the value abP as follows: Z=αFS+αBS−1Cwσ2−h2σTch+βchPch+αchPpub−tFS+tBS+βFSxFS+βBSxBSbP=abP.Analysis.
The advantage ofC winning the game is analyzed below. C wins in above game if none of the events Eventi (i=1,2,3,4) occur.
From the above proof of Lemma3,
(19)PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=δ1−δqSK+qPSK+qT,when δ=1/qSK+qPSK+qT+1, this value is at its maximum value
(20)PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=1qSK+qPSK+qT+11−1qSK+qPSK+qT+1qSK+qPSK+qT≈1qT+qSK+qPSK+1e.
Thus,(21)ε′≥ε·PrEvent1¯∧Event2¯∧Event3¯∧Event4¯=εqT+qSK+qPSK+1e.Lemma 4.
Letε denote the advantage of A2 winning in IND-CKA game. Then, the algorithm C can be constructed to solve the CDH problem with advantage
(22)ε′≥εqSK+qT+1e,where e, qSK, and qT are defined as Lemma 3.Proof.
Given a CDH instance, i.e.,P,aP,bP, C will try to output abP.
(i)
Setup: C selects s∈ℤq∗, calculates Ppub=sP and generates parm=q,G,P,Ppub,h0,h1,h2. Then, C selects xFS, xBS, tFS, and tBS∈ℤq∗, sets PFS=xFSP, PBS=xBSP, TFS=tFSaP, and TBS=tBSaP, and lets PKFS=TFS,PFS and PKBS=TBS,PBS. Finally, C sends parm,s,PKFS,PKBS to A2(ii)
Phase1: the following oracles can be queried by A2(a)
h0, h1, h2Queries: when A2 submits these oracle queries, C responds as defined in Lemma 3(b)
CreateUserQueries: C maintains a user-list with IDi,PKi,SKi,ti,xi,coini. Upon receiving this query for IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list. If this tuple is already in user-list, C returns PKi; otherwise, C tosses coini∈0,1 randomly such that Prcoini=1=δ (δ will be computed later) and executes the following steps
(1)
Ifcoini=1, C selects ti, xi from ℤq∗, computes Ti=tiaP, Pi=xiP, and sets PKi=Ti,Pi. C adds IDi,PKi,⊥,⊥,xi,1 into user-list and returns PKi(2)
Otherwise,C selects xi,ti,αi from ℤq∗ at random, computes di=ti+sαimodq, Ti=tiP, Pi=xiP, and sets SKi=di,xi, PKi=Ti,Pi. C adds IDi,PKi,SKi,⊥,⊥,0 into user-list, adds IDi,Ti,αi into h0-list, and returns PKi(c)
PrivateKeyQueries: Upon receiving this query for IDi, C searches user-list to find IDi,PKi,SKi,ti,xi,coini. If coini=0, C outputs SKi; otherwise, C aborts the game (this event is denoted as Event1)(d)
TrapdoorQueries: when A2 submits the query for w,IDi, C searches IDi,PKi,SKi,ti,xi,coini from user-list and recovers IDi,Ti,Pi,βi and wi,IDi,h2i from h1-list and h2-list, respectively. If coini=0, C chooses l∈ℤq∗, computes Tw1=lP, Tw2=di+βixih2iQFS+lQBS, and returns Tw=Tw1,Tw2 to A2, where QFS and QBS are computed as in the proposed scheme; otherwise, C aborts the game (this event is denoted as Event2)(iii)
Challenge: A2 outputs IDch and w0,w1. C recovers IDch,PKch,SKch,tch,xch,coinch from user-list. If coinch=1, C randomly selects σ∈0,1, Cwσ2∈G and recovers wσ,IDch,h2σ from h2-list. C sets Cwσ1=bP and returns Cwσ=Cwσ1,Cwσ2 to A2. Otherwise, C aborts the game (this event is denoted as Event3)
Note thatCwσ2 is implicitly defined as bQFS+bQBS+h2σQch=bTFS+βFSPFS+αFSPpub+bTBS+βBSPBS+αBSPpub+h2σTch+βchPch+αchPpub.
(iv)
Phase2: the oracles defined in phase 1 can be continuously accessed by A2(v)
Guess: A2 returns σ′. If σ′=σ, then C wins in the game
At this point,C can compute abP as below: Z=tFS+tBS−1·Cwσ2−h2σTch+βchPch+αchPpub−βFSxFS+βBSxBS+αFSs+αBSsbP=abP.Analysis.
Now let us analyzeC’s advantage in winning the above game. C will win the game if Event1, Event2, and Event3 do not occur.
From the above proof of Lemma4,
(23)PrEvent1¯∧Event2¯∧Event3¯=δ·1−δqSK+qT,when δ=1/qSK+qT+1, PrEvent1¯∧Event2¯∧Event3¯ takes its maximum value
(24)PrEvent1¯∧Event2¯∧Event3¯=1qSK+qT+11−1qSK+qT+1qSK+qT≈1qSK+qT+1e.
Then, we have(25)ε′≥ε·PrEvent1¯∧Event2¯∧Event3¯=εqSK+qT+1e.


## 6. Performance Analysis

This section mainly compares the computation/communication costs of DS-CLSPE with that of Lu and Li [21] and Peng et al. [18]. Let p, q be 512-bit and 160-bit prime numbers, respectively. G is a cyclic group with order q, which is generated by a point on a super-singular elliptic curve EFp. For the convenience of comparison, Table 1 presents the definition of some symbols.Table 1
Notions for some basic operations.
SymbolsDefinitionTsmRuntime for a scalar multiplication inGTmmRuntime for a modular multiplication inℤq∗TbpRuntime for a bilinear pairingTpaRuntime for a point addition inGTHRuntime for a map-to-point hashGThe bit-size of a point inGℤqThe bit-size of a number inℤqPKThe bit-size ofPKCThe bit-size of ciphertextTThe bit-size of trapdoorWe evaluate the running time of the above basic operations using the MIRACL library [34] and performing on a personal computer (Processor: i5-8250U 1.60 GHz; Memory: 8 GB; Operating system: Win10). The evaluation result shows that Tsm=4.800 ms, Tmm=0.003 ms, Tbp=13.144 ms, TH=12.082 ms, Tpa=0.025 ms. Furthermore, the result indicates that the operations of TH and Tbp consume much more time than other operations. Therefore, we should minimize or even avoid using these time-consuming operations to enhance the efficiency of the designed scheme.To compare the computation costs, we analyze the proposed DS-CLSPE scheme and schemes [18, 21] in terms of four phases: KenGen, Encrypt, Trapdoor, and Test. Table 2 and Figure 3 present the specific comparison results. In addition, the communication costs of DS-CLSPE and schemes [18, 21] are also presented in Table 2.Table 2
The performance comparison.
SchemesComputation cost (ms)Communication cost (bit)KeyGenEncryptTrapdoorTestPKCTLu and Li [21]2Tsm+Tmm3Tsm+TmmTmmTsm2GG+ℤqℤqPeng et al. [18]8Tsm+2TH4Tsm+3TH+3Tbp3Tsm+THTsm+2Tpa+Tbp4GG+ℤq3GDS-CLSPE6Tsm10Tsm+8Tpa3Tsm+Tpa4Tsm+3Tpa6G2G2GFigure 3
Computation cost comparison.From Table2 and Figure 3, the efficiency of DS-CLSPE is slightly worse than the scheme [21], but DS-CLSPE avoids the security flaws that existed in the scheme [21]. The data security is a primary concern in practical application, so DS-CLSPE is more practical. And in comparison with scheme [18], DS-CLSPE has better performance.


## 7. Conclusion

As the maturity of IoT and the popularization of sensor devices, IIoT has attracted widespread attention, which can provide users with real-time and reliable intelligent services by collecting and analyzing massive industrial data via the IoT devices. However, some sensitive information may be involved in industrial data, so data security is concerned. To protect data privacy, Lu et al. designed a CLSPE scheme without bilinear pairing operation. Unfortunately, we analyze that their CLSPE scheme cannot prevent user impersonation attacks. To resolve the security flaws, we design an improved pairing-free dual-server CLSPE scheme, i.e., DS-CLSPE. The formal security proof shows that DS-CLSPE can realize IND-CKA security. Additionally, we evaluate the efficiency of DS-CLSPE, and evaluation results indicate the proposed scheme has better efficiency.



---

*Source: 8850520-2020-12-21.xml*