# Secure and Efficient Searchable Public Key Encryption for Resource Constrained Environment Based on Pairings under Prime Order Group

Authors: Yu Zhang; Yin Li; Yifan Wang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Searchable public key encryption scheme is a key technique for protecting data confidentiality in today’s cloud environment. Specifically, public key encryption with conjunctive and disjunctive keyword search (PECDK) can provide flexible search options without sacrificing keywords security and thus attracts a lot of attention nowadays. However, the most effective PECDK scheme is based on the inner product encryption (IPE), which needs more time and space cost. In this paper, by utilizing the bilinear pairing with a prime order group, we propose an efficient PECDK scheme needing less time and storage consumption. The proposed scheme is proven to be secure under a rigorous security definition. The theoretical analysis and experimental results demonstrate that our proposed scheme can significantly improve the time and space efficiency over the state-of-the-art scheme.


---

## Body

## 1. Introduction

In the era of big data, more and more companies and individuals are willing to share their data over the cloud platform. If the data is stored in plaintext form, the cloud service providers can easily access and analyze the data illegally, which may lead to a big threaten to some sensitive data, e.g., electronic health and personal credit records. To protect data privacy, encrypting data before outsourcing it to the cloud server is a common approach. But, this brings a new issue of how to perform keyword search over these unreadable ciphertext. A straightforward solution is to download all the encrypted data to the client and decrypt it. After obtaining all unencrypted data, users can utilize the common information retrieval technique used on the plaintext to perform keywords query. However, this approach requires a very high communication, storage, and computing costs, which are not applicable for large scale networks. This issue put forward a new challenge: how to effectively search for encrypted data without decrypting it first.Searchable encryption (SE) is a promising method to address this problem. SE can be classified into two categories according to its applications: searchable symmetric key encryption (SSE) and searchable public key encryption (SPE). Based on many researchers’ work these years, SSE can support advanced query conditions like Boolean keywords search, multikeywords rank search, and top-k similarity keywords search. Works [1–3] dealt with multikeywords search, where the query condition contains more than one keyword. Considering the fact that it is not practical to return all the search results, more recent works like [4–6] focused on the multikeywords rank search. Sometimes, users want to search documents related to their query keywords rather than the documents that precisely match those keywords. The SSE schemes supporting similarity keywords search were created to address this issue [7, 8].Conversely, SPE is difficult to support advanced search function without sacrificing security as anyone who has the public key (pk) can create encrypted index or ciphertext, and easily perform chosen keywords attack. In addition, the SSE scheme is generally more efficient than the SPE scheme. Although the SPE scheme has these weaknesses, it still holds some advantages for many applications. Specifically, for the application in which there are many data senders and only one data receiver (Figure 1), SSE needs that all senders and the receiver hold the same symmetric key to generate the encrypted data. So, if one of the senders is compromised by an adversary, then the data for all senders will be leaked. Compared with SSE, in SPE, the public key can be accessed by all senders, and the private key is only given to the receiver. Thus, SPE can naturally solve the security problem of key management in this application [9] and is an irreplaceable solution.Figure 1
Architecture of searchable public key encryption (SPE).The first SPE named as public key encryption with keyword search (PEKS) was introduced in [10], in which senders who hold pk can send their encrypted documents with encrypted indexes to a server, and the receiver holding secret key (sk) can make a keyword search over the encrypted data. However, this scheme only supports a single keyword search. How to construct a public key encryption scheme supporting a complex query conditions such as the Boolean keyword search is a significant problem. Specifically, as two typical Boolean keyword search schemes, conjunctive and disjunctive keyword search over encrypted data in the public key setting are needed to be developed.Park et al. [11] first proposed the public key encryption with conjunctive keyword search (PECK) scheme that supports keywords search like w1∧w2∧w3, where w1,w2 and w3 are query words. After that, many PECK schemes [12, 13] were proposed to improve the efficiency and security. The first public key encryption with disjunctive keyword search (PEDK) scheme was proposed by Katz et al. [14]. In their work, they proposed an inner product encryption (IPE) scheme and converted this IPE scheme into a PEDK scheme, which supports keywords search like w1∨w2∨w3. In an IPE scheme, the secret key corresponding to a predicate vector v→ can decrypt the ciphertext associated with an attribute vector x→ if and only if x→·v→=0. According to this property, we know that, by converting index and query keyword set into an attribute and a predicate vector, respectively, an IPE scheme can be changed into a SPE scheme supporting multikeywords search.In the practical cloud environment, the user usually perform conjunctive and disjunctive keywords search simultaneously. In [15], Zhang and Lu proposed an approach of converting an IPE scheme into a public key encryption with conjunctive and disjunctive keyword search (PECDK) scheme and gave a concrete scheme. In their scheme, the size of each document’s index, the size of a trapdoor, and the time cost of pairing operations in the test process are all O(N). Since N is the number of keywords in a dictionary, the previous PECDK scheme is impractical if N is a large integer. Inspired by this problem, we proposed a new approach to build an efficient PECDK scheme with less time and space overhead [16]. However, these two PECDK schemes are based on the IPE scheme [17], which is a costly cryptographic prototype. In this paper, we aim to build an efficient PECDK scheme using an alternative method.Main Works. In the scheme introduced in [17], the user first converts an index and a query keyword set into an attribute and a predicate vector, respectively. After this, the user can construct encrypted index and trapdoor by applying the attribute and predicate vectors to the encryption and key generation algorithms of IPE. The keyword search process can be executed by adopting the decryption algorithm of IPE. However, this scheme is constructed by utilizing many group operations due to being based on the IPE scheme. The IPE scheme adopts a technique called dual pairing vector space (DPVS), which generates n2 group elements to create the public key and secret key. By using these keys, both the storage size of the obtained indices and the time cost of the search process are linear with O(n2). To address this issue, we aim to create an efficient PECDK scheme without using IPE as the infrastructure. We take advantage of the conversion method similar to the one introduced in [16] for creating a group of vectors. Then, by applying these vectors to the prime order pairing groups, a PECDK scheme with a better time and space complexity than the previous schemes is presented. Security of our construction is based on decision linear Diffie-Hellman (DLIN) assumption in the random oracle model. In addition, we design an experiment that verifies the efficiency of the proposed scheme and give a detailed comparison with the previous scheme. The experiment result shows that the key generation, index building, trapdoor generation, and testing algorithms in our scheme are more efficient than those in the previous one. Besides, the space cost for indices in our scheme is also less than that in the previous one. In practice, client device, e.g., a mobile device, has less storage space and limited computation capacity. Thus, compared with the previous scheme, ours is much more suitable for the resource constrained environment.Related Work. There are two classes of searchable encryption schemes in terms of different cryptography primitives: searchable symmetric key encryption (SSE) and searchable public key encryption (SPE).SSE. Song et al. [18] introduced the definition of searching on encrypted data and gave a concrete scheme. Then, Goh [19] defined a formal security definition for SSE and presented an effective conjunctive keywords search scheme by using a technique called Bloom Filter. Soon afterward, many works [20, 21] were constructed to improve the search efficiency and security level. These schemes failed to achieve a sublinear search speed. To address this issue, by taking advantage of tree structures, such as r-tree and kd-tree, SSE schemes with sublinear search time were released in [22, 23]. The SSE scheme supporting Boolean keywords search with sublinear search time was given in [24]. In order to support queries with rich expressiveness, SSE schemes supporting media data and similarity keywords search are introduced in [25, 26]. More important, these works also support dynamic update. In practical application, the search engine should return the top-k related documents to users instead of returning all the search results. Some SSE schemes, supporting rank search, are proposed in [4–6] to obtain more accurate query results.SPE. The first SPE scheme is called public key encryption with keyword search (PEKS), which was proposed by Boneh et al. [10]. Then, Abdalla et al. [27] defined the computational and statistical consistency in PEKS and presented a statistically consistent scheme. However, this work only supports a single keyword search. The concept of PECK was first proposed in [11]. They defined the security model of this mechanism and gave two constructions. One requires many bilinear pairing operations, while the other needs more private keys. Hwang and Lee [28] designed a more efficient scheme in a multiple users setting. However, all these constructions use the keyword field as additional information for keyword search. The keyword field may leak more information to the public. To eliminate the keyword field, Boneh and Waters [29] presented a public key encryption scheme called hidden vector encryption (HVE), which supports a conjunctive search, comparison queries (x≥a), and subset queries (x∈S) on encrypted data.In order to create a SPE scheme supporting disjunctive keyword search, katz et al. [14] proposed a public key encryption scheme called inner product encryption (IPE), which is related to the attribute-based encryption (ABE) [30, 31]. Recently, in order to better utilize the encrypted data and improve the security, some public key schemes which can support verifiable attribute-based search over outsourced encrypted data are proposed in [32–37]. For supporting advanced keywords search function, Zhang and Lu proposed the first PECDK scheme [15] by combining an efficient IPE scheme [17] and a keyword conversion method. However, their scheme is a costly solution due to using an IPE scheme. In fact, the PECDK scheme based on an IPE scheme needs more computation and storage cost than the one without utilizing an IPE scheme as a foundation. Therefore, in this paper, we will find a new method irrelevant to IPE to construct a more efficient PECDK scheme.Organization. The remainder of the paper is organized as follows: The model and security definitions of PECDK are defined in Section 2. In Section 3, we propose our PECDK scheme and give the security proof for the scheme. The analysis of the presented PECDK scheme is described in Section 4. Section 5 presents some conclusions.


## 2. Preliminaries

In this section, we will give a formal definition of the PECDK model and the corresponding security model. Our scheme is based on this model and proven to be secure under this security model. Moreover, we also briefly introduce some basic ingredients used to create our scheme, including the bilinear pairing and the complexity assumption.


### 2.1. Model of PECDK

In PECDK, letpk,sk be the receiver’s public key and secret key. When a sender wants to send a message M to a receiver with keywords w1,w2,…,wn, she uses the standard public key encryption system to encrypt M and uses pk and keywords w1,w2,…,wn to construct the encrypted index of M. After that, she sends the encrypted message M and the encrypted index of M to the server. When the receiver wants to retrieve messages including a specific list of keywords, he takes the sk, a symbol, and keyword set Q as input to construct a trapdoor TQ and sends TQ to the server. Note that the symbol is used to refer to the type of query, e.g., conjunctive form or disjunctive form. When the server receives the trapdoor, it tests each encrypted index by using the trapdoor and returns the matched messages to the receiver.According to the description above, we give the model of PECDK based on the previous definition introduced in [16].Definition 1.
There are four probabilistic polynomial time algorithms in the PECDK scheme. There are KenGen, IndexBuild, Trapdoor, and Test:(1)
KeyGen(1γ): choosing a security parameter γ, this algorithm outputs the key pair (pk,sk) in which pk is the public key and sk is the secret key.(2)
IndexBuild(pk,W): the algorithm is performed by the sender to produce an encrypted index IW by using a keyword set W={w1,w2,…,wn} and pk.(3)
Trapdoor(sk,{Q,sym}): the receiver runs this algorithm to produce a trapdoor. It takes sk, sym∈{∨,∧}, and the keyword query Q={q1,q2,…,qm} as input to generate a trapdoor TQ, where m≤n. ∨ and ∧ represent disjunctive and conjunctive keywords search, respectively.(4)
Test(pk, TQ, IW): it takes the trapdoor TQ={tQ,sym}, the secure index IW, and the public key pk as input. If sym is ∧, it means that the trapdoor is for conjunctive keywords search. In this case, the output is 1 if Q⊆W, or 0 otherwise. If sym is ∨, disjunctive keywords search should be performed. In this case, if Q∩W≠ϕ, it outputs 1, or 0 otherwise.Correctness Property.Let {Q,sym} and W be a query and a keyword set, respectively. Suppose that pk, sk, IW, and TQ are correctly generated by KeyGen(γ), IndexBuild(pk,W), and Trapdoor(sk,{Q,sym}), respectively. The correctness property of PECDK involves two situations described as follows.(1)
When there is a conjunctive keywords search (sym is ∧), Test(pk,TQ,IW)=1 holds if Q⊆W. Otherwise, it holds with negligible probability.(2)
When there is a disjunctive keywords search (sym is ∨), Test(pk,TQ,IW)=1 holds if Q∩W≠ϕ. Otherwise, it holds with negligible probability.In practical use, if a sender would like to send a messageM with keyword set W, a ciphertext with the form of {Enc(pk,M), IndexBuild(pk,W)} will be created, where Enc(·) is a frequently used public key encryption scheme, e.g., RSA. Similar with other related works [10, 11, 28], the proposal only concentrate on searchable encryption part, which is PECDK in this paper.


### 2.2. Security Definition of PECDK

Since previous PECDK schemes are based on the IPE scheme, the security definition also depends on the security of IPE. For the PECDK scheme without using IPE, we need to give a new security definition. Inspired by the previous security definition called indistinguishability of ciphertext from random (IND-CR-CKA) introduced in [28], we define a security game under the PECDK model.The security game is described as follows.(1)
Setup: the challengerC runs the KeyGen(1γ) algorithm to generate the public key pk and the secret key sk. Then, C gives pk to the attacker A.(2)
Phase 1: the attackerA can adaptively ask the challenger C for the trapdoor TQ for any query Q of his choice.(3)
Challenge:A selects a target keyword set W∗ and sends it to C. After receiving W∗, C selects a random keyword set R and sets W0=W∗ and W1=R. Suppose that {Q1,sym1}, {Q2,sym2}, …, {Qt,symt} are queries which are asked to construct trapdoors in Phase 1, where t is the number of trapdoors queried in Phase 1. For each i∈[1,t], the only restriction is that Qi∩W0=0=Qi∩W1, where the number of the keywords in Qi∩W0 and Qi∩W1 is denoted by Qi∩W0 and Qi∩W1, respectively. Then, C picks a random bit β∈{0,1}, produces Iβ=IndexBuild(pk,Wβ), and sends {Iβ,W0,W1} to A.(4)
Phase 2:A can continue to ask for trapdoor TQ for any query Q of his choice, and subject to the same restriction as before.(5)
Response:A outputs β′∈{0,1} and wins the game if β′=β.A’s advantage can be expressed as a function of the security parameter (1γ): (1)AdvAGame1γ=Prβ′=β-12Then, we have the following definition.Definition 2.
According to the game above, a PECDK is semantic secure if, for any probabilistic polynomial time attackerA, the function AdvAGame(1γ) is negligible.


### 2.3. Bilinear Pairings

LetG1, G2 be two cyclic groups of prime order q. There are three properties in the bilinear pairings map e^:G1×G1→G2.(1)
Bilinear:e^(au,bv)=e^(a,b)uv, where a,b∈G1 and u,v∈Zq∗.(2)
Nondegenerate: ifg∈G1, then e^(g,g)∈G2.(3)
Computable: for anya,b∈G1, e^(a,b) can be efficiently computable.An efficient bilinear map can be obtained by applying the Weil pairing or the Tate pairing [38].


### 2.4. Complexity Assumption

We review the complexity assumption named Decisionl Bilinear Diffie-Hellman Inversion (Decision l-BDHI) assumption [11], which is related to the bilinear pairing. The security of our scheme is based on this assumption.Decision l -BDHI Assumption: Given a tuple D={g,gx,gx2,…,gxl} with the random choice of x∈Zq∗ and g∈G1, it is argued that an algorithm C outputting b∈{0,1} has advantage ε in solving thedecision l-BDHI problem in G1 if (2)AdvBD-l-BDHI=PrBD,e^g,g1/x=1-PrBD,R=1≥εwhere the probability (Pr[·]) is over the random choice R∈G2 and random bits chosen by C.Definition 3.
The Decision l-BDHI assumption holds inG1, if no probabilistic polynomial time algorithm has advantage at least ε in solving the Decision l-BDHI problem in G1.


## 2.1. Model of PECDK

In PECDK, letpk,sk be the receiver’s public key and secret key. When a sender wants to send a message M to a receiver with keywords w1,w2,…,wn, she uses the standard public key encryption system to encrypt M and uses pk and keywords w1,w2,…,wn to construct the encrypted index of M. After that, she sends the encrypted message M and the encrypted index of M to the server. When the receiver wants to retrieve messages including a specific list of keywords, he takes the sk, a symbol, and keyword set Q as input to construct a trapdoor TQ and sends TQ to the server. Note that the symbol is used to refer to the type of query, e.g., conjunctive form or disjunctive form. When the server receives the trapdoor, it tests each encrypted index by using the trapdoor and returns the matched messages to the receiver.According to the description above, we give the model of PECDK based on the previous definition introduced in [16].Definition 1.
There are four probabilistic polynomial time algorithms in the PECDK scheme. There are KenGen, IndexBuild, Trapdoor, and Test:(1)
KeyGen(1γ): choosing a security parameter γ, this algorithm outputs the key pair (pk,sk) in which pk is the public key and sk is the secret key.(2)
IndexBuild(pk,W): the algorithm is performed by the sender to produce an encrypted index IW by using a keyword set W={w1,w2,…,wn} and pk.(3)
Trapdoor(sk,{Q,sym}): the receiver runs this algorithm to produce a trapdoor. It takes sk, sym∈{∨,∧}, and the keyword query Q={q1,q2,…,qm} as input to generate a trapdoor TQ, where m≤n. ∨ and ∧ represent disjunctive and conjunctive keywords search, respectively.(4)
Test(pk, TQ, IW): it takes the trapdoor TQ={tQ,sym}, the secure index IW, and the public key pk as input. If sym is ∧, it means that the trapdoor is for conjunctive keywords search. In this case, the output is 1 if Q⊆W, or 0 otherwise. If sym is ∨, disjunctive keywords search should be performed. In this case, if Q∩W≠ϕ, it outputs 1, or 0 otherwise.Correctness Property.Let {Q,sym} and W be a query and a keyword set, respectively. Suppose that pk, sk, IW, and TQ are correctly generated by KeyGen(γ), IndexBuild(pk,W), and Trapdoor(sk,{Q,sym}), respectively. The correctness property of PECDK involves two situations described as follows.(1)
When there is a conjunctive keywords search (sym is ∧), Test(pk,TQ,IW)=1 holds if Q⊆W. Otherwise, it holds with negligible probability.(2)
When there is a disjunctive keywords search (sym is ∨), Test(pk,TQ,IW)=1 holds if Q∩W≠ϕ. Otherwise, it holds with negligible probability.In practical use, if a sender would like to send a messageM with keyword set W, a ciphertext with the form of {Enc(pk,M), IndexBuild(pk,W)} will be created, where Enc(·) is a frequently used public key encryption scheme, e.g., RSA. Similar with other related works [10, 11, 28], the proposal only concentrate on searchable encryption part, which is PECDK in this paper.


## 2.2. Security Definition of PECDK

Since previous PECDK schemes are based on the IPE scheme, the security definition also depends on the security of IPE. For the PECDK scheme without using IPE, we need to give a new security definition. Inspired by the previous security definition called indistinguishability of ciphertext from random (IND-CR-CKA) introduced in [28], we define a security game under the PECDK model.The security game is described as follows.(1)
Setup: the challengerC runs the KeyGen(1γ) algorithm to generate the public key pk and the secret key sk. Then, C gives pk to the attacker A.(2)
Phase 1: the attackerA can adaptively ask the challenger C for the trapdoor TQ for any query Q of his choice.(3)
Challenge:A selects a target keyword set W∗ and sends it to C. After receiving W∗, C selects a random keyword set R and sets W0=W∗ and W1=R. Suppose that {Q1,sym1}, {Q2,sym2}, …, {Qt,symt} are queries which are asked to construct trapdoors in Phase 1, where t is the number of trapdoors queried in Phase 1. For each i∈[1,t], the only restriction is that Qi∩W0=0=Qi∩W1, where the number of the keywords in Qi∩W0 and Qi∩W1 is denoted by Qi∩W0 and Qi∩W1, respectively. Then, C picks a random bit β∈{0,1}, produces Iβ=IndexBuild(pk,Wβ), and sends {Iβ,W0,W1} to A.(4)
Phase 2:A can continue to ask for trapdoor TQ for any query Q of his choice, and subject to the same restriction as before.(5)
Response:A outputs β′∈{0,1} and wins the game if β′=β.A’s advantage can be expressed as a function of the security parameter (1γ): (1)AdvAGame1γ=Prβ′=β-12Then, we have the following definition.Definition 2.
According to the game above, a PECDK is semantic secure if, for any probabilistic polynomial time attackerA, the function AdvAGame(1γ) is negligible.


## 2.3. Bilinear Pairings

LetG1, G2 be two cyclic groups of prime order q. There are three properties in the bilinear pairings map e^:G1×G1→G2.(1)
Bilinear:e^(au,bv)=e^(a,b)uv, where a,b∈G1 and u,v∈Zq∗.(2)
Nondegenerate: ifg∈G1, then e^(g,g)∈G2.(3)
Computable: for anya,b∈G1, e^(a,b) can be efficiently computable.An efficient bilinear map can be obtained by applying the Weil pairing or the Tate pairing [38].


## 2.4. Complexity Assumption

We review the complexity assumption named Decisionl Bilinear Diffie-Hellman Inversion (Decision l-BDHI) assumption [11], which is related to the bilinear pairing. The security of our scheme is based on this assumption.Decision l -BDHI Assumption: Given a tuple D={g,gx,gx2,…,gxl} with the random choice of x∈Zq∗ and g∈G1, it is argued that an algorithm C outputting b∈{0,1} has advantage ε in solving thedecision l-BDHI problem in G1 if (2)AdvBD-l-BDHI=PrBD,e^g,g1/x=1-PrBD,R=1≥εwhere the probability (Pr[·]) is over the random choice R∈G2 and random bits chosen by C.Definition 3.
The Decision l-BDHI assumption holds inG1, if no probabilistic polynomial time algorithm has advantage at least ε in solving the Decision l-BDHI problem in G1.


## 3. PECDK Scheme

Based on previous definitions and notations, in this section, we give our PECDK scheme without using IPE. Our scheme mainly involves three steps. Initially, we utilize a keyword conversion method inspired by the approach introduced in [16] to convert the index and query keywords into a set of vectors. Moreover, by applying the bilinear pairing under the prime order group, we encrypt these vectors to construct encrypted index and trapdoor. Eventually, a test algorithm is built to perform secure keywords query. The method adopted in the first step is described in Section 3.1, and the algorithms used in the second and third steps are given in Section 3.2.


### 3.1. Keywords Conversion Method

The keywords in query and index are strings; thus we need to change all the keywords to a group of integers. Moreover, in order to verify whether the query matches the index or not, the integers between the query and index must hold some relationships. According to these concerns, we introduce a method that can convert the index and query set into a matrix and a vector.This method is based on the relationship between the roots and coefficients in an equation of degreen with one unknown. Specifically, the roots and coefficients are used to create a matrix of index keywords and a vector of query keywords, respectively. By adopting a prime order group to encrypt the matrix and vector, an encrypted index and query can be built. The relationship between the matrix and vector can be utilized to construct the test algorithm.Suppose that any keywordw can be expressed as {0,1}∗; we define a function H1:{0,1}∗→Zp∗. Since p is a large prime and is larger than the number of all words, H1 can be collision-resistance. This means that, if i≠j, then H1(wi)≠H1(wj), where wi and wj are two distinct keywords. Let W={w1,w2,…,wn} and Q={q1,q2,…,qm} be two keyword sets, where m<n. The method can be listed into three steps and described as follows.(1)
For the keyword setW={w1,w2,…,wn}, we construct a matrix for W: (3)H1w10H1w11⋯H1w1nH1wi0H1wi1⋯H1win⋮⋮⋱⋮H1wn0H1wn1⋯H1wnnNote that H1(w1),H1(w2),…,H1(wn) can be seen as the roots of equation:(4)fx=x-H1w1x-H1w2…x-H1wn(2)
For the query{q1,q2,…qm}, we create an equation:(5)fx=x-H1q1x-H1q2…x-H1qm=amxm+am-1xm-1+…+a0x0According to the coefficient of the f(x), a vector a→={a0,a1,…,am} can be obtained.(3)
Suppose thatw→i={H1(wi)0,H1(wi)1,…,H1(wi)m} is from the i-th row of the matrix (3); we can infer that if there is a keyword wi∈W such that wi∈Q, where i∈[1,m], according to (5), it is not difficult to verify that a→·w→i=0. Based on this property, we can build the test algorithm.


### 3.2. Construction of PECDK

By combining the keyword conversion method and the bilinear pairing under prime order group, we propose a PECDK scheme which allows the user to perform conjunctive and disjunctive keyword search over encrypted data. Our key idea is as follows. First, by adopting the keyword conversion method introduced in Section3.1, we change the index and query keyword set into an index matrix and a query vector, respectively. Then, by using a set of elements randomly chosen from the prime order group, we encrypt the index matrix to the secure index and the query vector to the trapdoor, respectively. Specifically, in order to guarantee the scheme’s security, the encryption process relies strictly on the complexity assumption given in Section 2.4. Finally, by taking advantage of the properties of the bilinear pairing, both conjunctive and disjunctive keywords search can be achieved. Specifically, for the conjunctive keywords search, the matched documents are returned if and only if all the keywords in the query are including in the index keyword set. For the disjunctive logic query, the matched documents are returned if and only if the intersection between the index and the query keyword set is not an empty set.According to the above ideas, the concrete construction is proposed in the following paragraphs. Because of making use of the prime order group, the proposed scheme is more efficient than the previous scheme adopting the IPE crypto-system on the time and space complexities. Experimental results showing the advantages of our scheme can be found in Section4.(i)
KeyGen(1γ): given a security parameter γ, the algorithm generates two cyclic groups G1,G2 of prime order q and a bilinear pairing e^:G1×G1→G2. It picks a random generator g of G1 and two hash functions H1:{0,1}∗→Zq∗ and H2:G2→{0,1}log2⁡q. Choosing 2n+3 random numbers α0,α1,…,αn,β0,β1,…,βn,θ∈Zq∗, it computes {X0=gα0,X1=gα1,…,Xn=gαn,Y0=gβ0,Y1=gβ1,…,Yn=gβn,Z=gθ,μ=e^(g,g)}. After this, it outputs the public key pk={X0,X1,…,Xn,Y0,Y1,…,Yn,Z,μ,g,H1,H2,e^} and the secret key sk={α0,α1,…,αn,β0,β1,…,βn,θ}, where pk is also open to the public.(ii)
IndexBuild(pk,W): the algorithm generates n2+2n random numbers r1,r2,…,rn and uij∈Zq∗, where i∈[1,n],j∈[0,n]. Given a keyword set W={w1,w2,…,wn} and the public key pk, for each word wi∈W, it computes Aij=Xjri×griH1(wi)j+uij,Bij=Yjuij,Ci=Zri=gθri and Di=H2(μri), where i∈[1,n] and j∈[0,n]. The index of the keyword set W is(6)IW=A10A11…A1nB10B11…B1nC1D1A20A21…A2nB20B21…B2nC2D2⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮An0An1…AnnBn0Bn1…BnnCnDnNote that the secure index can be seen as an encrypted version of matrix (3).(iii)
Trapdoor(sk,{Q,sym}): when the algorithm receives a keyword query Q={q1,q2,…,qm}, where m≤n, it will construct a vector a→={am,am-1,…,a0} by utilizing (5). Given a vector a→ and sk, t1j=gaj/∑j=0mαjaj+∑j=0majuθ and t2j=t1j1/βj can be computed, where u is a random number in Zq and j∈[0,m]. Let t3=u and sym∈{∨,∧}; the trapdoor for the keyword query Q is TQ=(t10,t11,…,t1m,t20,t21,…,t2m,t3,sym).(iv)
Test(pk,TQ,IW): when the algorithm receives a trapdoor TQ and a secure index IW, it works as follows:
(1)
If the symbol inTQ is ∨,
(a)
The algorithm chooses a counteri and sets i=1.(b)
Ifi>n, then it goes to step (c); otherwise it checks whether H2(testi1/testi2)=Di, where testi1=∏j=0me^(t1j,AijCit3),testi2=∏j=0me^(t2j,Bij). If so, the algorithm outputs 1 and ends. Otherwise, it sets i=i+1 and goes to step (b).(c)
The algorithm outputs0 and ends.(2)
If the symbol inTQ is ∧,
(a)
The algorithm chooses two countersi and j and sets i=1 and j=1.(b)
Ifi>n, then it goes to step (c); otherwise it tests whether H2(testi1/testi2)=Di, where testi1=∏j=0me^(t1j,AijCit3),testi2=∏j=0me^(t2j,Bij). If so, then the algorithm sets j=j+1. Otherwise, it does nothing. After that, it sets i=i+1 and goes to step (b).(c)
Ifj=m, the algorithm outputs 1 and ends. Otherwise, it outputs 0 and ends.Correctness.The key idea of disjunctive keywords search is to determine whether there exists an i∈[1,n] such that wi∈Q. For the conjunctive keywords search, we need to check whether there are m keywords wϕ(1),wϕ(2),…,wϕ(m) such that wϕ(j)∈Q, where ϕ(j)∈[1,n] and j∈[1,m]. According to these ideas, we know that the essence of test algorithm is to verify whether wi∈Q. In the proposed scheme, it is can be verified that testi1/testi2=e^(g,g)ri+ri∑j=0majH1(wi)j/∑j=0mαjaj+∑j=0majuθ. If wi∈Q, there is ∑j=0majH1(wi)j=0. Thus, it must be testi1/testi2=e^(g,g)ri and H2(testi1/testi2)=Di. Based on this, we argue that our scheme is correct.


### 3.3. Security Analysis

Theorem 4.
The proposed PECDK scheme is secure according to security definition in the random model if Decision(qT+1)-BDHI is hard.Proof.
Suppose that an algorithmA has advantage ε in breaking the PECDK under the security definition. Suppose A makes at most qT trapdoor queries, we can build an algorithm C which solves the decision (qT+1)-BDHI assumption with a probability at least ε′=ε/e(nqT+1), where e is the base of the natural logarithm, and n is the number of keywords in an index. Let g be a generator of G1. Given g,gx,gx2,…,gxqT+1,R, if R=e^(g,g)1/x, the algorithm C outputs 1, 0 otherwise. The interaction between the algorithm C and the algorithm A is as follows: (i)
Setup: the algorithm C works as follows:
(1)
The algorithmC randomly chooses qT numbers ρ1,ρ2,…,ρqT∈Zq∗ and returns f(z)=∏i=1qT(z+ρi)=∑i=0qTcizi.(2)
C computes U=gf(x)=g∑i=0qTcixi,V=gxf(x)=g∑i=0qTcixi+1, and fi(z)=1/z+ρif(z)=∑i=0qT-1dizi, where i∈[1,qT]. Then, C gets U1/x+ρi=gfi(x)=g∑i=0qT-1dixi and stores the pairs ρi,gfix in a list namedS-list, where i∈[1,qT].(3)
C computes f(z)-c0/z=∑i=1qTcizi-1 and sets RU=e^(g∑i=1qTcixi-1,g∑i=0qTcixi+c0)×Rc02. If R=e^(g,g)1/x, RU=e^(g∑i=1qTcixi-1,g∑i=0qTcixi+c0)×Rc02=e^(gf(x)-c0/x,gf(x)+c0)×Rc02=e^(g,g)f2(x)-c02/x×e^(g,g)c02/x=e^(g,g)f2(x)/x=e^(U,U)1/x.(4)
C randomly chooses 2n+4 numbers s0,s1,…,sn,t0,t1,…,tn,η, λ∈Zq∗ and constructs Xi=Vsi×U-ηi,Yi=Uti for each i∈[0,n]. Let Z=Vλ, C gives A the public key pk={U,X0,X1,…,Xn,Y0,Y1,…,Yn,Z,μ=e^(U,U),g,H1,H2,e^}. The corresponding sk is s0x-η0,s1x-η1,…,snx-ηn,t0,t1,…,tn,λx, where the values s0x-η0,s1x-η1,…,snx-ηn,λx are unknown to C.(ii)
H1,H2-queries: the random oracles H1 or H2 can be queried by A at any time. To answer H1-queries, C keeps a list of tuples (wj,hj,σj) called H1-list which is empty initially. When A queries the random oracle H1 at a point wi∈0,1∗, algorithm C answers as follows:H1-queries:
(1)
If the querywi is already in a tuple (wi,hi,σi) on H1-list, then C responds with H1(wi)=hi, where hi∈Zq∗.(2)
Otherwise,C generates a random coin σi∈[0,nqT] so that Pr[σi=0]=1/nqT+1.(3)
Ifσi=0, C sets hi=η. Otherwise, C picks a random ai∈Zq∗ and sets hi=ai.(4)
C adds the tuple (wi,hi,σi) to H1-list and answers A with H1(wi)=hi.H2-queries are similar to H1-queries. To answer H2 queries from A, C holds a list of tuples (φj,ψj) called H2-list which is initially empty. When A queries the random oracle H2 at a point φi∈G2, algorithm C responds as follows:H2-queries:
(1)
If the queryφi already appears on H2-list in a tuple (φi,ψi), then C responds with H2(φi)=ψi, where ψi∈0,1log2⁡q.(2)
Otherwise,C picks a random bi∈0,1log2⁡q and sets ψi=bi.(3)
C adds the tuple (φi,ψi) to H2-list and responds A with H2(φi)=ψi.(iii)
Trapdoor queries: when A queries a trapdoor of the keyword set Qi=qi1,qi2,…,qim and sym, the algorithm C answers as follows:
(1)
C runs H1-queries algorithm to obtain hij, where hij=H1(qij) for each j∈[1,m]. Let (wij,hij,σij) be the corresponding tuples on H1-list, for each j∈[1,m]; if σij=0, then C reports failure and terminates.(2)
Otherwise,C constructs a trapdoor for query Qi,sym. C first computes f′x′=∏i=1m(x′+hij)=am′x′m+am-1′x′m-1+…+a1′x′+a0′. Then, for each j∈[0,m], C can compute lij=-∑j=0maj′ηj/aj′ρi and νi=-∑j=0maj′ηj+ρi∑j=0maj′sj/ρiλ∑j=0maj′ through an equality of 1/x′+ρi=aj′lij/∑j=0maj′(sjx′-ηj)+νiλ∑j=0maj′x′. Obviously, (U1/(x′+ρi)li0,U1/(x′+ρi)li1,…,U1/(x′+ρi)lim, U1/(x′+ρi)li0t0,U1/(x′+ρi)li1t1,…,U1/(x′+ρi)limtm,νi, sym) is the trapdoor for the keyword query Qi.(3)
C searches S-list to obtain the tuple ρi,gfix′. Then C sends (gfi(x′)/li0, gfi(x′)/li1, …, gfi(x′)/lim, gfi(x′)/li0t0, gfi(x′)/li1t1, …,gfi(x′)/limtm,νi,sym) to the algorithm A as the correct trapdoor for the query Qi(iv)
Challenge: algorithm A produces a keyword set W∗={w01,w02,…,w0n}, which is what A wants to challenge. Then, A sends the target keyword set W∗ to C. C chooses a random keyword set R′={w11,w12,…,w1n} and sets W0=W∗ and W1=R′. The only restriction is that the previous trapdoor queries cannot distinguish W0 and W1. If there is any previous trapdoor that can break the restriction, C regenerates the keyword set W1. Then C selects a random bit β∈0,1 and runs the above algorithm for responding to H1-queries to obtain the values hβ1,hβ2,…,hβn, where H1(wβi)=hβi,wβi∈Wβ,i∈[1,n]. Let (wβi,hβi,σβi) be the corresponding tuples on H1-list, if there is no σβi=0 for all i∈[1,n], then C terminates. Otherwise, C generates the challenge PECDK index Iβ of Wβ as follows:
(1)
Ifσβi=0, C computes Aβij=Urβisj+yβij, Bβij=Utjyβij, Cβi=Urβiλ, and Dβi=H2(RUrβi), where j∈[0,n]. Observe that if R=e^(g,g)1/x, then RU=e^(U,U)1/x. So, the above values are equivalent to Aβij=Xjrβi/x×Urβiηj/x+yβij, Bβij=Yjyβij, Cβi=Zrβi/x, and Dβi=H2(e^(U,U)rβi/x), where j∈[0,n]. It means that this is a valid PECDK encryption of keyword wβi when R=e^(g,g)1/x.(2)
Otherwise,C computes Aβij=Vrβisj×Urβihβij+yβij-rβiηj, Bβij=Utjyβij, Cβi=Vrβiλ, Dβi=H2(e^(U,U)rβi), where j∈[0,n].(3)
C sends (7)Iβ=Aβ10Aβ11…Aβ1nBβ10Bβ11…Bβ1nCβ1Dβ1Aβ20Aβ21…Aβ2nBβ20Bβ21…Bβ2nCβ2Dβ2⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮Aβn0Aβn1…AβnnBβn0Bβn1…BβnnCβnDβnand two keyword sets W0 and W1 to A.(v)
More queries: A continues to inquire trapdoor queries. The restriction is similar to thechallenge phase.(vi)
Response: A outputs a guess β′∈{0,1}. C will output 1 if β′=β. Otherwise, C will output 0.
Now, we show that the algorithmC can solve the decision (qT+1)-BDHI assumption with probability at least ε′=ε/e(nqT+1). First of all, we should analyze the probability that C does not abort intrapdoor queries phase andchallenge phase. We define two events:
ω 1: C does not abort due to any of A’s trapdoor queries.
ω 2: C does not abort inchallenge phase for generating Iβ.
Suppose thatqT is large enough. Therefore, the probability of the event ω1 is at least (1-1/nqT+1)nqT≥1/e. The probability of the event ω2 is 1/nqT+1.
IfR=e^(g,g)1/x, A’s view is identical to its view in a real attack game. Since we assume that A can break the PECDK scheme with an advantage ε, it must satisfy Prβ′=β-1/2≥ε. If R is a random number, where R∈G2, then |Pr[β′=β]|=1/2 since A made a random guess.
Therefore, letD={g,gx,gx2,…,gxqT+1}; we have that (8)PrBD,e^g,g1/x=1-PrBD,R=1≥εenqT+1Then we conclude the theorem.


## 3.1. Keywords Conversion Method

The keywords in query and index are strings; thus we need to change all the keywords to a group of integers. Moreover, in order to verify whether the query matches the index or not, the integers between the query and index must hold some relationships. According to these concerns, we introduce a method that can convert the index and query set into a matrix and a vector.This method is based on the relationship between the roots and coefficients in an equation of degreen with one unknown. Specifically, the roots and coefficients are used to create a matrix of index keywords and a vector of query keywords, respectively. By adopting a prime order group to encrypt the matrix and vector, an encrypted index and query can be built. The relationship between the matrix and vector can be utilized to construct the test algorithm.Suppose that any keywordw can be expressed as {0,1}∗; we define a function H1:{0,1}∗→Zp∗. Since p is a large prime and is larger than the number of all words, H1 can be collision-resistance. This means that, if i≠j, then H1(wi)≠H1(wj), where wi and wj are two distinct keywords. Let W={w1,w2,…,wn} and Q={q1,q2,…,qm} be two keyword sets, where m<n. The method can be listed into three steps and described as follows.(1)
For the keyword setW={w1,w2,…,wn}, we construct a matrix for W: (3)H1w10H1w11⋯H1w1nH1wi0H1wi1⋯H1win⋮⋮⋱⋮H1wn0H1wn1⋯H1wnnNote that H1(w1),H1(w2),…,H1(wn) can be seen as the roots of equation:(4)fx=x-H1w1x-H1w2…x-H1wn(2)
For the query{q1,q2,…qm}, we create an equation:(5)fx=x-H1q1x-H1q2…x-H1qm=amxm+am-1xm-1+…+a0x0According to the coefficient of the f(x), a vector a→={a0,a1,…,am} can be obtained.(3)
Suppose thatw→i={H1(wi)0,H1(wi)1,…,H1(wi)m} is from the i-th row of the matrix (3); we can infer that if there is a keyword wi∈W such that wi∈Q, where i∈[1,m], according to (5), it is not difficult to verify that a→·w→i=0. Based on this property, we can build the test algorithm.


## 3.2. Construction of PECDK

By combining the keyword conversion method and the bilinear pairing under prime order group, we propose a PECDK scheme which allows the user to perform conjunctive and disjunctive keyword search over encrypted data. Our key idea is as follows. First, by adopting the keyword conversion method introduced in Section3.1, we change the index and query keyword set into an index matrix and a query vector, respectively. Then, by using a set of elements randomly chosen from the prime order group, we encrypt the index matrix to the secure index and the query vector to the trapdoor, respectively. Specifically, in order to guarantee the scheme’s security, the encryption process relies strictly on the complexity assumption given in Section 2.4. Finally, by taking advantage of the properties of the bilinear pairing, both conjunctive and disjunctive keywords search can be achieved. Specifically, for the conjunctive keywords search, the matched documents are returned if and only if all the keywords in the query are including in the index keyword set. For the disjunctive logic query, the matched documents are returned if and only if the intersection between the index and the query keyword set is not an empty set.According to the above ideas, the concrete construction is proposed in the following paragraphs. Because of making use of the prime order group, the proposed scheme is more efficient than the previous scheme adopting the IPE crypto-system on the time and space complexities. Experimental results showing the advantages of our scheme can be found in Section4.(i)
KeyGen(1γ): given a security parameter γ, the algorithm generates two cyclic groups G1,G2 of prime order q and a bilinear pairing e^:G1×G1→G2. It picks a random generator g of G1 and two hash functions H1:{0,1}∗→Zq∗ and H2:G2→{0,1}log2⁡q. Choosing 2n+3 random numbers α0,α1,…,αn,β0,β1,…,βn,θ∈Zq∗, it computes {X0=gα0,X1=gα1,…,Xn=gαn,Y0=gβ0,Y1=gβ1,…,Yn=gβn,Z=gθ,μ=e^(g,g)}. After this, it outputs the public key pk={X0,X1,…,Xn,Y0,Y1,…,Yn,Z,μ,g,H1,H2,e^} and the secret key sk={α0,α1,…,αn,β0,β1,…,βn,θ}, where pk is also open to the public.(ii)
IndexBuild(pk,W): the algorithm generates n2+2n random numbers r1,r2,…,rn and uij∈Zq∗, where i∈[1,n],j∈[0,n]. Given a keyword set W={w1,w2,…,wn} and the public key pk, for each word wi∈W, it computes Aij=Xjri×griH1(wi)j+uij,Bij=Yjuij,Ci=Zri=gθri and Di=H2(μri), where i∈[1,n] and j∈[0,n]. The index of the keyword set W is(6)IW=A10A11…A1nB10B11…B1nC1D1A20A21…A2nB20B21…B2nC2D2⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮An0An1…AnnBn0Bn1…BnnCnDnNote that the secure index can be seen as an encrypted version of matrix (3).(iii)
Trapdoor(sk,{Q,sym}): when the algorithm receives a keyword query Q={q1,q2,…,qm}, where m≤n, it will construct a vector a→={am,am-1,…,a0} by utilizing (5). Given a vector a→ and sk, t1j=gaj/∑j=0mαjaj+∑j=0majuθ and t2j=t1j1/βj can be computed, where u is a random number in Zq and j∈[0,m]. Let t3=u and sym∈{∨,∧}; the trapdoor for the keyword query Q is TQ=(t10,t11,…,t1m,t20,t21,…,t2m,t3,sym).(iv)
Test(pk,TQ,IW): when the algorithm receives a trapdoor TQ and a secure index IW, it works as follows:
(1)
If the symbol inTQ is ∨,
(a)
The algorithm chooses a counteri and sets i=1.(b)
Ifi>n, then it goes to step (c); otherwise it checks whether H2(testi1/testi2)=Di, where testi1=∏j=0me^(t1j,AijCit3),testi2=∏j=0me^(t2j,Bij). If so, the algorithm outputs 1 and ends. Otherwise, it sets i=i+1 and goes to step (b).(c)
The algorithm outputs0 and ends.(2)
If the symbol inTQ is ∧,
(a)
The algorithm chooses two countersi and j and sets i=1 and j=1.(b)
Ifi>n, then it goes to step (c); otherwise it tests whether H2(testi1/testi2)=Di, where testi1=∏j=0me^(t1j,AijCit3),testi2=∏j=0me^(t2j,Bij). If so, then the algorithm sets j=j+1. Otherwise, it does nothing. After that, it sets i=i+1 and goes to step (b).(c)
Ifj=m, the algorithm outputs 1 and ends. Otherwise, it outputs 0 and ends.Correctness.The key idea of disjunctive keywords search is to determine whether there exists an i∈[1,n] such that wi∈Q. For the conjunctive keywords search, we need to check whether there are m keywords wϕ(1),wϕ(2),…,wϕ(m) such that wϕ(j)∈Q, where ϕ(j)∈[1,n] and j∈[1,m]. According to these ideas, we know that the essence of test algorithm is to verify whether wi∈Q. In the proposed scheme, it is can be verified that testi1/testi2=e^(g,g)ri+ri∑j=0majH1(wi)j/∑j=0mαjaj+∑j=0majuθ. If wi∈Q, there is ∑j=0majH1(wi)j=0. Thus, it must be testi1/testi2=e^(g,g)ri and H2(testi1/testi2)=Di. Based on this, we argue that our scheme is correct.


## 3.3. Security Analysis

Theorem 4.
The proposed PECDK scheme is secure according to security definition in the random model if Decision(qT+1)-BDHI is hard.Proof.
Suppose that an algorithmA has advantage ε in breaking the PECDK under the security definition. Suppose A makes at most qT trapdoor queries, we can build an algorithm C which solves the decision (qT+1)-BDHI assumption with a probability at least ε′=ε/e(nqT+1), where e is the base of the natural logarithm, and n is the number of keywords in an index. Let g be a generator of G1. Given g,gx,gx2,…,gxqT+1,R, if R=e^(g,g)1/x, the algorithm C outputs 1, 0 otherwise. The interaction between the algorithm C and the algorithm A is as follows: (i)
Setup: the algorithm C works as follows:
(1)
The algorithmC randomly chooses qT numbers ρ1,ρ2,…,ρqT∈Zq∗ and returns f(z)=∏i=1qT(z+ρi)=∑i=0qTcizi.(2)
C computes U=gf(x)=g∑i=0qTcixi,V=gxf(x)=g∑i=0qTcixi+1, and fi(z)=1/z+ρif(z)=∑i=0qT-1dizi, where i∈[1,qT]. Then, C gets U1/x+ρi=gfi(x)=g∑i=0qT-1dixi and stores the pairs ρi,gfix in a list namedS-list, where i∈[1,qT].(3)
C computes f(z)-c0/z=∑i=1qTcizi-1 and sets RU=e^(g∑i=1qTcixi-1,g∑i=0qTcixi+c0)×Rc02. If R=e^(g,g)1/x, RU=e^(g∑i=1qTcixi-1,g∑i=0qTcixi+c0)×Rc02=e^(gf(x)-c0/x,gf(x)+c0)×Rc02=e^(g,g)f2(x)-c02/x×e^(g,g)c02/x=e^(g,g)f2(x)/x=e^(U,U)1/x.(4)
C randomly chooses 2n+4 numbers s0,s1,…,sn,t0,t1,…,tn,η, λ∈Zq∗ and constructs Xi=Vsi×U-ηi,Yi=Uti for each i∈[0,n]. Let Z=Vλ, C gives A the public key pk={U,X0,X1,…,Xn,Y0,Y1,…,Yn,Z,μ=e^(U,U),g,H1,H2,e^}. The corresponding sk is s0x-η0,s1x-η1,…,snx-ηn,t0,t1,…,tn,λx, where the values s0x-η0,s1x-η1,…,snx-ηn,λx are unknown to C.(ii)
H1,H2-queries: the random oracles H1 or H2 can be queried by A at any time. To answer H1-queries, C keeps a list of tuples (wj,hj,σj) called H1-list which is empty initially. When A queries the random oracle H1 at a point wi∈0,1∗, algorithm C answers as follows:H1-queries:
(1)
If the querywi is already in a tuple (wi,hi,σi) on H1-list, then C responds with H1(wi)=hi, where hi∈Zq∗.(2)
Otherwise,C generates a random coin σi∈[0,nqT] so that Pr[σi=0]=1/nqT+1.(3)
Ifσi=0, C sets hi=η. Otherwise, C picks a random ai∈Zq∗ and sets hi=ai.(4)
C adds the tuple (wi,hi,σi) to H1-list and answers A with H1(wi)=hi.H2-queries are similar to H1-queries. To answer H2 queries from A, C holds a list of tuples (φj,ψj) called H2-list which is initially empty. When A queries the random oracle H2 at a point φi∈G2, algorithm C responds as follows:H2-queries:
(1)
If the queryφi already appears on H2-list in a tuple (φi,ψi), then C responds with H2(φi)=ψi, where ψi∈0,1log2⁡q.(2)
Otherwise,C picks a random bi∈0,1log2⁡q and sets ψi=bi.(3)
C adds the tuple (φi,ψi) to H2-list and responds A with H2(φi)=ψi.(iii)
Trapdoor queries: when A queries a trapdoor of the keyword set Qi=qi1,qi2,…,qim and sym, the algorithm C answers as follows:
(1)
C runs H1-queries algorithm to obtain hij, where hij=H1(qij) for each j∈[1,m]. Let (wij,hij,σij) be the corresponding tuples on H1-list, for each j∈[1,m]; if σij=0, then C reports failure and terminates.(2)
Otherwise,C constructs a trapdoor for query Qi,sym. C first computes f′x′=∏i=1m(x′+hij)=am′x′m+am-1′x′m-1+…+a1′x′+a0′. Then, for each j∈[0,m], C can compute lij=-∑j=0maj′ηj/aj′ρi and νi=-∑j=0maj′ηj+ρi∑j=0maj′sj/ρiλ∑j=0maj′ through an equality of 1/x′+ρi=aj′lij/∑j=0maj′(sjx′-ηj)+νiλ∑j=0maj′x′. Obviously, (U1/(x′+ρi)li0,U1/(x′+ρi)li1,…,U1/(x′+ρi)lim, U1/(x′+ρi)li0t0,U1/(x′+ρi)li1t1,…,U1/(x′+ρi)limtm,νi, sym) is the trapdoor for the keyword query Qi.(3)
C searches S-list to obtain the tuple ρi,gfix′. Then C sends (gfi(x′)/li0, gfi(x′)/li1, …, gfi(x′)/lim, gfi(x′)/li0t0, gfi(x′)/li1t1, …,gfi(x′)/limtm,νi,sym) to the algorithm A as the correct trapdoor for the query Qi(iv)
Challenge: algorithm A produces a keyword set W∗={w01,w02,…,w0n}, which is what A wants to challenge. Then, A sends the target keyword set W∗ to C. C chooses a random keyword set R′={w11,w12,…,w1n} and sets W0=W∗ and W1=R′. The only restriction is that the previous trapdoor queries cannot distinguish W0 and W1. If there is any previous trapdoor that can break the restriction, C regenerates the keyword set W1. Then C selects a random bit β∈0,1 and runs the above algorithm for responding to H1-queries to obtain the values hβ1,hβ2,…,hβn, where H1(wβi)=hβi,wβi∈Wβ,i∈[1,n]. Let (wβi,hβi,σβi) be the corresponding tuples on H1-list, if there is no σβi=0 for all i∈[1,n], then C terminates. Otherwise, C generates the challenge PECDK index Iβ of Wβ as follows:
(1)
Ifσβi=0, C computes Aβij=Urβisj+yβij, Bβij=Utjyβij, Cβi=Urβiλ, and Dβi=H2(RUrβi), where j∈[0,n]. Observe that if R=e^(g,g)1/x, then RU=e^(U,U)1/x. So, the above values are equivalent to Aβij=Xjrβi/x×Urβiηj/x+yβij, Bβij=Yjyβij, Cβi=Zrβi/x, and Dβi=H2(e^(U,U)rβi/x), where j∈[0,n]. It means that this is a valid PECDK encryption of keyword wβi when R=e^(g,g)1/x.(2)
Otherwise,C computes Aβij=Vrβisj×Urβihβij+yβij-rβiηj, Bβij=Utjyβij, Cβi=Vrβiλ, Dβi=H2(e^(U,U)rβi), where j∈[0,n].(3)
C sends (7)Iβ=Aβ10Aβ11…Aβ1nBβ10Bβ11…Bβ1nCβ1Dβ1Aβ20Aβ21…Aβ2nBβ20Bβ21…Bβ2nCβ2Dβ2⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮Aβn0Aβn1…AβnnBβn0Bβn1…BβnnCβnDβnand two keyword sets W0 and W1 to A.(v)
More queries: A continues to inquire trapdoor queries. The restriction is similar to thechallenge phase.(vi)
Response: A outputs a guess β′∈{0,1}. C will output 1 if β′=β. Otherwise, C will output 0.
Now, we show that the algorithmC can solve the decision (qT+1)-BDHI assumption with probability at least ε′=ε/e(nqT+1). First of all, we should analyze the probability that C does not abort intrapdoor queries phase andchallenge phase. We define two events:
ω 1: C does not abort due to any of A’s trapdoor queries.
ω 2: C does not abort inchallenge phase for generating Iβ.
Suppose thatqT is large enough. Therefore, the probability of the event ω1 is at least (1-1/nqT+1)nqT≥1/e. The probability of the event ω2 is 1/nqT+1.
IfR=e^(g,g)1/x, A’s view is identical to its view in a real attack game. Since we assume that A can break the PECDK scheme with an advantage ε, it must satisfy Prβ′=β-1/2≥ε. If R is a random number, where R∈G2, then |Pr[β′=β]|=1/2 since A made a random guess.
Therefore, letD={g,gx,gx2,…,gxqT+1}; we have that (8)PrBD,e^g,g1/x=1-PrBD,R=1≥εenqT+1Then we conclude the theorem.


## 4. Performance Analysis

In this section, we first give a detailed theoretical analysis for the previous scheme and then compare it with the proposed one. After that, we set up an experiment to show that our scheme has better performance than the previous one. For simplicity, we denote the proposed scheme and the previous one by PECDK-1 and PECDK-2, respectively.


### 4.1. Theoretical Analysis

In an IPE scheme, each ciphertext associated with an attribute vectorx→ can be decrypted by the secret keys corresponding to the predicate vector v→ if and only if v→·x→=0. The PECDK-2 is based on the approach of converting an IPE scheme into a PECDK scheme. In order to analyze the efficiency of the previous one, we will introduce the conversion method, which is described as follows.Suppose thatQ={q1,q2,…,qm} and W={w1,w2,…,wn} are two keyword sets. By utilizing an IPE scheme, (c1,c2,…,cn) is the index of W, where ci is a ciphertext of the vector {wim,wim-1,…,wi0} and i∈[1,n]. Suppose that f(x)=amxm+am-1xm-1+…+a1x+a0=(x-H1(q1))(x-H1(q2))…(x-H1(qm)); the trapdoor of Q is {ka,sym}, where ka is a secret key of the vector {am,am-1,…,a0}. Let the decryption algorithm be DEC(pk,CT,KEY), where pk is the public key, CT is the ciphertext, and KEY is the secret key. For each i∈[1,n], the test algorithm can be performed by implementing DEC(pk,ci,ka). According to different search function, there are two situations:(1)
Forsym is ∨, if there is at least one i∈[1,n] such that the decryption algorithm DEC(pk,ci,ka) outputs 1, the test algorithm outputs 1, otherwise, 0.(2)
Forsym is ∧, the test algorithm will verify whether there are mci that can be decrypted by the decryption algorithm DEC(pk,ci,ka). If so, the test algorithm outputs 1, otherwise, 0.PECDK-2 is based on the IPE presented in [17]. For this IPE scheme, the time cost of setup, encryption, key generation, and decryption are all linear with O(N2), O(N2), O(N2), and O(N), respectively, where N is the length of the predicate or attribute vector. Moreover, the space overhead of public key, master secret key (msk), ciphertext, and secret key is linear with O(N2), O(N2), O(N), and O(N), respectively. According to the conversion method mentioned above, we have the following results.(1)
Thepk and sk in the previous scheme are the same as the pk and msk in the IPE scheme. Thus, the time and space cost of pk and sk are both linear with o(n2).(2)
Since the index of the previous scheme containsn ciphertexts of IPE, the time and space cost of index are linear with O(n3) and O(n2), respectively. Because the algorithm of trapdoor generating is similar with that of the index building, the time and space cost of trapdoor is also linear with O(n3) and O(n2), respectively.(3)
The test algorithm needs to performn times decryption algorithm. Thus, the time cost of test is proportional to the square of n.For our scheme,pk contains 2n+3 elements in group G1 and one element in G2, and sk involves 2n+3 elements in Zp∗. Thus, we know that the time and space cost of KeyGen algorithm in our scheme are both linear with O(n). Because the IndexBuild algorithm generates 2n2+3n elements in group G1 and n elements in G2, the time and space cost of IndexBuild algorithm are both linear with O(n2). The time cost and space cost of Trapdoor algorithm are both O(m) since this algorithm creates 2m+2 elements in group G1. Whether sym=∧ or sym=∨, the test algorithm executes at most O(mn) pairing operations. Therefore, we can reckon that the time cost of test algorithm is less than O(mn).According to the above analysis, we will give two tables to demonstrate the comparison. LetTe be the time cost for a pairing operation [15] on G1, and TG1 and TG2 be the time cost for the exponential operation on G1 and G2, where G1 and G2 are two groups of a prime order. For evaluating the time complexity, we only take these two operations into account since the time cost of these two operations is much more than the time cost of other operations like group add operation. The theoretical analysis of time complexity is shown in Table 1.Table 1
Comparison with the previous PECDK scheme in time complexity.
PECDK-1 PECDK-2 Key Generation O n 2 T G 1 + T e 2 n + 3 T G 1 + T e  Index Building 4 n 2 + 2 n T G 1 + n T G 2 3 n 2 + 4 n T G 1 + n T G 2  Trapdoor Generation 4 m + 2 T G 1 2 m + 2 T G 1 Testing 2 n 2 m + 1 T e 2 n m + 1 T eWe denote the size of an element ofZp, G1, and G2 by Zp, G1, and G2, respectively. The comparison result of space complexity is shown in Table 2.Table 2
Comparison with the previous PECDK scheme in space complexity.
PECDK-1 PECDK-2 PK size O n 2 G 1 + G 2 ( 2 n + 3 ) | G 1 | + | G 2 | SK size O n 2 G 1 ( 2 n + 3 ) | Z p | Trapdoor size 4 m + 2 G 1 ( 2 m + 2 ) | G 1 | + | Z p | Index size 4 n 2 + 2 n G 1 + G 2 ( 2 n 2 + 4 n ) | G 1 | + | G 2 |


### 4.2. Experimental Results

We implement our construction in JAVA with Java Pairing Based Cryptography (JPBC) library [39]. In our implementation, the bilinear map is instantiated as Type A pairing (base field size is 128 bits), which offers a level of security equivalent to 1024-bit DLOG [16]. Our experiment was run on Intel(R) Core(TM) i7-4570 CPU at 3.60GHz processor with 8GB memory size. Such an experiment is based on a group of artificial keyword sets with different number of keywords in each set (i.e., n=5;10;15;20;25), where each keyword set can be seen as an index of a document. In each keyword set, we denote each keyword as an unique integer in the range of [0,1000], where 1000 can be regarded as the number of different words in the artificial keyword sets. We encrypt each keyword set with PECDK-1 and PECDK-2 schemes, and the encrypted indices were stored on our machine and then execute random queries over these encrypted indices (the number of documents and queries is denoted by D and Qt, respectively). In addition, for simplicity, we denote the conjunctive and disjunctive keyword search by CKS (conjunctive keywords search) and DKS (disjunctive keywords search), respectively.


#### 4.2.1. Time Overhead

Figure2 shows that the impact of n on the time consumption. The statements of Figure 2 are described as follows.(1)
Figure2(a) shows that the execution time of key generation in PECDK-2 is linear with O(n2), while that in PECDK-1 is linear with n. The time cost of the key generation algorithm in PECDK-2 is nearly 100 times than that in PECDK-1 since PECDK-2 needs to generate a pair of orthogonal matrices and more exponential operations on G1.(2)
In Figure2(b), we can find that the time cost of creating index in PECDK-2 is much more than that in PECDK-1, though the time complexities of index building in PECDK-1 and PECDK-2 are both linear with O(n2). The reason for this situation is that the DPVS structure used in PECDK-2 is based on a pair of orthogonal matrices, which will bring more exponential operations on G1 and some additional matrix operations.(3)
The time consumption of testing in PECDK-1 and PECDK-2 is illustrated in Figure2(c). In Figure 2(c), we can find that time cost of CKS and DKS in PECDK-1 is much less than that in PECDK-2. In addition, whether PECDK-1 or PECDK-2, the time cost in DKS is slightly less than that in CKS since DKS may test fewer keywords than CKS.(4)
The time complexity of trapdoor generation in PECDK-1 is independent withn, while that in PECDK-2 is linear with O(n). The trapdoor generation algorithm in PECDK-1 still needs much less time cost than that in PECDK-2 with the same reason described in (2).Figure 2
Impact ofn on the time cost of key generation (a), index building (b), testing (c), and trapdoor generation (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Figure3 shows the impact of m on the time consumption. Because the key generation and index algorithms are not related to the parameter m, we only focus on the trapdoor generation and test algorithms. The comparison is stated as follows.(1)
The time costs of trapdoor generation in PECDK-1 and PECDK-2 are both linear withO(m), which is shown in Figure 3(a). However, the time cost of creating trapdoor in PECDK-2 is nearly 10 times than that in PECDK-1. The reason for this is that PECDK-2 needs more exponential operations on G1.(2)
Figure3(b) shows that the time cost of testing in PECDK-1 is linear with O(m), while that in PECDK-2 is not related with m. The reason is that the predicate vector and attribute vector must have the same dimension in an IPE scheme. So, we must convert the query keyword set into a predicate vector having the same length as the attribute vector generated from the index keyword set. According to this, the time cost of testing in PECDK-2 is independent to m actually. In addition, the time cost in DKS is also slightly less than that in CKS since DKS needs less test operations.Figure 3
Impact ofm on the time cost of trapdoor generation (a) and testing (b) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, n=25, Qt=10, m={5;10;15;20;25}).
(a) (b)


#### 4.2.2. Storage Overhead

The storage cost ofpk and sk, indices, and trapdoors are illustrated in Figure 4. The comparison results are listed as follows.(1)
Figures4(a) and 4(b) show that the storage cost of pk and sk in PECDK-2 increases with O(n2), while that in PECDK-1 is linear with O(n). Moreover, the storage cost in PECDK-2 is more than 100 times than that in PECDK-1. The reason is that the PECDK-2 needs to store two matrices.(2)
In Figure4(c), we know that the storage costs of indices in PECDK-1 and PECDK-2 are both linear with O(n2). However, the storage cost in PECDK-2 is also nearly two times than that in PECDK-1 since PECDK-2 needs to store more G1 elements than PECDK-1.(3)
In Figure4(d), the storage cost of trapdoors in PECDK-1 is independent to n, while that in PECDK-2 is linear with O(n). The storage cost in PECDK-2 is still more than that in PECDK-1.Figure 4
Impact ofn on the storage cost of pk (a), sk (b), index (c), and trapdoor (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Because the size ofpk, sk, and indices are not related to the parameter m, we only analyze the impact of parameter m on the storage cost of trapdoor. According to Table 3, we find that the size of trapdoor in PECDK-2 is independent with m since the query keywords must be converted into a predicate vector owing the same length to the attribute vector generated from the index keywords. The trapdoor size in PECDK-1 is linear with m and less than that in PECDK-2.Table 3
Impact ofm on storage consumption of trapdoor generation (n=25, D=100, Qt=10).
Size ofm 5 10 15 20 25 PECDK-1(kb) 6 10 14 19 23 PECDK-2(kb) 46 46 46 46 46According to the experimental results described above, we can find that these results are consistent with our theoretical analysis.


#### 4.2.3. More Comments

Generally speaking, the number of keywords in a document (n) is usually only 3~5 (e.g., the research paper), and the number of keywords in a query (m) is often less than 10 [40]. According to above results, we can reckon that both n and m are less than 10 in the actual process of retrieval. According to the experiment result with n=10 and m=5, for the PECDK-1, the generation time of a single index and a single trapdoor is nearly 100 ms and 20 ms, respectively, and the test time of a single document is 15 ms. Compared with the PECDK-2, it is more practical. Moreover, the time and storage cost of trapdoor in PECDK-1 scheme is very low, which means that the proposed scheme is fit for the mobile setting where the client has limited computation and storage resources.Many applications require that the client cannot only add a group of documents to the server but also remove a set of documents from the server. Considering this situation, we need that the proposed scheme supports dynamic update. It means that users can update the encrypted indices and files securely. Many previous works can achieve this goal [24, 25]. In our scheme, we adopt the forward index structure in which each file has its index. Thus, it can support dynamic update naturally. For example, when a client wants to add a document, he/she will generate an encrypted document and its corresponding secure index and send them to the server. If a client wants to delete a document, he/she will send a request to the server. The server will remove the related document and the associated index according to the request.In addition, because each document has its own encrypted index, we can easily accelerate the search process by utilizing the technique of parallel computation [6]. Thus, we argue that our scheme is more practical in the cloud platform, which has strong computing power.


## 4.1. Theoretical Analysis

In an IPE scheme, each ciphertext associated with an attribute vectorx→ can be decrypted by the secret keys corresponding to the predicate vector v→ if and only if v→·x→=0. The PECDK-2 is based on the approach of converting an IPE scheme into a PECDK scheme. In order to analyze the efficiency of the previous one, we will introduce the conversion method, which is described as follows.Suppose thatQ={q1,q2,…,qm} and W={w1,w2,…,wn} are two keyword sets. By utilizing an IPE scheme, (c1,c2,…,cn) is the index of W, where ci is a ciphertext of the vector {wim,wim-1,…,wi0} and i∈[1,n]. Suppose that f(x)=amxm+am-1xm-1+…+a1x+a0=(x-H1(q1))(x-H1(q2))…(x-H1(qm)); the trapdoor of Q is {ka,sym}, where ka is a secret key of the vector {am,am-1,…,a0}. Let the decryption algorithm be DEC(pk,CT,KEY), where pk is the public key, CT is the ciphertext, and KEY is the secret key. For each i∈[1,n], the test algorithm can be performed by implementing DEC(pk,ci,ka). According to different search function, there are two situations:(1)
Forsym is ∨, if there is at least one i∈[1,n] such that the decryption algorithm DEC(pk,ci,ka) outputs 1, the test algorithm outputs 1, otherwise, 0.(2)
Forsym is ∧, the test algorithm will verify whether there are mci that can be decrypted by the decryption algorithm DEC(pk,ci,ka). If so, the test algorithm outputs 1, otherwise, 0.PECDK-2 is based on the IPE presented in [17]. For this IPE scheme, the time cost of setup, encryption, key generation, and decryption are all linear with O(N2), O(N2), O(N2), and O(N), respectively, where N is the length of the predicate or attribute vector. Moreover, the space overhead of public key, master secret key (msk), ciphertext, and secret key is linear with O(N2), O(N2), O(N), and O(N), respectively. According to the conversion method mentioned above, we have the following results.(1)
Thepk and sk in the previous scheme are the same as the pk and msk in the IPE scheme. Thus, the time and space cost of pk and sk are both linear with o(n2).(2)
Since the index of the previous scheme containsn ciphertexts of IPE, the time and space cost of index are linear with O(n3) and O(n2), respectively. Because the algorithm of trapdoor generating is similar with that of the index building, the time and space cost of trapdoor is also linear with O(n3) and O(n2), respectively.(3)
The test algorithm needs to performn times decryption algorithm. Thus, the time cost of test is proportional to the square of n.For our scheme,pk contains 2n+3 elements in group G1 and one element in G2, and sk involves 2n+3 elements in Zp∗. Thus, we know that the time and space cost of KeyGen algorithm in our scheme are both linear with O(n). Because the IndexBuild algorithm generates 2n2+3n elements in group G1 and n elements in G2, the time and space cost of IndexBuild algorithm are both linear with O(n2). The time cost and space cost of Trapdoor algorithm are both O(m) since this algorithm creates 2m+2 elements in group G1. Whether sym=∧ or sym=∨, the test algorithm executes at most O(mn) pairing operations. Therefore, we can reckon that the time cost of test algorithm is less than O(mn).According to the above analysis, we will give two tables to demonstrate the comparison. LetTe be the time cost for a pairing operation [15] on G1, and TG1 and TG2 be the time cost for the exponential operation on G1 and G2, where G1 and G2 are two groups of a prime order. For evaluating the time complexity, we only take these two operations into account since the time cost of these two operations is much more than the time cost of other operations like group add operation. The theoretical analysis of time complexity is shown in Table 1.Table 1
Comparison with the previous PECDK scheme in time complexity.
PECDK-1 PECDK-2 Key Generation O n 2 T G 1 + T e 2 n + 3 T G 1 + T e  Index Building 4 n 2 + 2 n T G 1 + n T G 2 3 n 2 + 4 n T G 1 + n T G 2  Trapdoor Generation 4 m + 2 T G 1 2 m + 2 T G 1 Testing 2 n 2 m + 1 T e 2 n m + 1 T eWe denote the size of an element ofZp, G1, and G2 by Zp, G1, and G2, respectively. The comparison result of space complexity is shown in Table 2.Table 2
Comparison with the previous PECDK scheme in space complexity.
PECDK-1 PECDK-2 PK size O n 2 G 1 + G 2 ( 2 n + 3 ) | G 1 | + | G 2 | SK size O n 2 G 1 ( 2 n + 3 ) | Z p | Trapdoor size 4 m + 2 G 1 ( 2 m + 2 ) | G 1 | + | Z p | Index size 4 n 2 + 2 n G 1 + G 2 ( 2 n 2 + 4 n ) | G 1 | + | G 2 |


## 4.2. Experimental Results

We implement our construction in JAVA with Java Pairing Based Cryptography (JPBC) library [39]. In our implementation, the bilinear map is instantiated as Type A pairing (base field size is 128 bits), which offers a level of security equivalent to 1024-bit DLOG [16]. Our experiment was run on Intel(R) Core(TM) i7-4570 CPU at 3.60GHz processor with 8GB memory size. Such an experiment is based on a group of artificial keyword sets with different number of keywords in each set (i.e., n=5;10;15;20;25), where each keyword set can be seen as an index of a document. In each keyword set, we denote each keyword as an unique integer in the range of [0,1000], where 1000 can be regarded as the number of different words in the artificial keyword sets. We encrypt each keyword set with PECDK-1 and PECDK-2 schemes, and the encrypted indices were stored on our machine and then execute random queries over these encrypted indices (the number of documents and queries is denoted by D and Qt, respectively). In addition, for simplicity, we denote the conjunctive and disjunctive keyword search by CKS (conjunctive keywords search) and DKS (disjunctive keywords search), respectively.


### 4.2.1. Time Overhead

Figure2 shows that the impact of n on the time consumption. The statements of Figure 2 are described as follows.(1)
Figure2(a) shows that the execution time of key generation in PECDK-2 is linear with O(n2), while that in PECDK-1 is linear with n. The time cost of the key generation algorithm in PECDK-2 is nearly 100 times than that in PECDK-1 since PECDK-2 needs to generate a pair of orthogonal matrices and more exponential operations on G1.(2)
In Figure2(b), we can find that the time cost of creating index in PECDK-2 is much more than that in PECDK-1, though the time complexities of index building in PECDK-1 and PECDK-2 are both linear with O(n2). The reason for this situation is that the DPVS structure used in PECDK-2 is based on a pair of orthogonal matrices, which will bring more exponential operations on G1 and some additional matrix operations.(3)
The time consumption of testing in PECDK-1 and PECDK-2 is illustrated in Figure2(c). In Figure 2(c), we can find that time cost of CKS and DKS in PECDK-1 is much less than that in PECDK-2. In addition, whether PECDK-1 or PECDK-2, the time cost in DKS is slightly less than that in CKS since DKS may test fewer keywords than CKS.(4)
The time complexity of trapdoor generation in PECDK-1 is independent withn, while that in PECDK-2 is linear with O(n). The trapdoor generation algorithm in PECDK-1 still needs much less time cost than that in PECDK-2 with the same reason described in (2).Figure 2
Impact ofn on the time cost of key generation (a), index building (b), testing (c), and trapdoor generation (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Figure3 shows the impact of m on the time consumption. Because the key generation and index algorithms are not related to the parameter m, we only focus on the trapdoor generation and test algorithms. The comparison is stated as follows.(1)
The time costs of trapdoor generation in PECDK-1 and PECDK-2 are both linear withO(m), which is shown in Figure 3(a). However, the time cost of creating trapdoor in PECDK-2 is nearly 10 times than that in PECDK-1. The reason for this is that PECDK-2 needs more exponential operations on G1.(2)
Figure3(b) shows that the time cost of testing in PECDK-1 is linear with O(m), while that in PECDK-2 is not related with m. The reason is that the predicate vector and attribute vector must have the same dimension in an IPE scheme. So, we must convert the query keyword set into a predicate vector having the same length as the attribute vector generated from the index keyword set. According to this, the time cost of testing in PECDK-2 is independent to m actually. In addition, the time cost in DKS is also slightly less than that in CKS since DKS needs less test operations.Figure 3
Impact ofm on the time cost of trapdoor generation (a) and testing (b) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, n=25, Qt=10, m={5;10;15;20;25}).
(a) (b)


### 4.2.2. Storage Overhead

The storage cost ofpk and sk, indices, and trapdoors are illustrated in Figure 4. The comparison results are listed as follows.(1)
Figures4(a) and 4(b) show that the storage cost of pk and sk in PECDK-2 increases with O(n2), while that in PECDK-1 is linear with O(n). Moreover, the storage cost in PECDK-2 is more than 100 times than that in PECDK-1. The reason is that the PECDK-2 needs to store two matrices.(2)
In Figure4(c), we know that the storage costs of indices in PECDK-1 and PECDK-2 are both linear with O(n2). However, the storage cost in PECDK-2 is also nearly two times than that in PECDK-1 since PECDK-2 needs to store more G1 elements than PECDK-1.(3)
In Figure4(d), the storage cost of trapdoors in PECDK-1 is independent to n, while that in PECDK-2 is linear with O(n). The storage cost in PECDK-2 is still more than that in PECDK-1.Figure 4
Impact ofn on the storage cost of pk (a), sk (b), index (c), and trapdoor (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Because the size ofpk, sk, and indices are not related to the parameter m, we only analyze the impact of parameter m on the storage cost of trapdoor. According to Table 3, we find that the size of trapdoor in PECDK-2 is independent with m since the query keywords must be converted into a predicate vector owing the same length to the attribute vector generated from the index keywords. The trapdoor size in PECDK-1 is linear with m and less than that in PECDK-2.Table 3
Impact ofm on storage consumption of trapdoor generation (n=25, D=100, Qt=10).
Size ofm 5 10 15 20 25 PECDK-1(kb) 6 10 14 19 23 PECDK-2(kb) 46 46 46 46 46According to the experimental results described above, we can find that these results are consistent with our theoretical analysis.


### 4.2.3. More Comments

Generally speaking, the number of keywords in a document (n) is usually only 3~5 (e.g., the research paper), and the number of keywords in a query (m) is often less than 10 [40]. According to above results, we can reckon that both n and m are less than 10 in the actual process of retrieval. According to the experiment result with n=10 and m=5, for the PECDK-1, the generation time of a single index and a single trapdoor is nearly 100 ms and 20 ms, respectively, and the test time of a single document is 15 ms. Compared with the PECDK-2, it is more practical. Moreover, the time and storage cost of trapdoor in PECDK-1 scheme is very low, which means that the proposed scheme is fit for the mobile setting where the client has limited computation and storage resources.Many applications require that the client cannot only add a group of documents to the server but also remove a set of documents from the server. Considering this situation, we need that the proposed scheme supports dynamic update. It means that users can update the encrypted indices and files securely. Many previous works can achieve this goal [24, 25]. In our scheme, we adopt the forward index structure in which each file has its index. Thus, it can support dynamic update naturally. For example, when a client wants to add a document, he/she will generate an encrypted document and its corresponding secure index and send them to the server. If a client wants to delete a document, he/she will send a request to the server. The server will remove the related document and the associated index according to the request.In addition, because each document has its own encrypted index, we can easily accelerate the search process by utilizing the technique of parallel computation [6]. Thus, we argue that our scheme is more practical in the cloud platform, which has strong computing power.


## 4.2.1. Time Overhead

Figure2 shows that the impact of n on the time consumption. The statements of Figure 2 are described as follows.(1)
Figure2(a) shows that the execution time of key generation in PECDK-2 is linear with O(n2), while that in PECDK-1 is linear with n. The time cost of the key generation algorithm in PECDK-2 is nearly 100 times than that in PECDK-1 since PECDK-2 needs to generate a pair of orthogonal matrices and more exponential operations on G1.(2)
In Figure2(b), we can find that the time cost of creating index in PECDK-2 is much more than that in PECDK-1, though the time complexities of index building in PECDK-1 and PECDK-2 are both linear with O(n2). The reason for this situation is that the DPVS structure used in PECDK-2 is based on a pair of orthogonal matrices, which will bring more exponential operations on G1 and some additional matrix operations.(3)
The time consumption of testing in PECDK-1 and PECDK-2 is illustrated in Figure2(c). In Figure 2(c), we can find that time cost of CKS and DKS in PECDK-1 is much less than that in PECDK-2. In addition, whether PECDK-1 or PECDK-2, the time cost in DKS is slightly less than that in CKS since DKS may test fewer keywords than CKS.(4)
The time complexity of trapdoor generation in PECDK-1 is independent withn, while that in PECDK-2 is linear with O(n). The trapdoor generation algorithm in PECDK-1 still needs much less time cost than that in PECDK-2 with the same reason described in (2).Figure 2
Impact ofn on the time cost of key generation (a), index building (b), testing (c), and trapdoor generation (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Figure3 shows the impact of m on the time consumption. Because the key generation and index algorithms are not related to the parameter m, we only focus on the trapdoor generation and test algorithms. The comparison is stated as follows.(1)
The time costs of trapdoor generation in PECDK-1 and PECDK-2 are both linear withO(m), which is shown in Figure 3(a). However, the time cost of creating trapdoor in PECDK-2 is nearly 10 times than that in PECDK-1. The reason for this is that PECDK-2 needs more exponential operations on G1.(2)
Figure3(b) shows that the time cost of testing in PECDK-1 is linear with O(m), while that in PECDK-2 is not related with m. The reason is that the predicate vector and attribute vector must have the same dimension in an IPE scheme. So, we must convert the query keyword set into a predicate vector having the same length as the attribute vector generated from the index keyword set. According to this, the time cost of testing in PECDK-2 is independent to m actually. In addition, the time cost in DKS is also slightly less than that in CKS since DKS needs less test operations.Figure 3
Impact ofm on the time cost of trapdoor generation (a) and testing (b) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, n=25, Qt=10, m={5;10;15;20;25}).
(a) (b)


## 4.2.2. Storage Overhead

The storage cost ofpk and sk, indices, and trapdoors are illustrated in Figure 4. The comparison results are listed as follows.(1)
Figures4(a) and 4(b) show that the storage cost of pk and sk in PECDK-2 increases with O(n2), while that in PECDK-1 is linear with O(n). Moreover, the storage cost in PECDK-2 is more than 100 times than that in PECDK-1. The reason is that the PECDK-2 needs to store two matrices.(2)
In Figure4(c), we know that the storage costs of indices in PECDK-1 and PECDK-2 are both linear with O(n2). However, the storage cost in PECDK-2 is also nearly two times than that in PECDK-1 since PECDK-2 needs to store more G1 elements than PECDK-1.(3)
In Figure4(d), the storage cost of trapdoors in PECDK-1 is independent to n, while that in PECDK-2 is linear with O(n). The storage cost in PECDK-2 is still more than that in PECDK-1.Figure 4
Impact ofn on the storage cost of pk (a), sk (b), index (c), and trapdoor (d) (blue and red scale are for PECDK-1 and PECDK-2, respectively, and D=100, m=5, Qt=10, n={5;10;15;20;25}).
(a) (b) (c) (d)Because the size ofpk, sk, and indices are not related to the parameter m, we only analyze the impact of parameter m on the storage cost of trapdoor. According to Table 3, we find that the size of trapdoor in PECDK-2 is independent with m since the query keywords must be converted into a predicate vector owing the same length to the attribute vector generated from the index keywords. The trapdoor size in PECDK-1 is linear with m and less than that in PECDK-2.Table 3
Impact ofm on storage consumption of trapdoor generation (n=25, D=100, Qt=10).
Size ofm 5 10 15 20 25 PECDK-1(kb) 6 10 14 19 23 PECDK-2(kb) 46 46 46 46 46According to the experimental results described above, we can find that these results are consistent with our theoretical analysis.


## 4.2.3. More Comments

Generally speaking, the number of keywords in a document (n) is usually only 3~5 (e.g., the research paper), and the number of keywords in a query (m) is often less than 10 [40]. According to above results, we can reckon that both n and m are less than 10 in the actual process of retrieval. According to the experiment result with n=10 and m=5, for the PECDK-1, the generation time of a single index and a single trapdoor is nearly 100 ms and 20 ms, respectively, and the test time of a single document is 15 ms. Compared with the PECDK-2, it is more practical. Moreover, the time and storage cost of trapdoor in PECDK-1 scheme is very low, which means that the proposed scheme is fit for the mobile setting where the client has limited computation and storage resources.Many applications require that the client cannot only add a group of documents to the server but also remove a set of documents from the server. Considering this situation, we need that the proposed scheme supports dynamic update. It means that users can update the encrypted indices and files securely. Many previous works can achieve this goal [24, 25]. In our scheme, we adopt the forward index structure in which each file has its index. Thus, it can support dynamic update naturally. For example, when a client wants to add a document, he/she will generate an encrypted document and its corresponding secure index and send them to the server. If a client wants to delete a document, he/she will send a request to the server. The server will remove the related document and the associated index according to the request.In addition, because each document has its own encrypted index, we can easily accelerate the search process by utilizing the technique of parallel computation [6]. Thus, we argue that our scheme is more practical in the cloud platform, which has strong computing power.


## 5. Conclusion

In this paper, we propose an efficient PECDK scheme based on a prime order group, which has better performance than the previous PECDK scheme. Our scheme is proven to be secure under the security definition.To justify the efficiency of the proposed scheme, we present detailed theoretical analysis and experimental results. These results show that the proposed scheme is more practical than the most efficient PECDK scheme based on the IPE scheme. In the future, we will focus on building a SPE scheme supporting more advanced search function.



---

*Source: 5280806-2019-05-13.xml*