# A Secure Ciphertext Retrieval Scheme against Insider KGAs for Mobile Devices in Cloud Storage

Authors: Run Xie; Chanlian He; Dongqing Xie; Chongzhi Gao; Xiaojun Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the advent of cloud computing, data privacy has become one of critical security issues and attracted much attention as more and more mobile devices are relying on the services in cloud. To protect data privacy, users usually encrypt their sensitive data before uploading to cloud servers, which renders the data utilization to be difficult. The ciphertext retrieval is able to realize utilization over encrypted data and searchable public key encryption is an effective way in the construction of encrypted data retrieval. However, the previous related works have not paid much attention to the design of ciphertext retrieval schemes that are secure against inside keyword-guessing attacks (KGAs). In this paper, we first construct a new architecture to resist inside KGAs. Moreover we present an efficient ciphertext retrieval instance with a designated tester (dCRKS) based on the architecture. This instance is secure under the inside KGAs. Finally, security analysis and efficiency comparison show that the proposal is effective for the retrieval of encrypted data in cloud computing.


---

## Body

## 1. Introduction

With the development and deployment of cloud computing, more and more mobile devices are connected to the cloud and receiving services provided by the cloud servers. Cloud storage service is one of the most critical applications of cloud computing, which offers great convenience to users, including the storage of data and sharing of data [1]. However, the cloud service providers are usually cannot be completely trusted because they are managed and controlled by a third party such as Google or Amazon. Thus, the users have to take the risk that the cloud servers may find and leak their sensitive information.To tackle the challenge of security in cloud storage, a lot of research has been performed to address the security and privacy issues in cloud computing, such as the cloud data access control [2–4], cloud data outsourcing computation [5–8], and privacy in data processing [9–13].To protect data privacy, data are usually encrypted before they are uploaded to the cloud server. Nevertheless, this way generates the new obstacles that the cloud server is not able to carry out data retrieval over ciphertext data [14]. When users would like to access the part of encrypted data, they have to get entire data back or share the keys with the cloud server. As a result, users have to pay more for the bandwidth or give up their data privacy.To overcome this obstacle, the concept of searchable encryption [15] was first proposed by Song et al. at 2000. Meanwhile, based on symmetric encryption, they proposed the keyword search scheme based on symmetric encryption, namely, Searchable Symmetric Encryption (abbreviation SSE). The searchable encryption permits users to retrieve a particular keyword over encrypted data by sending a trapdoor to the cloud server. However, the SSE involves detailed secret key management.To overcome weakness and improve security, a new searchable encryption primitive was presented by Boneh and Boyen, which is called Public key Encryption with Keyword Search (PEKS in short) [16]. In their solution, with public information, the sender can encrypt the keyword associated with encrypted data and store its ciphertext to cloud server. To achieve keyword retrieval over the encrypted data, the receiver creates a trapdoor corresponding to the keyword, then he delivers the trapdoor to server. By the testing procedure, the server can find the ciphertext of keyword associated with the trapdoor. Then it sends corresponding data to receiver. Yet, there is the requirement of secure channel in their PEKS [16]. Usually, it is difficult to fulfill this requirement. This weakness limits the applications of their scheme. Following Boneh’s PEKS, Baek et al. presented a new PEKS solution, which is called Secure Channel Free Public Key Encryption with Keyword Search [17] (denoted as SCF-PEKS). However, Baek’s scheme was proved to be insecure by Yau et al. [18] with the following reasons. When the outside adversary acquires a trapdoor in channel, he can launch keyword-guessing attacks. This attack is called outside KGAs. So far, many of existing solutions concentrate on building up the security to resist outside KGAs [19–23]. Only a few schemes [24–28] are secure against this attacks.Additionally, the most difficult issue is to resist keyword-guessing attacks launched by the cloud server, namely, inside KGAs. The inside KGAs are that the test server launched keyword-guessing attacks. Actually, such kind of attack also has been considered in deduplication system [30] and other security protocols [3, 31–33]. Specifically, the malicious server can create their ciphertext since the production of a PEKS ciphertext of keyword involves only public parameters. Given the trapdoor, the malicious cloud server can perform the test procedure with the guessing keyword. Therefore the server is able to know if the guessing keyword matches given trapdoor. Repeating guessing-then-testing process, the server can find the correct keyword. Because of the weakness of the small size of keyword space, this attack is available. Based on dual-server, Chen et al. [34] presented a new PEKS scheme which is considered to be secure against insider KGAs. However, in their solution, the front server can test whether the ciphertext of keyword relates to given trapdoor. Hence, under the original framework of [16], designing a secure scheme against inside KGAs is out of the question.Recently, a new scheme [29] has been proposed by Jiang et al. based on slightly different architecture. With the aid of TTP (trusted third party), their solution can resist inside KGAs. In [29], TTP delivers its secret key to the sender from a safe channel. With his own secret key, the sender produces the legal ciphertext of keywords. Without the sender’s secret key, the server is not able to generate a correct ciphertext of keyword as inputs of the test procedure. Hence, the server is not able to launch inside KGAs.


### 1.1. Our Contributions

In this paper, we present a new ciphertext retrieval system with a designated tester (dCRKS) based on the new security model. Compared with some analogous works, such as the cloud data retrieval schemes [35–37], the advantages of this system can be summarized as follows.Firstly, we build security model of ciphertext retrieval system. Here, the server will not be considered as special attacker. So this model is more simple.Second, we design an instance of dCRKS. This dCRKS instance can resist inside KGAs. In the instance, the server can not produce a correct ciphertext of keywords without the secret key of sender. Meanwhile the server can not generate a valid trapdoor without the secret key of receiver. Therefore, the malicious server is not able to launch inside KGAs. Most of the existing literatures (as [25, 28]) can not resist inside KGAs. Although the [29] is secure against inside KGAs, the TTP (trusted third party) is required in their scheme.Thirdly, in this dCRKS instance, only a specified server is able to test whether given trapdoor relates to a dCRKS ciphertext. So, the proposal is stronger than [29].Last, the analysis proves that the generation method of trapdoor and the testing algorithm are more effective than those of [29].


## 1.1. Our Contributions

In this paper, we present a new ciphertext retrieval system with a designated tester (dCRKS) based on the new security model. Compared with some analogous works, such as the cloud data retrieval schemes [35–37], the advantages of this system can be summarized as follows.Firstly, we build security model of ciphertext retrieval system. Here, the server will not be considered as special attacker. So this model is more simple.Second, we design an instance of dCRKS. This dCRKS instance can resist inside KGAs. In the instance, the server can not produce a correct ciphertext of keywords without the secret key of sender. Meanwhile the server can not generate a valid trapdoor without the secret key of receiver. Therefore, the malicious server is not able to launch inside KGAs. Most of the existing literatures (as [25, 28]) can not resist inside KGAs. Although the [29] is secure against inside KGAs, the TTP (trusted third party) is required in their scheme.Thirdly, in this dCRKS instance, only a specified server is able to test whether given trapdoor relates to a dCRKS ciphertext. So, the proposal is stronger than [29].Last, the analysis proves that the generation method of trapdoor and the testing algorithm are more effective than those of [29].


## 2. Preliminaries

Here, we will build the framework of dCRKS and its security model. Next, we introduce the hard assumptions which are used to prove the security of the instance of dCRKS system. In security model, letF be an adversary. The challenger denoted by G. The dCRKS ciphertexts refer to the list of encrypted keywords.


### 2.1. Framework of dCRKS and Security Model

#### 2.1.1. Framework of dCRKS

The dCRKS system is a ciphertext retrieval approach. In this system, only the specified server can carry out the testing procedure with the correct dCRKS ciphertext. The framework of dCRKS consists of the four algorithms. They are defined as follows.Setup. Here n is the essential parameter. Let PP be the set public parameter. Inputting n, this algorithm outputs PP.KeyGen ( P P ). When the PP are imported, this algorithm outputs (Pd,Kd), (Pr,Kr), and (Ps,Ks). The Pd (or Kd) is the sender’s public (or private) key. Similarly, the receiver’s public (private) is the Pr (Kr). The server’s public (private) is the Ps (Ks).EndCRKS ( P P , K d , P d , P r ). Let w be a keyword. Taking Pd, Kd, Pr, w, and the public parameter PP as input, this EndCRKS produces Cw corresponding to w, where Cw is dCRKS ciphertext.dTrapdoor ( P d , K r , P s , P P ). When the keywords w′, Kr, Ps, and PP are imported, this algorithm produces a trapdoor Tw′ corresponding to w′.dTest ( K s , C w , T w ′ , P P ). In this algorithm, the server takes a trapdoor Tw′, PP, a dCRKS ciphertext Cw, and its private key Ks as input. If w′=w, it replies “yes”; otherwise it replies “no”.


#### 2.1.2. Security Model

Here, we construct the security architecture of the dCRKS. The security of dCRKS ciphertext and trapdoor are defined by this architecture. The security of dCRKS is based on the two games.In game 1, the adversary can be a malicious server or a malicious receiver or other attackers. So, the adversary can know the server’s secret key or the receiver’s secret key. The only limitation is that the adversary can not query the trapdoors corresponding to the challenge keywordsw0, w1. The dCRKS ciphertext is secure. That means the adversary F is unable to differentiate between the dCRKS ciphertext of w1 and the dCRKS ciphertext of keyword w0 when the coupling trapdoor has not be obtained.In game 2, the adversary can be a malicious server or a malicious sender or other attackers. Clearly, he can obtain the server’s secret key or the receiver’s secret key. The security of trapdoor requires that theF is unable to differentiate between a trapdoor of w1 and a trapdoor of w0 when the coupling trapdoor has not be obtained, where w0 and w1 are the challenge keywords.The game 1 is described as follows.Game 1. In this game, the F can enquire for private key and trapdoor. Yet F is not permitted to enquire the coupling trapdoors of the challenge keywords w0, w1, where both w0 and w1 are his choice. It requires that F differentiates between the dCRKS ciphertext of keyword w1 and the dCRKS ciphertext of w0. If the F can not win this game with nonnegligible probability, the dCRKS scheme is secure to resist the chosen keyword attacks.Init. In this phase, F issues Pd as the challenge public key Pd.Setup. Running the setup procedure, G generates the public parameters PP and gives the public parameters PP to adversary F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of enquiries is no more than polynomially bounded.Pk-Query (Private Key Query). For di≠d∗, F sends Pdi to G, then G replies F with Kdi.T-Query (Trapdoor Query). F issues Pri and wi to G. G runs the trapdoor procedure and replies the trapdoor Twi for Pri, wi to F.Challenge. F chooses the pair keywords (w0,w1) and Pd∗ as the challenge keywords for Pd∗. The restriction is that the private key corresponding to Pd∗ or the trapdoors corresponding to w0 and w1 have not been enquired by F. G generates the challenge ciphertext Cwb∗ and replies Cwb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the secret keys (d≠d∗) and the trapdoors (d≠d∗) or the trapdoor for d=d∗ with wi≠w0, w1. G replies as Phase 1.Outputs. In the end, F guesses b∈{0,1}. When b′=b, it means that F wins this game.Game 2. Here, F can enquire for dCRKS ciphertext and secret key. Yet, F is not allowed to enquire the dCRKS ciphertexts corresponding to the challenge keywords w0 and w1, where both w0 and w1 are his choice. It requires that F differentiates between the trapdoor of keyword w1 and the trapdoor of w0. If the F can not win this game with nonnegligible advantage probability, the dCRKS system can resist the chosen keyword attacks.Init. F issues the challenge public key Pr.Setup. Running setup procedure, the G produces public parameters PP and delivers the parameters PP to F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of inquiries is no more than polynomially bounded.Pk-Query. F sends Pri to G, ri≠r∗, and G responds Kri to F with ri.dc-Query (dCRKS Ciphertext Query). F sends Pdi and wi to G. Running the EndCRKS procedure, G replies the ciphertext Cwi for Pdi, wi to F.Challenge. F chooses a pair keywords w0, w1, and Pr∗ as the challenge keywords for Pr∗. The restriction is that the secret key for Pr∗ or the dCRKS ciphertext of w0, w1 for Pr∗ has not been inquired by F. G generates Twb∗ as challenge trapdoor and replies Twb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the dCRKS ciphertexts and the secret key for r≠r∗ or the dCRKS ciphertexts for r=r∗ and wi≠w0, w1. G replies as the first phase.Outputs. In the end, F guesses b′∈{0,1}. When b′=b, it means that F wins this game.


### 2.2. Complexity Assumptions

#### 2.2.1. Bilinear Map

LetG and GT be multiplicative cyclic groups with the order p (prime). Let e:G×G→GT be a bilinear map. e has the following properties:(1)g1, g2∈G exist, such that e(g1,g2) is not equal to 1GT.(2) For allη,π∈G and a, t∈Z, the e(ηa,πt)=e(η,π)at is true.(3) For allη,π∈G, the e(η,π) can be calculated in polynomial time.


#### 2.2.2. Complexity Assumptions

According to [38], the Computational Diffie-Hellman (CDH) problem is considered to be hard on G and GT. Meanwhile, we know that the Decision Diffie-Hellman (DDH) problem [39] is hard on GT.In additional, to prove the security of dCRKS system, we need to introduce a new hard problem onG and GT, namely, the Strong Decisional Diffie-Hellman assumption (in short SDDH). The SDDH problem is defined as follows.The SDDH problem in (G,GT) is as follows.GivenL′=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) as input, output “yes” if q=ct/a and “no” otherwise, where a, c, t, q∈Zp∗.As is known,gt is not able to infer from e(g,g)t because the e is considered to be one-way functions. Moreover, e(g,h)ct/a can not be calculated from ga, h, and hc. In fact, even the DDH problem is easy, the SDDH problem is seemingly still intractable.Additionally, the DLP (discrete logarithm problem) is assumed to hold overG and GT.


## 2.1. Framework of dCRKS and Security Model

### 2.1.1. Framework of dCRKS

The dCRKS system is a ciphertext retrieval approach. In this system, only the specified server can carry out the testing procedure with the correct dCRKS ciphertext. The framework of dCRKS consists of the four algorithms. They are defined as follows.Setup. Here n is the essential parameter. Let PP be the set public parameter. Inputting n, this algorithm outputs PP.KeyGen ( P P ). When the PP are imported, this algorithm outputs (Pd,Kd), (Pr,Kr), and (Ps,Ks). The Pd (or Kd) is the sender’s public (or private) key. Similarly, the receiver’s public (private) is the Pr (Kr). The server’s public (private) is the Ps (Ks).EndCRKS ( P P , K d , P d , P r ). Let w be a keyword. Taking Pd, Kd, Pr, w, and the public parameter PP as input, this EndCRKS produces Cw corresponding to w, where Cw is dCRKS ciphertext.dTrapdoor ( P d , K r , P s , P P ). When the keywords w′, Kr, Ps, and PP are imported, this algorithm produces a trapdoor Tw′ corresponding to w′.dTest ( K s , C w , T w ′ , P P ). In this algorithm, the server takes a trapdoor Tw′, PP, a dCRKS ciphertext Cw, and its private key Ks as input. If w′=w, it replies “yes”; otherwise it replies “no”.


### 2.1.2. Security Model

Here, we construct the security architecture of the dCRKS. The security of dCRKS ciphertext and trapdoor are defined by this architecture. The security of dCRKS is based on the two games.In game 1, the adversary can be a malicious server or a malicious receiver or other attackers. So, the adversary can know the server’s secret key or the receiver’s secret key. The only limitation is that the adversary can not query the trapdoors corresponding to the challenge keywordsw0, w1. The dCRKS ciphertext is secure. That means the adversary F is unable to differentiate between the dCRKS ciphertext of w1 and the dCRKS ciphertext of keyword w0 when the coupling trapdoor has not be obtained.In game 2, the adversary can be a malicious server or a malicious sender or other attackers. Clearly, he can obtain the server’s secret key or the receiver’s secret key. The security of trapdoor requires that theF is unable to differentiate between a trapdoor of w1 and a trapdoor of w0 when the coupling trapdoor has not be obtained, where w0 and w1 are the challenge keywords.The game 1 is described as follows.Game 1. In this game, the F can enquire for private key and trapdoor. Yet F is not permitted to enquire the coupling trapdoors of the challenge keywords w0, w1, where both w0 and w1 are his choice. It requires that F differentiates between the dCRKS ciphertext of keyword w1 and the dCRKS ciphertext of w0. If the F can not win this game with nonnegligible probability, the dCRKS scheme is secure to resist the chosen keyword attacks.Init. In this phase, F issues Pd as the challenge public key Pd.Setup. Running the setup procedure, G generates the public parameters PP and gives the public parameters PP to adversary F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of enquiries is no more than polynomially bounded.Pk-Query (Private Key Query). For di≠d∗, F sends Pdi to G, then G replies F with Kdi.T-Query (Trapdoor Query). F issues Pri and wi to G. G runs the trapdoor procedure and replies the trapdoor Twi for Pri, wi to F.Challenge. F chooses the pair keywords (w0,w1) and Pd∗ as the challenge keywords for Pd∗. The restriction is that the private key corresponding to Pd∗ or the trapdoors corresponding to w0 and w1 have not been enquired by F. G generates the challenge ciphertext Cwb∗ and replies Cwb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the secret keys (d≠d∗) and the trapdoors (d≠d∗) or the trapdoor for d=d∗ with wi≠w0, w1. G replies as Phase 1.Outputs. In the end, F guesses b∈{0,1}. When b′=b, it means that F wins this game.Game 2. Here, F can enquire for dCRKS ciphertext and secret key. Yet, F is not allowed to enquire the dCRKS ciphertexts corresponding to the challenge keywords w0 and w1, where both w0 and w1 are his choice. It requires that F differentiates between the trapdoor of keyword w1 and the trapdoor of w0. If the F can not win this game with nonnegligible advantage probability, the dCRKS system can resist the chosen keyword attacks.Init. F issues the challenge public key Pr.Setup. Running setup procedure, the G produces public parameters PP and delivers the parameters PP to F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of inquiries is no more than polynomially bounded.Pk-Query. F sends Pri to G, ri≠r∗, and G responds Kri to F with ri.dc-Query (dCRKS Ciphertext Query). F sends Pdi and wi to G. Running the EndCRKS procedure, G replies the ciphertext Cwi for Pdi, wi to F.Challenge. F chooses a pair keywords w0, w1, and Pr∗ as the challenge keywords for Pr∗. The restriction is that the secret key for Pr∗ or the dCRKS ciphertext of w0, w1 for Pr∗ has not been inquired by F. G generates Twb∗ as challenge trapdoor and replies Twb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the dCRKS ciphertexts and the secret key for r≠r∗ or the dCRKS ciphertexts for r=r∗ and wi≠w0, w1. G replies as the first phase.Outputs. In the end, F guesses b′∈{0,1}. When b′=b, it means that F wins this game.


## 2.1.1. Framework of dCRKS

The dCRKS system is a ciphertext retrieval approach. In this system, only the specified server can carry out the testing procedure with the correct dCRKS ciphertext. The framework of dCRKS consists of the four algorithms. They are defined as follows.Setup. Here n is the essential parameter. Let PP be the set public parameter. Inputting n, this algorithm outputs PP.KeyGen ( P P ). When the PP are imported, this algorithm outputs (Pd,Kd), (Pr,Kr), and (Ps,Ks). The Pd (or Kd) is the sender’s public (or private) key. Similarly, the receiver’s public (private) is the Pr (Kr). The server’s public (private) is the Ps (Ks).EndCRKS ( P P , K d , P d , P r ). Let w be a keyword. Taking Pd, Kd, Pr, w, and the public parameter PP as input, this EndCRKS produces Cw corresponding to w, where Cw is dCRKS ciphertext.dTrapdoor ( P d , K r , P s , P P ). When the keywords w′, Kr, Ps, and PP are imported, this algorithm produces a trapdoor Tw′ corresponding to w′.dTest ( K s , C w , T w ′ , P P ). In this algorithm, the server takes a trapdoor Tw′, PP, a dCRKS ciphertext Cw, and its private key Ks as input. If w′=w, it replies “yes”; otherwise it replies “no”.


## 2.1.2. Security Model

Here, we construct the security architecture of the dCRKS. The security of dCRKS ciphertext and trapdoor are defined by this architecture. The security of dCRKS is based on the two games.In game 1, the adversary can be a malicious server or a malicious receiver or other attackers. So, the adversary can know the server’s secret key or the receiver’s secret key. The only limitation is that the adversary can not query the trapdoors corresponding to the challenge keywordsw0, w1. The dCRKS ciphertext is secure. That means the adversary F is unable to differentiate between the dCRKS ciphertext of w1 and the dCRKS ciphertext of keyword w0 when the coupling trapdoor has not be obtained.In game 2, the adversary can be a malicious server or a malicious sender or other attackers. Clearly, he can obtain the server’s secret key or the receiver’s secret key. The security of trapdoor requires that theF is unable to differentiate between a trapdoor of w1 and a trapdoor of w0 when the coupling trapdoor has not be obtained, where w0 and w1 are the challenge keywords.The game 1 is described as follows.Game 1. In this game, the F can enquire for private key and trapdoor. Yet F is not permitted to enquire the coupling trapdoors of the challenge keywords w0, w1, where both w0 and w1 are his choice. It requires that F differentiates between the dCRKS ciphertext of keyword w1 and the dCRKS ciphertext of w0. If the F can not win this game with nonnegligible probability, the dCRKS scheme is secure to resist the chosen keyword attacks.Init. In this phase, F issues Pd as the challenge public key Pd.Setup. Running the setup procedure, G generates the public parameters PP and gives the public parameters PP to adversary F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of enquiries is no more than polynomially bounded.Pk-Query (Private Key Query). For di≠d∗, F sends Pdi to G, then G replies F with Kdi.T-Query (Trapdoor Query). F issues Pri and wi to G. G runs the trapdoor procedure and replies the trapdoor Twi for Pri, wi to F.Challenge. F chooses the pair keywords (w0,w1) and Pd∗ as the challenge keywords for Pd∗. The restriction is that the private key corresponding to Pd∗ or the trapdoors corresponding to w0 and w1 have not been enquired by F. G generates the challenge ciphertext Cwb∗ and replies Cwb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the secret keys (d≠d∗) and the trapdoors (d≠d∗) or the trapdoor for d=d∗ with wi≠w0, w1. G replies as Phase 1.Outputs. In the end, F guesses b∈{0,1}. When b′=b, it means that F wins this game.Game 2. Here, F can enquire for dCRKS ciphertext and secret key. Yet, F is not allowed to enquire the dCRKS ciphertexts corresponding to the challenge keywords w0 and w1, where both w0 and w1 are his choice. It requires that F differentiates between the trapdoor of keyword w1 and the trapdoor of w0. If the F can not win this game with nonnegligible advantage probability, the dCRKS system can resist the chosen keyword attacks.Init. F issues the challenge public key Pr.Setup. Running setup procedure, the G produces public parameters PP and delivers the parameters PP to F.Phase 1. F performs repeatedly inquiries. The restriction is that the number of inquiries is no more than polynomially bounded.Pk-Query. F sends Pri to G, ri≠r∗, and G responds Kri to F with ri.dc-Query (dCRKS Ciphertext Query). F sends Pdi and wi to G. Running the EndCRKS procedure, G replies the ciphertext Cwi for Pdi, wi to F.Challenge. F chooses a pair keywords w0, w1, and Pr∗ as the challenge keywords for Pr∗. The restriction is that the secret key for Pr∗ or the dCRKS ciphertext of w0, w1 for Pr∗ has not been inquired by F. G generates Twb∗ as challenge trapdoor and replies Twb∗ to F, where b∈{0,1} is a random bit.Phase 2. In this phase, F can still enquire the dCRKS ciphertexts and the secret key for r≠r∗ or the dCRKS ciphertexts for r=r∗ and wi≠w0, w1. G replies as the first phase.Outputs. In the end, F guesses b′∈{0,1}. When b′=b, it means that F wins this game.


## 2.2. Complexity Assumptions

### 2.2.1. Bilinear Map

LetG and GT be multiplicative cyclic groups with the order p (prime). Let e:G×G→GT be a bilinear map. e has the following properties:(1)g1, g2∈G exist, such that e(g1,g2) is not equal to 1GT.(2) For allη,π∈G and a, t∈Z, the e(ηa,πt)=e(η,π)at is true.(3) For allη,π∈G, the e(η,π) can be calculated in polynomial time.


### 2.2.2. Complexity Assumptions

According to [38], the Computational Diffie-Hellman (CDH) problem is considered to be hard on G and GT. Meanwhile, we know that the Decision Diffie-Hellman (DDH) problem [39] is hard on GT.In additional, to prove the security of dCRKS system, we need to introduce a new hard problem onG and GT, namely, the Strong Decisional Diffie-Hellman assumption (in short SDDH). The SDDH problem is defined as follows.The SDDH problem in (G,GT) is as follows.GivenL′=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) as input, output “yes” if q=ct/a and “no” otherwise, where a, c, t, q∈Zp∗.As is known,gt is not able to infer from e(g,g)t because the e is considered to be one-way functions. Moreover, e(g,h)ct/a can not be calculated from ga, h, and hc. In fact, even the DDH problem is easy, the SDDH problem is seemingly still intractable.Additionally, the DLP (discrete logarithm problem) is assumed to hold overG and GT.


## 2.2.1. Bilinear Map

LetG and GT be multiplicative cyclic groups with the order p (prime). Let e:G×G→GT be a bilinear map. e has the following properties:(1)g1, g2∈G exist, such that e(g1,g2) is not equal to 1GT.(2) For allη,π∈G and a, t∈Z, the e(ηa,πt)=e(η,π)at is true.(3) For allη,π∈G, the e(η,π) can be calculated in polynomial time.


## 2.2.2. Complexity Assumptions

According to [38], the Computational Diffie-Hellman (CDH) problem is considered to be hard on G and GT. Meanwhile, we know that the Decision Diffie-Hellman (DDH) problem [39] is hard on GT.In additional, to prove the security of dCRKS system, we need to introduce a new hard problem onG and GT, namely, the Strong Decisional Diffie-Hellman assumption (in short SDDH). The SDDH problem is defined as follows.The SDDH problem in (G,GT) is as follows.GivenL′=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) as input, output “yes” if q=ct/a and “no” otherwise, where a, c, t, q∈Zp∗.As is known,gt is not able to infer from e(g,g)t because the e is considered to be one-way functions. Moreover, e(g,h)ct/a can not be calculated from ga, h, and hc. In fact, even the DDH problem is easy, the SDDH problem is seemingly still intractable.Additionally, the DLP (discrete logarithm problem) is assumed to hold overG and GT.


## 3. dCRKS against Insider Attacks

### 3.1. The Instance of dCRKS

Now, we will describe the instance of dCRKS. Here, theG and GT are given groups as the previous definition. Let H:{0,1}∗→Zp∗ be the hash function, which is considered as random oracle in security model.Setup. Let e be a bilinear map on G. Let p be the order of G and GT, where both G and GT are multiplicative cyclic group. This procedure produces PP=(g,GT,G,p,H,e,h), where PP is the set of public parameters. The generator of G is g.KeyGen ( P P ). Takes as input x, y, z, g, and h, where x, y, z∈Zp∗. This procedure generates key as the following way.K d = z and Pd=hz, where Kd and Pd are the sender’s private key and public key, respectively.K r = x and Pr=(Pr1,Pr2)=(e(g,h)1/x,gx), where Kr=x and Pr are the receiver’s private key and public key.K s = y and Ps=gy, where Ks=y and Ps=gy are the server’s private key and public key.EndCRKS ( P d , K d , P r , w ). The sender takes a keyword w, Pr, Pd, Kd, PP, and a random u∈Zp∗ as input. This procedure produces C=(C1,C2,C3) as the dCRKS ciphertext of w output. C1, C2, and C3 are calculated as follows:C3=e(g,g)uC2=(Pr2)u·g-uH(w)=g(x-H(w))uC1=(Pr1)zu=e(g,h)zu/xdTrapdoor ( P d , K r , P s , w ′ ). The receiver takes a keyword w′, r∈Zp∗, Pd, Kr, and Ps as inputs. This procedure produces T=(T1,T2) as the trapdoor of w′ output. T1 and T2 are calculated as follows:T1=r;T2=(Pd1/x·Ps-r)1/x-Hw′.dTest. Receiving a trapdoor T, the server runs dTest algorithm over the dCRKS ciphertexts with his private key y. Let C be a dCRKS ciphertext. The retrieving operation is executed by checking (1)eC2,T2C3yT1=C1If the above equation is true, the algorithm returns 1; otherwise it returns 0.


### 3.2. Correctness of dCRKS

Now, we show that the above instance is correct. LetC be a dCRKS ciphertext which matches the trapdoor T. By the following equations, we can verify the correctness of dTest.T1=r;T2=(Pd1/x·Ps-r)1/x-Hw′;T=(T1,T2);C2=Pr2u·g-uH(w);e(C2,T2)=e(g(x-H(w))u,(hz/xg-yr)1/x-Hw′).Whenw′=w, we can obtain the equationse(C2,T2)=e(gu,hz/xg-yr)=e(gu,hz/x)e(gu,g-yr)As a result, the correctness of dTest is verified as follows:C1=e(g,h)zu/x=e(C2,T2)C3yT1.


### 3.3. Security of dCRKS

#### 3.3.1. Security of dCRKS Ciphertext

In this section, we demonstrate that the ciphertexts of keywords are secure under the chosen keyword attack in the instance.Theorem 1.
Suppose the SDDH problem is hard; the dCRKS instance can achieve dCRKS ciphertext indistinguishability.Proof.
LetF be polynomial-time adversary. If F can break the dCRKS instance with nonnegligible advantage probability, we construct an algorithm G as the challenger, who can solve the SDDH problem with nonnegligible advantage probability.
Init. The F issues the challenge public key Pd∗=hz∗ and a keyword set wi.
Setup. Let L=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) be a SDDH instance. G is given L and (G, GT, e(·)). The setup procedure produces parameters PP, then G sends PP to F.
Phase 1. F can carry out multiple queries. The restriction is that the number of enquiries is no more than polynomially bounded.
Pk-Query. To inquire di’s private key, F transmits Pdi to G. If di≠d∗, G returns zi=Kdi to F.
T-Query. To inquire the trapdoor of wi, F issues wi and Pri=(e(g,h)1/x,gx) to G. G responds the trapdoor Twi for Pri, wi by calling the trapdoor oracle.
Challenge. Let d∗ be the sender’s identity. F selects w0, w1, and Pd∗ as challenge. The restriction is that the secret key for Pd∗ or the trapdoor for w0, w1 for Pd∗ have not been inquired by F. G replies the challenge ciphertext Cwb∗ to F, where Cwb∗ is a tuple (C1,C2,C3) and C3=e(g,g)t, C2=gat′g-t′H(wb), and C1=e(g,h)q.
Phase 2. F can still enquire the trapdoor and the secret key for d≠d∗ or the trapdoor for d=d∗ and wi≠w0, w1. G replies as the front phase.
Outputs. In the end, F outputs b′∈{0,1}.
Analysis. Because the actual dCRKS ciphertext Cwb is C1=e(g,h)zu/x, C2=gx-H(wb)u, and C3=e(g,g)u, the distribution of challenge ciphertext Cwb∗ is identical to that in the actual system. In fact, for the uniformly random t′, t∈Zp∗, F needs to differentiate between the tuple (gt′(-H(wb)+a), e(g,g)t) and the tuple (gt(-H(wb)+a), e(g,g)t). If q=ct/a, the simulation is perfect. ε denotes nonnegligible probability. As a result, if F has advantage probability 1/2+ε to determine the bits b correctly, then the G can solve the SDDH problem with identical advantage probability ε.
This completes the proof of dCRKS ciphertexts indistinguishability.


#### 3.3.2. Security of Trapdoor

Now, we show that the trapdoor is secure under the chosen keyword attack.Theorem 2.
The dCRKS instance can achieve the trapdoor indistinguishability to resist the chosen keyword attack under random oracle model in game 2.Proof.
In this section, we show that the polynomial-time algorithmF is able to differentiate between the ciphertext of keyword w0 and the ciphertext of keyword w1 if and only if he can distinguish two uniform distributions on G.
Init. F issues Pr∗=(gx∗,e(g,h)1/x∗) as the challenge public key.
Setup. Running the setup procedure, G gives the public parameters to F.
Phase 1. F implements multiple queries without exceeding polynomial bounded.
Pk-Query. To inquire ri’s private key, F sends Pri=(e(g,h)1/xi) to G, ri≠r∗. Then G returns Kri=xi.
dc-Query. F issues Pdi and wi to G. Running EndCRKS oracle, G returns Cwi for Pdi, wi to F.
Challenge. F chooses keywords w0, w1, and Pr∗ as his challenge. The restriction is that the ciphertext for w0, w1 for Pr∗ or the private key for Pr∗ has not be enquired by F. G picks two random r′, z′ and computes the challenge trapdoor Twb∗, where Twb′∗=r′,hz′g-yr′. Then G replies the challenge trapdoor Twb′∗ to F.
Phase 2. F can still enquire the ciphertext and the secret key for r≠r∗ or the ciphertext for r=r∗ and wi≠w0, w1. G replies as first phase.
Outputs. F outputs b′∈0,1.
Analysis. By enquiring, F can obtain gx∗, e(g,h)1/x∗, and Twb′∗=(r′,hz′g-yr′). In scheme, Twb∗=(r,(hz/x∗g-yr)1/x∗-H(wb)), where r is uniform random value. Thus the distribution of (hz/x∗g-yr)1/x∗-H(wb) is a uniform distribution on G. Meanwhile, the Twb′∗=(r′,hz′g-yr′) is uniform distribution on G with taking uniform random r′, z′. As a result, the simulation is perfect, namely, the distribution of Twb′∗ is identical to that in the actual system.
Moreover, as game 2,F can not know z and x∗. Even if F can calculate the following value:e(g(x∗-H(wb)),Twb∗) = e(g,h)(z/x∗-yr)(x∗-Hwb′/x∗-H(wb))
F cannot distinguishe(g,h)z/x∗-yrx∗-Hwb′/x∗-Hwb  (where b′≠b)
frome(g,h)z/x∗·e(g,h)-yr  (where b′=b).
Therefore,F can guess b′=b with nonnegligible advantage probability, then G can distinguish between (hz/x∗g-yr)1/x∗-H(wb) and uniformly distribution on G with identical advantage probability.


#### 3.3.3. Analysis of against Inside KGAs

In this section, we show that the dCRKS instance is secure against inside KGAs as follows.First, given the trapdoorTwd, the server can generate the legal ciphertext C corresponding to Twd if and only if it can obtain the specified senders private key. Maybe the server can select z′ and calculate hz′ to produce ciphertext C=(C1′,C2′,C3′) corresponding to w′, wheree(g,hz′)u/x=(Pr1)z′u=C1′gx-Hw′u=(Pr2)u·g-uHw′=C2′e(g,g)u=C3′LetTwd=(T1,T2), thene(C2,T2)=e(g(x-H(w))u,(hz/xg-yr)1/x-Hw′)Based on the dTest, thee(C2,T2)C3yT1=C1 is true if and only if w=w′ and z′=z, where z and w correspond to Twd. However, given the trapdoor Twd, the probability of selecting z′∈Zp∗ such that z′=z is negligible, even w′=w. Therefore, the malicious cloud server is not able to launch keyword-guessing attacks by computing the dCRKS ciphertext of all possible keywords.Second, given the ciphertextCw=(C1,C2,C3), the cloud server can not produce a legal trapdoor Tw corresponding to Cw. Although the server may select a x′, Pd, and w′ to generate the trapdoor, the probability of selecting x′∈Zp∗ such that x′=x is negligible, where x is the receiver’s private key associated with the Cw. Based on the same analysis, we know that the malicious cloud server is not able to launch keyword-guessing attacks by creating the trapdoor of all possible keywords.Lastly, takinggx, H(w), and e(g,h)1/x, the server may build the following equation: e(gx-Hwb,Twb)=e(g,h)z/xx-Hwb′/x-Hwb·e(g,h)-yr(x-H(wb′)/x-H(wb))However, this equation can not help to find correct trapdoor or launch KGAs sinceTwb contains a random number. Summarize these reasons; the proposal is secure under the inside KGAs.


## 3.1. The Instance of dCRKS

Now, we will describe the instance of dCRKS. Here, theG and GT are given groups as the previous definition. Let H:{0,1}∗→Zp∗ be the hash function, which is considered as random oracle in security model.Setup. Let e be a bilinear map on G. Let p be the order of G and GT, where both G and GT are multiplicative cyclic group. This procedure produces PP=(g,GT,G,p,H,e,h), where PP is the set of public parameters. The generator of G is g.KeyGen ( P P ). Takes as input x, y, z, g, and h, where x, y, z∈Zp∗. This procedure generates key as the following way.K d = z and Pd=hz, where Kd and Pd are the sender’s private key and public key, respectively.K r = x and Pr=(Pr1,Pr2)=(e(g,h)1/x,gx), where Kr=x and Pr are the receiver’s private key and public key.K s = y and Ps=gy, where Ks=y and Ps=gy are the server’s private key and public key.EndCRKS ( P d , K d , P r , w ). The sender takes a keyword w, Pr, Pd, Kd, PP, and a random u∈Zp∗ as input. This procedure produces C=(C1,C2,C3) as the dCRKS ciphertext of w output. C1, C2, and C3 are calculated as follows:C3=e(g,g)uC2=(Pr2)u·g-uH(w)=g(x-H(w))uC1=(Pr1)zu=e(g,h)zu/xdTrapdoor ( P d , K r , P s , w ′ ). The receiver takes a keyword w′, r∈Zp∗, Pd, Kr, and Ps as inputs. This procedure produces T=(T1,T2) as the trapdoor of w′ output. T1 and T2 are calculated as follows:T1=r;T2=(Pd1/x·Ps-r)1/x-Hw′.dTest. Receiving a trapdoor T, the server runs dTest algorithm over the dCRKS ciphertexts with his private key y. Let C be a dCRKS ciphertext. The retrieving operation is executed by checking (1)eC2,T2C3yT1=C1If the above equation is true, the algorithm returns 1; otherwise it returns 0.


## 3.2. Correctness of dCRKS

Now, we show that the above instance is correct. LetC be a dCRKS ciphertext which matches the trapdoor T. By the following equations, we can verify the correctness of dTest.T1=r;T2=(Pd1/x·Ps-r)1/x-Hw′;T=(T1,T2);C2=Pr2u·g-uH(w);e(C2,T2)=e(g(x-H(w))u,(hz/xg-yr)1/x-Hw′).Whenw′=w, we can obtain the equationse(C2,T2)=e(gu,hz/xg-yr)=e(gu,hz/x)e(gu,g-yr)As a result, the correctness of dTest is verified as follows:C1=e(g,h)zu/x=e(C2,T2)C3yT1.


## 3.3. Security of dCRKS

### 3.3.1. Security of dCRKS Ciphertext

In this section, we demonstrate that the ciphertexts of keywords are secure under the chosen keyword attack in the instance.Theorem 1.
Suppose the SDDH problem is hard; the dCRKS instance can achieve dCRKS ciphertext indistinguishability.Proof.
LetF be polynomial-time adversary. If F can break the dCRKS instance with nonnegligible advantage probability, we construct an algorithm G as the challenger, who can solve the SDDH problem with nonnegligible advantage probability.
Init. The F issues the challenge public key Pd∗=hz∗ and a keyword set wi.
Setup. Let L=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) be a SDDH instance. G is given L and (G, GT, e(·)). The setup procedure produces parameters PP, then G sends PP to F.
Phase 1. F can carry out multiple queries. The restriction is that the number of enquiries is no more than polynomially bounded.
Pk-Query. To inquire di’s private key, F transmits Pdi to G. If di≠d∗, G returns zi=Kdi to F.
T-Query. To inquire the trapdoor of wi, F issues wi and Pri=(e(g,h)1/x,gx) to G. G responds the trapdoor Twi for Pri, wi by calling the trapdoor oracle.
Challenge. Let d∗ be the sender’s identity. F selects w0, w1, and Pd∗ as challenge. The restriction is that the secret key for Pd∗ or the trapdoor for w0, w1 for Pd∗ have not been inquired by F. G replies the challenge ciphertext Cwb∗ to F, where Cwb∗ is a tuple (C1,C2,C3) and C3=e(g,g)t, C2=gat′g-t′H(wb), and C1=e(g,h)q.
Phase 2. F can still enquire the trapdoor and the secret key for d≠d∗ or the trapdoor for d=d∗ and wi≠w0, w1. G replies as the front phase.
Outputs. In the end, F outputs b′∈{0,1}.
Analysis. Because the actual dCRKS ciphertext Cwb is C1=e(g,h)zu/x, C2=gx-H(wb)u, and C3=e(g,g)u, the distribution of challenge ciphertext Cwb∗ is identical to that in the actual system. In fact, for the uniformly random t′, t∈Zp∗, F needs to differentiate between the tuple (gt′(-H(wb)+a), e(g,g)t) and the tuple (gt(-H(wb)+a), e(g,g)t). If q=ct/a, the simulation is perfect. ε denotes nonnegligible probability. As a result, if F has advantage probability 1/2+ε to determine the bits b correctly, then the G can solve the SDDH problem with identical advantage probability ε.
This completes the proof of dCRKS ciphertexts indistinguishability.


### 3.3.2. Security of Trapdoor

Now, we show that the trapdoor is secure under the chosen keyword attack.Theorem 2.
The dCRKS instance can achieve the trapdoor indistinguishability to resist the chosen keyword attack under random oracle model in game 2.Proof.
In this section, we show that the polynomial-time algorithmF is able to differentiate between the ciphertext of keyword w0 and the ciphertext of keyword w1 if and only if he can distinguish two uniform distributions on G.
Init. F issues Pr∗=(gx∗,e(g,h)1/x∗) as the challenge public key.
Setup. Running the setup procedure, G gives the public parameters to F.
Phase 1. F implements multiple queries without exceeding polynomial bounded.
Pk-Query. To inquire ri’s private key, F sends Pri=(e(g,h)1/xi) to G, ri≠r∗. Then G returns Kri=xi.
dc-Query. F issues Pdi and wi to G. Running EndCRKS oracle, G returns Cwi for Pdi, wi to F.
Challenge. F chooses keywords w0, w1, and Pr∗ as his challenge. The restriction is that the ciphertext for w0, w1 for Pr∗ or the private key for Pr∗ has not be enquired by F. G picks two random r′, z′ and computes the challenge trapdoor Twb∗, where Twb′∗=r′,hz′g-yr′. Then G replies the challenge trapdoor Twb′∗ to F.
Phase 2. F can still enquire the ciphertext and the secret key for r≠r∗ or the ciphertext for r=r∗ and wi≠w0, w1. G replies as first phase.
Outputs. F outputs b′∈0,1.
Analysis. By enquiring, F can obtain gx∗, e(g,h)1/x∗, and Twb′∗=(r′,hz′g-yr′). In scheme, Twb∗=(r,(hz/x∗g-yr)1/x∗-H(wb)), where r is uniform random value. Thus the distribution of (hz/x∗g-yr)1/x∗-H(wb) is a uniform distribution on G. Meanwhile, the Twb′∗=(r′,hz′g-yr′) is uniform distribution on G with taking uniform random r′, z′. As a result, the simulation is perfect, namely, the distribution of Twb′∗ is identical to that in the actual system.
Moreover, as game 2,F can not know z and x∗. Even if F can calculate the following value:e(g(x∗-H(wb)),Twb∗) = e(g,h)(z/x∗-yr)(x∗-Hwb′/x∗-H(wb))
F cannot distinguishe(g,h)z/x∗-yrx∗-Hwb′/x∗-Hwb  (where b′≠b)
frome(g,h)z/x∗·e(g,h)-yr  (where b′=b).
Therefore,F can guess b′=b with nonnegligible advantage probability, then G can distinguish between (hz/x∗g-yr)1/x∗-H(wb) and uniformly distribution on G with identical advantage probability.


### 3.3.3. Analysis of against Inside KGAs

In this section, we show that the dCRKS instance is secure against inside KGAs as follows.First, given the trapdoorTwd, the server can generate the legal ciphertext C corresponding to Twd if and only if it can obtain the specified senders private key. Maybe the server can select z′ and calculate hz′ to produce ciphertext C=(C1′,C2′,C3′) corresponding to w′, wheree(g,hz′)u/x=(Pr1)z′u=C1′gx-Hw′u=(Pr2)u·g-uHw′=C2′e(g,g)u=C3′LetTwd=(T1,T2), thene(C2,T2)=e(g(x-H(w))u,(hz/xg-yr)1/x-Hw′)Based on the dTest, thee(C2,T2)C3yT1=C1 is true if and only if w=w′ and z′=z, where z and w correspond to Twd. However, given the trapdoor Twd, the probability of selecting z′∈Zp∗ such that z′=z is negligible, even w′=w. Therefore, the malicious cloud server is not able to launch keyword-guessing attacks by computing the dCRKS ciphertext of all possible keywords.Second, given the ciphertextCw=(C1,C2,C3), the cloud server can not produce a legal trapdoor Tw corresponding to Cw. Although the server may select a x′, Pd, and w′ to generate the trapdoor, the probability of selecting x′∈Zp∗ such that x′=x is negligible, where x is the receiver’s private key associated with the Cw. Based on the same analysis, we know that the malicious cloud server is not able to launch keyword-guessing attacks by creating the trapdoor of all possible keywords.Lastly, takinggx, H(w), and e(g,h)1/x, the server may build the following equation: e(gx-Hwb,Twb)=e(g,h)z/xx-Hwb′/x-Hwb·e(g,h)-yr(x-H(wb′)/x-H(wb))However, this equation can not help to find correct trapdoor or launch KGAs sinceTwb contains a random number. Summarize these reasons; the proposal is secure under the inside KGAs.


## 3.3.1. Security of dCRKS Ciphertext

In this section, we demonstrate that the ciphertexts of keywords are secure under the chosen keyword attack in the instance.Theorem 1.
Suppose the SDDH problem is hard; the dCRKS instance can achieve dCRKS ciphertext indistinguishability.Proof.
LetF be polynomial-time adversary. If F can break the dCRKS instance with nonnegligible advantage probability, we construct an algorithm G as the challenger, who can solve the SDDH problem with nonnegligible advantage probability.
Init. The F issues the challenge public key Pd∗=hz∗ and a keyword set wi.
Setup. Let L=(g,h,ga,hc,e(g,h)1/a,e(g,g)t,e(g,h)q) be a SDDH instance. G is given L and (G, GT, e(·)). The setup procedure produces parameters PP, then G sends PP to F.
Phase 1. F can carry out multiple queries. The restriction is that the number of enquiries is no more than polynomially bounded.
Pk-Query. To inquire di’s private key, F transmits Pdi to G. If di≠d∗, G returns zi=Kdi to F.
T-Query. To inquire the trapdoor of wi, F issues wi and Pri=(e(g,h)1/x,gx) to G. G responds the trapdoor Twi for Pri, wi by calling the trapdoor oracle.
Challenge. Let d∗ be the sender’s identity. F selects w0, w1, and Pd∗ as challenge. The restriction is that the secret key for Pd∗ or the trapdoor for w0, w1 for Pd∗ have not been inquired by F. G replies the challenge ciphertext Cwb∗ to F, where Cwb∗ is a tuple (C1,C2,C3) and C3=e(g,g)t, C2=gat′g-t′H(wb), and C1=e(g,h)q.
Phase 2. F can still enquire the trapdoor and the secret key for d≠d∗ or the trapdoor for d=d∗ and wi≠w0, w1. G replies as the front phase.
Outputs. In the end, F outputs b′∈{0,1}.
Analysis. Because the actual dCRKS ciphertext Cwb is C1=e(g,h)zu/x, C2=gx-H(wb)u, and C3=e(g,g)u, the distribution of challenge ciphertext Cwb∗ is identical to that in the actual system. In fact, for the uniformly random t′, t∈Zp∗, F needs to differentiate between the tuple (gt′(-H(wb)+a), e(g,g)t) and the tuple (gt(-H(wb)+a), e(g,g)t). If q=ct/a, the simulation is perfect. ε denotes nonnegligible probability. As a result, if F has advantage probability 1/2+ε to determine the bits b correctly, then the G can solve the SDDH problem with identical advantage probability ε.
This completes the proof of dCRKS ciphertexts indistinguishability.


## 3.3.2. Security of Trapdoor

Now, we show that the trapdoor is secure under the chosen keyword attack.Theorem 2.
The dCRKS instance can achieve the trapdoor indistinguishability to resist the chosen keyword attack under random oracle model in game 2.Proof.
In this section, we show that the polynomial-time algorithmF is able to differentiate between the ciphertext of keyword w0 and the ciphertext of keyword w1 if and only if he can distinguish two uniform distributions on G.
Init. F issues Pr∗=(gx∗,e(g,h)1/x∗) as the challenge public key.
Setup. Running the setup procedure, G gives the public parameters to F.
Phase 1. F implements multiple queries without exceeding polynomial bounded.
Pk-Query. To inquire ri’s private key, F sends Pri=(e(g,h)1/xi) to G, ri≠r∗. Then G returns Kri=xi.
dc-Query. F issues Pdi and wi to G. Running EndCRKS oracle, G returns Cwi for Pdi, wi to F.
Challenge. F chooses keywords w0, w1, and Pr∗ as his challenge. The restriction is that the ciphertext for w0, w1 for Pr∗ or the private key for Pr∗ has not be enquired by F. G picks two random r′, z′ and computes the challenge trapdoor Twb∗, where Twb′∗=r′,hz′g-yr′. Then G replies the challenge trapdoor Twb′∗ to F.
Phase 2. F can still enquire the ciphertext and the secret key for r≠r∗ or the ciphertext for r=r∗ and wi≠w0, w1. G replies as first phase.
Outputs. F outputs b′∈0,1.
Analysis. By enquiring, F can obtain gx∗, e(g,h)1/x∗, and Twb′∗=(r′,hz′g-yr′). In scheme, Twb∗=(r,(hz/x∗g-yr)1/x∗-H(wb)), where r is uniform random value. Thus the distribution of (hz/x∗g-yr)1/x∗-H(wb) is a uniform distribution on G. Meanwhile, the Twb′∗=(r′,hz′g-yr′) is uniform distribution on G with taking uniform random r′, z′. As a result, the simulation is perfect, namely, the distribution of Twb′∗ is identical to that in the actual system.
Moreover, as game 2,F can not know z and x∗. Even if F can calculate the following value:e(g(x∗-H(wb)),Twb∗) = e(g,h)(z/x∗-yr)(x∗-Hwb′/x∗-H(wb))
F cannot distinguishe(g,h)z/x∗-yrx∗-Hwb′/x∗-Hwb  (where b′≠b)
frome(g,h)z/x∗·e(g,h)-yr  (where b′=b).
Therefore,F can guess b′=b with nonnegligible advantage probability, then G can distinguish between (hz/x∗g-yr)1/x∗-H(wb) and uniformly distribution on G with identical advantage probability.


## 3.3.3. Analysis of against Inside KGAs

In this section, we show that the dCRKS instance is secure against inside KGAs as follows.First, given the trapdoorTwd, the server can generate the legal ciphertext C corresponding to Twd if and only if it can obtain the specified senders private key. Maybe the server can select z′ and calculate hz′ to produce ciphertext C=(C1′,C2′,C3′) corresponding to w′, wheree(g,hz′)u/x=(Pr1)z′u=C1′gx-Hw′u=(Pr2)u·g-uHw′=C2′e(g,g)u=C3′LetTwd=(T1,T2), thene(C2,T2)=e(g(x-H(w))u,(hz/xg-yr)1/x-Hw′)Based on the dTest, thee(C2,T2)C3yT1=C1 is true if and only if w=w′ and z′=z, where z and w correspond to Twd. However, given the trapdoor Twd, the probability of selecting z′∈Zp∗ such that z′=z is negligible, even w′=w. Therefore, the malicious cloud server is not able to launch keyword-guessing attacks by computing the dCRKS ciphertext of all possible keywords.Second, given the ciphertextCw=(C1,C2,C3), the cloud server can not produce a legal trapdoor Tw corresponding to Cw. Although the server may select a x′, Pd, and w′ to generate the trapdoor, the probability of selecting x′∈Zp∗ such that x′=x is negligible, where x is the receiver’s private key associated with the Cw. Based on the same analysis, we know that the malicious cloud server is not able to launch keyword-guessing attacks by creating the trapdoor of all possible keywords.Lastly, takinggx, H(w), and e(g,h)1/x, the server may build the following equation: e(gx-Hwb,Twb)=e(g,h)z/xx-Hwb′/x-Hwb·e(g,h)-yr(x-H(wb′)/x-H(wb))However, this equation can not help to find correct trapdoor or launch KGAs sinceTwb contains a random number. Summarize these reasons; the proposal is secure under the inside KGAs.


## 4. Performance Analysis

Now, we demonstrate efficiency of the proposal by analyzing its security and calculation cost. With the analysis in Table1, it shows that only [29] and our scheme are secure to resist inside KGAs. Furthermore, the TTP is removed in our scheme.Table 1
A comparison of various schemes.
Schemes Inside KGAs Outside KGAs ZC ZT TrC TeC CiC [28] NO YES l G + l H 2lG 2Et Pt+2Et Pt+2Et [17] NO NO l G + l H lG E t Pt+Et P t + E t [29] YES YES 2lG 2lG+2lp 2Et Pt+2Et 2Et [25] NO YES 3lG+2lGT ls l G + l p Et 4Pt+3Et+tv [27] NO YES 2lG+lGT 2lGT Et 3 P t + E t Pt+4Et Ours YES YES lG+2lGT lG+lp Et P t + E t 3EtTo compare performance, letEt and Pt be the exponential operation and the pairing operation over a bilinear group, respectively. The size of Zp’s element is denoted by lp. Similarly, the character lG and lGT denote the size of G’s element and the size of GT’s element, respectively. The size of hash value denotes lH. For brevity, the calculation cost of creating trapdoor and keyword ciphertext denote TrC and CiC, respectively. The character ZC denotes the size of keyword ciphertext. The ZT denotes the size of trapdoor.From Table1, it shows that one Et is required to create trapdoor in our scheme. Compared with [29], our solution is more efficient to create trapdoor. Meanwhile, the performance overhead of testing is one Et and one Pt. In [29], it requires two Et and one Pt.Lastly, the test procedure can only be run by a specified server. This improves the security of the system.


## 5. Conclusion

With the wide application of cloud computing, data privacy has become one of critical security issues for mobile users. The ciphertext retrieval is one of the most useful approaches to achieve data privacy for cloud storage. In this paper, we first proposed a new architecture and security model to resist inside KGAs, which is a strong attack on the keyword search scheme. We also proposed an instance of the dCRKS system. Under the security model proposed in our paper, this new scheme has been proven secure to resist inside KGAs. Security analysis and efficiency comparison show that our scheme is effective for the retrieval of encrypted data in cloud computing.



---

*Source: 7254305-2018-06-06.xml*