# Tree-Based Public Key Encryption with Conjunctive Keyword Search

Authors: Yu Zhang; Lei You; Yin Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Searchable public key encryption supporting conjunctive keyword search is an important technique in today’s cloud environment. Nowadays, previous schemes usually take advantage of forward index structure, which leads to a linear search complexity. In order to obtain better search efficiency, in this paper, we utilize a tree index structure instead of forward index to realize such schemes. To achieve the goal, we first give a set of keyword conversion methods that can convert the index and query keywords into a group of vectors and then present a novel algorithm for building index tree based on these vectors. Finally, by combining an efficient predicate encryption scheme to encrypt the index tree, a tree-based public key encryption with conjunctive keyword search scheme is proposed. The proposed scheme is proven to be secure against chosen plaintext attacks and achieves a sublinear search complexity. Moreover, both theoretical analysis and experimental result show that the proposed scheme is efficient and feasible for practical applications.


---

## Body

## 1. Introduction

With the rapid development of cloud computing, many enterprises and individuals are willing to store their data over the cloud server for the sake of its efficiency and convenience. Although data outsourcing has brought great convenience to resource-constrained users, it inevitably raises data privacy and security concerns since users’ data stored in the cloud server are generally in plaintext mode. If the cloud server is compromised by some malicious intruder, these data can be accessed by them with no obstacles. To overcome this problem, a straightforward approach is encrypting data before outsourcing them. Nevertheless, this trivial approach needs to download all encrypted data to the client and then perform a keyword search after decrypting these data. Because this method is inefficient, if the amount of data is relatively large, exploring a new technology which can retrieve encrypted data on the cloud server without decryption is of prime importance in practical application.Searchable encryption (SE) [1] is a promising method, which offers a capacity for searching over encrypted data securely. In terms of different cryptography primitives, SE can be classified into two types, that is, searchable symmetric encryption (SSE) and searchable public key encryption (SPE). SSE is fit for the scenario of one data owner and one data user, while SPE can be applied in the scenario of many data owners and one data user, e.g., Mail Routing Service (MRS) and Personal Healthcare Record (PHR). In practice, since user’s data and query can be expressed as a keyword set, many existing SPE schemes are keyword-based schemes.The first SPE scheme that supports a keyword search, called public key encryption with keyword search (PEKS), was proposed by Boneh et al. [2]. They first defined the framework and security definition of SPE and gave a concrete scheme supporting only a single keyword search. To support conjunctive keywords search, Park et al. gave two public key encryptions with conjunctive keyword search (PECK) schemes [3]. The first scheme requires too much bilinear pairing operations, while the second one requires many private keys that are linear with the number of keywords. However, their schemes need the keyword field as additional information to perform the keyword search. To create a PECK scheme without keyword field, a hidden vector encryption scheme was presented by Boneh and Waters [4]. To improve the search efficiency, Zhang et al. proposed a keyword field-free PECK scheme with less search overhead [5]. In the years that followed, many works aim to improve the efficiency of PECK [6, 7], which enhances the practicability of PECK. Nevertheless, the search complexities of the aforementioned schemes are all linear with the number of keywords in a corpus, which is not practical when the corpus is large.Motivation and Objective. To better clarify the motivation of our scheme, we give Table 1 to show some recent works that are relevant to our work. According to Table 1, we find whether most SPE schemes [5–12] own additional abilities or do not utilize forward index structure, which suffers from linear search complexity. In this case, these schemes are impractical in reality applications, as the volume of data increases. To improve the search efficiency, recently, a PECK scheme using a hidden structure was proposed, which can achieve a sublinear search efficiency [13]. However, the time consumption of index building is proportional to the square of the number of keywords in each document. For the efficiency concern, it is necessary to construct a PECK scheme with high efficiency in the aspects of encryption and search.Table 1
Comparison between previous searchable encryption schemes and ours.
Ref.Search functionIndex structureSettingAdditional special abilitiesOursConjunctive keyword searchTree-based indexPublic key—[5]Conjunctive keyword searchForward indexPublic key—[6]Conjunctive keyword searchForward indexPublic key—[7]Boolean keyword searchForward indexPublic key—[8]Conjunctive keyword searchForward indexPublic key—[9]Conjunctive keyword searchForward indexPublic keyVerification for query results[10]Conjunctive keyword searchForward indexPublic keyResistance for KGA[11]Single keyword searchForward indexPublic keyAccess control[12]Single keyword searchForward indexPublic keyCertificateless encryption[13]Conjunctive keyword searchHidden structurePublic key—[14]Rank searchTree-based indexSymmetric key—[15]Rank searchTree-based indexSymmetric key—[16]Rank searchTree-based indexSymmetric key—[17]Rank searchInverted indexSymmetric key—[18]Rank searchInverted indexSymmetric key—The additional special ability means that this scheme owns some extra security mechanism. KGA is the abbreviation of keyword guessing attack. Rank search is that the search result will be ranked before returning to the data users.In the field of information retrieval, index structures with sublinear search complexity, such as inverted and tree-based index structures, are very popular and have already been adopted in the domain of SSE [14–18]. Considering that the tree structure commonly owns a better search performance than the forward index structure, thus, this paper aims to construct a PECK scheme under a tree index structure to achieve a sublinear search efficiency without sacrificing encryption efficiency. For simplicity, we name this scheme as tree-based public encryption with conjunctive keyword search (T-PECK).Contributions. The contributions of our scheme are listed as follows:(1)
We design a set of keyword conversion methods, which are used to transform the keyword set in each document and a query into a group of vector representations. The semantic information embedded in these vector representations can be utilized to appraise the relationship between documents and queries.(2)
Based on the above conversion methods, a tree building algorithm is proposed to create a tree index for all documents. Correspondingly, a tree search algorithm is also given to realize conjunctive keyword search with a sublinear search complexity.(3)
Inspired by the definition of PECK proposed in [3], we give a detailed framework and security definition of T-PECK. Based on the framework, by taking advantage of an efficient predicate-only encryption supporting inner product scheme (PO-IPE) scheme introduced in [19] to encrypt the index tree, a concrete T-PECK scheme is proposed. Moreover, a rigorous proof is given to demonstrate the security of T-PECK according to the security definition.In addition, to show the feasibility of our scheme, we also give a detailed experiment to verify the efficiency of our scheme. The experiment results given in Section5 show that the search complexity of T-PECK is indeed sublinear with the number of the documents without sacrificing the encrypting efficiency, and T-PECK is more practical than recent PECK schemes [8, 13].Related work. Generally speaking, SE can be categorized as SSE and SPE, where SSE and SPE are based on public key and symmetric key encryption systems, respectively. Although SPE is less efficient in terms of encryption and search than SSE as the use of public key cryptography, it allows more extensive application scenarios and better security properties.The first SPE encryption solution supporting keyword search (PEKS), reckoned as a generalization of anonymous identity-based encryption (IBE) [20], was designed by Boneh et al. [2]. After this, Abdalla et al. gave definitions of computational and statistical consistency of PEKS and proposed a new PEKS scheme [21]. Considering that works in [2, 21] only realize a single keyword search, Park et al. first gave the first PECK scheme [3]. In their scheme, each keyword is affiliated with a keyword field. If two same keywords are associated with two different keyword field, they are reckoned as two different keywords. This property has limited it in applications of many scenarios. To achieve PECK without the keyword field, a hidden vector encryption (HVE) scheme was proposed by Boneh and Waters [4]. To support disjunctive keyword search, Katz et al. proposed a predicate encryption (PE) scheme supporting inner product [22], which is also called inner product encryption (IPE). In their scheme, the keyword sets of a document and a query can be converted to be an attribute and a predicate vector, respectively. By applying the PE scheme to encrypt these vectors, a PECK or a public key encryption with disjunctive keyword search (PEDK) can be obtained. In order to improve the query efficiency, some efficient PECK schemes [5, 6, 8] were proposed by reducing the bilinear pairing operations in the search process. To support conjunctive and disjunctive keyword search simultaneously, by adopting an efficient IPE scheme [23], Zhang et al. proposed a public key encryption with conjunctive and disjunctive keyword search (PECDK) scheme [24]. Then, they also presented a new PECDK scheme [25] which is more efficient than their previous scheme [24]. To support more expressive queries, Yang et al. devised a SPE scheme supporting various search functions, e.g., range search, conjunctive keyword search, and Boolean keyword search [7]. Although this scheme can support sophisticated query, the search efficiency of this scheme remains to be further improved. For efficiency concern, two SPE scheme [13, 26] supporting Boolean keyword search were proposed to improve the search efficiency. In addition, in recent years, some works are interested in other aspects of SPE, such as keyword guessing attack (KGA) [27–29], access control [30, 31], and fast search [32, 33]. These works profoundly improves the usability of SPE.In the domain of SSE, the tree and inverted index structures are usually adopted in SSE schemes to achieve better search efficiency. The SSE schemes using inverted index were given in [17, 18]. By taking advantage of r-tree, kd-tree, and balanced binary tree, SSE schemes with the tree index structure were released in [14–16]. To the best of our knowledge, there is no PECK scheme based on the tree index structure so far. Thus, in this paper, to improve the search efficiency substantially, we attempt to construct a PECK scheme based on the balanced binary tree.Organization. We organize this paper as follows. In Section 2, we present the framework of T-PECK and the security definition of T-PECK and introduce some backgrounds related to our scheme. The keyword conversion methods and the tree building algorithm are presented in Section 3. We construct T-PECK in Section 4, and a detailed security proof of T-PECK is also presented in this section. In Section 5, we give the theoretical and experimental analysis of T-PECK. Section 6 concludes our work.


## 2. Preliminary

In this section, we describe the application scenario and give the system model of the T-PECK scheme. Based on this system model, we present a formal framework and security definition of T-PECK. Besides, because PO-IPE scheme is adopted as the basic encryption module, we also introduce the bilinear pairing group and the definition of PO-IPE. To formulate our work mathematically, Table2 shows notations that are adopted in this paper.Table 2
Notation.
F=f1,f2,…,fdAll documents in a corpusC=c1,c2,…,cdEncrypted documents ofFDic=w1,w2,…,wNAll keywords inF (dictionary for F)TThe plaintext index tree forFITThe encrypted index tree forTWi=wi1,wi2,…,winThe keyword set offiQ=q1,q2,…,qmThe keyword set of queryQTQThe trapdoor ofQnThe number of keywords in each documentWimThe number of keywords in the queryQWi¯The vector representation forWiS1,S2,…,SlA group of document sets obtained by splittingDicqiA keyword inQ, i∈1,mwijA keyword inWi, i∈1,d and j∈1,n


### 2.1. The Proposed T-PECK Model

In T-PECK scheme, there are three roles: data owners (DOs), data user (DU), and cloud server (CS). DU first generates a pair of keys for which the public key (pk) is open to the public and the secret key (sk) can be only obtained by DU. When one DO wants to send a group of documents to DU, he/she will encrypt these documents and send the encrypted documents along with an encrypted index tree. Note that this encrypted index tree is generated by using a group of keyword set W1,W2,…,Wd derived from these documents and pk. When DU wants to retrieve documents containing a specific list of keywords, he/she makes use of sk and query keywords to construct a trapdoor and sends the trapdoor to CS. Once the trapdoor is received, CS tests the encrypted index against the trapdoor and returns the matched documents to DU. The system model is illustrated in Figure 1. As shown in Figure 1, DO builds the secure index and sends it to the CS. When CS receives the trapdoor generated by DU, it performs the search algorithm and returns the query results to DO. According to this model, the definition of the framework of T-PECK is given as follows.Figure 1
Architecture of the search over encrypted cloud data.Definition 1.
The T-PECK scheme consists of five probabilistic polynomial time (PPT) algorithms (KeyGen, CreateTree, IndexBuild, Trapdoor, and Search):(1)
KeyGen (γ): given a security parameter γ, this algorithm generates the public key pk and the secret key sk(2)
CreateTree (W): given a dataset W=W1,W2,…,Wd in which Wi is the corresponding keyword set of document fi and i∈1,d, the algorithm outputs a plaintext tree T(3)
IndexBuild (pk,T): this algorithm builds a searchable encrypted index tree IT by utilizing the public key pk and a plaintext tree T(4)
Trapdoor (sk,Q): given the secret key sk and a conjunctive keyword query Q=q1,q2,…,qm, where qi is a query keyword and i∈1,m, this algorithm produces a trapdoor TQ(5)
Search (pk, TQ, IT): this algorithm takes pk, TQ, and IT as input and returns a group of documents by searching the index tree
Correctness property. For a conjunctive keyword query Q and a group of keyword sets W=W1,W2,…,Wd, for correctly generating KeyGenγ⟶pk,sk, CreateTreeW⟶T, IndexBuildpk,T⟶IT, and Trapdoorsk,Q⟶TQ, if Q⊆Wi, the algorithm Searchpk,TQ,IT outputs the document fi. Otherwise, it outputs fi with negligible probability.
Actually, in the T-PECK scheme, the index treeT and the document set F are encrypted by IndexBuildpk,T and Enckey,F, respectively, where Enc⋅ is a secure symmetric encryption scheme, e.g., AES-CBC. Moreover, in practice, the Search algorithm only returns the identifiers of matched documents, and then, DU will make use of these identifiers to look up the corresponding ciphertexts. Thus, like other related work, our work only concentrates on searchable encryption part.


### 2.2. Security Definition of T-PECK

Before presenting the formal security definition of T-PECK, based on four kinds of private leaks, we first define a leakage function under four patterns introduced in [34], which is inevitably exposed to the cloud server.Size Pattern. The size of encrypted documents and queries can be accessed by the cloud server as they are stored in the cloud. This leakage is denoted as the leak of size pattern.Access Pattern. The cloud server can obtain the relationship between a specific query and identifiers of matched documents, which is called the leakage of access pattern.Search Pattern. Given a document set F=f1,f2,…,fd and a query set Q=Q1,Q2,…,Qt, a d×t matrix can be constructed by the cloud server. In this matrix, if fi matches the query Qj, the element in the ith row and jth column is set to be 1. The search pattern is the information of the matrix.Path Pattern. For a specific query, when the search algorithm traverses in the tree, the path will be revealed to the cloud server. This path information can be regarded as the leakage of the path pattern.These leakage patterns are default in most searchable encryption schemes [5–8]. Actually, the technique called oblivious RAMs can be adopted to protect the access pattern and the search pattern, but it suffers from the problem of low efficiency in the actual applications. Thus, we do not consider these leakages in this paper.Similar to the definition presented in [3], for two challenge index trees T0 and T1 based on two datasets W0 and W1, we propose a security definition which demands that the encrypted index tree of T0 and that of T1 are computationally indistinguishable for any probabilistic polynomial time adversary A. Given a leakage function LT,Q in which T is an index tree of a dataset D and Q is a keyword query, the detailed security definition is given as follows.Definition 2.
For any probabilistic polynomial time (PPT) adversaryA, using a security parameter γ, A T-PECK scheme can be seen as semantical security against chosen plaintext attacks if A’s advantage is negligible under the following game.(1)
Setup: the challengerℂ utilizes KeyGen (γ) to create pk and sk and sends pk to A.(2)
Phase 1: for any queryQ that A wants to perform, A adaptively ask ℂ for the trapdoor TQ of Q.(3)
Challenge: letQ1,Q2,…,Qt be t keyword queries that are performed in Phase 1. Two challenge index trees T0 and T1 are chosen and sent to ℂ under the restriction that LT0,Qi=LT1,Qi for each i∈1,t. After this, ℂ selects a random bit β∈0,1, builds an encrypted index tree ITβ by using IndexBuildpk,Tβ, and sends ITβ,T0,T1 to A.(4)
Phase 2: for any keyword queryQ, A can continue to request the trapdoor TQ under the restriction LT0,TQ=LT1,TQ.(5)
Response:A outputs β′∈0,1. If β′=β, A wins the game.
According the above game, the advantage ofA is defined as(1)AdvGameA=Prβ′=β−12.


### 2.3. The Concept of PO-IPE Scheme

#### 2.3.1. Framework of PO-IPE

The original definition of PO-IPE was presented in [19]. In this definition, a ciphertext is associated with an attribute vector x⟶, and a key is associated with a predicate vector v⟶ correspondingly. The significant property of PO-IPE is that a ciphertext of x⟶ can be decrypted by a key of v⟶ if and only if v⟶⋅x⟶=0. More explicitly, the framework of PO-IPE is introduced in the following definition.Definition 3.
∑ and F are represented as an arbitrary set of attributes and predicated on ∑, respectively. There are four PPT algorithms in a PO-IPE scheme with ∑ and F, i.e.,(1)
Setup: this algorithm inputs a security parameter γ and outputs pk and master secret key (msk)(2)
KeyGen: given msk and a predicate vector v⟶∈F as input, this algorithm outputs the secret key skv⟶ of v⟶(3)
Enc: this encryption algorithm uses pk to encrypt an attribute vector x⟶∈∑ and outputs the ciphertext C(4)
Dec. taking pk, skv⟶, and C as input, this decryption algorithm outputs 1 or 0 either
Consistency of PO-IPE. For correctly generating Setup1n⟶pk,msk, KeyGenmsk,v⟶⟶skv⟶, and Encpk,x⟶⟶C, for all v⟶∈F and x⟶∈Σ, the decryption algorithm Decpk,skv⟶,C outputs 1 if v⟶⋅x⟶=0, otherwise 0.
According to the definitions of T-PECK and PO-IPE, by converting the index and query keyword sets into an attribute vectorx⟶ and a predicate vector v⟶, respectively, we can take advantage of a PO-IPE scheme to create our scheme. The key to realizing the goal of conjunctive keyword search is constructing a keyword conversion method to change the query and index keyword sets into vectors.


#### 2.3.2. Security Definition of PO-IPE

The security of T-PECK depends on that of PO-IPE since PO-IPE is the basis of T-PECK. To present a detailed proof for the security of T-PECK, the security definition of PO-IPE given in [19] is described as follows.Definition 4.
Given a security parameterγ, for any PPT adversary A, if A’s advantage is negligible in the game described below, we say that a PO-IPE scheme is semantically secure against chosen plaintext attacks.(1)
Setup:ℂ creates pk and msk by utilizing Setup (γ) and sends pk to A.(2)
Phase 1:A can ask ℂ for t predicate vectors v⟶1,v⟶2,…,v⟶t adaptively and obtain corresponding keys skv⟶1, skv⟶2, …, skvt⟶.(3)
Challenge: two challenge attribute vectorsx⟶0,x⟶1 are selected randomly by A under the following constraints. For secret keys skv⟶1, skv⟶2, …, skv⟶t requested in Phase 1, one of the following constraints should be satisfied.v⟶j⋅x⟶0≠0 and v⟶j⋅x⟶1≠0.v⟶j⋅x⟶0=0 and v⟶j⋅x⟶1=0, where j∈1,t.ℂ randomly chooses a bit β and sends the ciphertext Cβ⟶Encpk,x⟶β to A.(4)
Phase 2:A can continue to request keys skv⟶t+1, skv⟶t+2, …, skv⟶q, for other predicate vectors, v⟶t+1, v⟶t+2, …, v⟶q. These keys must comply with the restriction given in the challenge phase.(5)
Response: a bitβ′ is given by A. If β′=β, A wins the game.
A’s advantage under the above game is described as(2)AdvGameA=Prβ′=β−12.


## 2.1. The Proposed T-PECK Model

In T-PECK scheme, there are three roles: data owners (DOs), data user (DU), and cloud server (CS). DU first generates a pair of keys for which the public key (pk) is open to the public and the secret key (sk) can be only obtained by DU. When one DO wants to send a group of documents to DU, he/she will encrypt these documents and send the encrypted documents along with an encrypted index tree. Note that this encrypted index tree is generated by using a group of keyword set W1,W2,…,Wd derived from these documents and pk. When DU wants to retrieve documents containing a specific list of keywords, he/she makes use of sk and query keywords to construct a trapdoor and sends the trapdoor to CS. Once the trapdoor is received, CS tests the encrypted index against the trapdoor and returns the matched documents to DU. The system model is illustrated in Figure 1. As shown in Figure 1, DO builds the secure index and sends it to the CS. When CS receives the trapdoor generated by DU, it performs the search algorithm and returns the query results to DO. According to this model, the definition of the framework of T-PECK is given as follows.Figure 1
Architecture of the search over encrypted cloud data.Definition 1.
The T-PECK scheme consists of five probabilistic polynomial time (PPT) algorithms (KeyGen, CreateTree, IndexBuild, Trapdoor, and Search):(1)
KeyGen (γ): given a security parameter γ, this algorithm generates the public key pk and the secret key sk(2)
CreateTree (W): given a dataset W=W1,W2,…,Wd in which Wi is the corresponding keyword set of document fi and i∈1,d, the algorithm outputs a plaintext tree T(3)
IndexBuild (pk,T): this algorithm builds a searchable encrypted index tree IT by utilizing the public key pk and a plaintext tree T(4)
Trapdoor (sk,Q): given the secret key sk and a conjunctive keyword query Q=q1,q2,…,qm, where qi is a query keyword and i∈1,m, this algorithm produces a trapdoor TQ(5)
Search (pk, TQ, IT): this algorithm takes pk, TQ, and IT as input and returns a group of documents by searching the index tree
Correctness property. For a conjunctive keyword query Q and a group of keyword sets W=W1,W2,…,Wd, for correctly generating KeyGenγ⟶pk,sk, CreateTreeW⟶T, IndexBuildpk,T⟶IT, and Trapdoorsk,Q⟶TQ, if Q⊆Wi, the algorithm Searchpk,TQ,IT outputs the document fi. Otherwise, it outputs fi with negligible probability.
Actually, in the T-PECK scheme, the index treeT and the document set F are encrypted by IndexBuildpk,T and Enckey,F, respectively, where Enc⋅ is a secure symmetric encryption scheme, e.g., AES-CBC. Moreover, in practice, the Search algorithm only returns the identifiers of matched documents, and then, DU will make use of these identifiers to look up the corresponding ciphertexts. Thus, like other related work, our work only concentrates on searchable encryption part.


## 2.2. Security Definition of T-PECK

Before presenting the formal security definition of T-PECK, based on four kinds of private leaks, we first define a leakage function under four patterns introduced in [34], which is inevitably exposed to the cloud server.Size Pattern. The size of encrypted documents and queries can be accessed by the cloud server as they are stored in the cloud. This leakage is denoted as the leak of size pattern.Access Pattern. The cloud server can obtain the relationship between a specific query and identifiers of matched documents, which is called the leakage of access pattern.Search Pattern. Given a document set F=f1,f2,…,fd and a query set Q=Q1,Q2,…,Qt, a d×t matrix can be constructed by the cloud server. In this matrix, if fi matches the query Qj, the element in the ith row and jth column is set to be 1. The search pattern is the information of the matrix.Path Pattern. For a specific query, when the search algorithm traverses in the tree, the path will be revealed to the cloud server. This path information can be regarded as the leakage of the path pattern.These leakage patterns are default in most searchable encryption schemes [5–8]. Actually, the technique called oblivious RAMs can be adopted to protect the access pattern and the search pattern, but it suffers from the problem of low efficiency in the actual applications. Thus, we do not consider these leakages in this paper.Similar to the definition presented in [3], for two challenge index trees T0 and T1 based on two datasets W0 and W1, we propose a security definition which demands that the encrypted index tree of T0 and that of T1 are computationally indistinguishable for any probabilistic polynomial time adversary A. Given a leakage function LT,Q in which T is an index tree of a dataset D and Q is a keyword query, the detailed security definition is given as follows.Definition 2.
For any probabilistic polynomial time (PPT) adversaryA, using a security parameter γ, A T-PECK scheme can be seen as semantical security against chosen plaintext attacks if A’s advantage is negligible under the following game.(1)
Setup: the challengerℂ utilizes KeyGen (γ) to create pk and sk and sends pk to A.(2)
Phase 1: for any queryQ that A wants to perform, A adaptively ask ℂ for the trapdoor TQ of Q.(3)
Challenge: letQ1,Q2,…,Qt be t keyword queries that are performed in Phase 1. Two challenge index trees T0 and T1 are chosen and sent to ℂ under the restriction that LT0,Qi=LT1,Qi for each i∈1,t. After this, ℂ selects a random bit β∈0,1, builds an encrypted index tree ITβ by using IndexBuildpk,Tβ, and sends ITβ,T0,T1 to A.(4)
Phase 2: for any keyword queryQ, A can continue to request the trapdoor TQ under the restriction LT0,TQ=LT1,TQ.(5)
Response:A outputs β′∈0,1. If β′=β, A wins the game.
According the above game, the advantage ofA is defined as(1)AdvGameA=Prβ′=β−12.


## 2.3. The Concept of PO-IPE Scheme

### 2.3.1. Framework of PO-IPE

The original definition of PO-IPE was presented in [19]. In this definition, a ciphertext is associated with an attribute vector x⟶, and a key is associated with a predicate vector v⟶ correspondingly. The significant property of PO-IPE is that a ciphertext of x⟶ can be decrypted by a key of v⟶ if and only if v⟶⋅x⟶=0. More explicitly, the framework of PO-IPE is introduced in the following definition.Definition 3.
∑ and F are represented as an arbitrary set of attributes and predicated on ∑, respectively. There are four PPT algorithms in a PO-IPE scheme with ∑ and F, i.e.,(1)
Setup: this algorithm inputs a security parameter γ and outputs pk and master secret key (msk)(2)
KeyGen: given msk and a predicate vector v⟶∈F as input, this algorithm outputs the secret key skv⟶ of v⟶(3)
Enc: this encryption algorithm uses pk to encrypt an attribute vector x⟶∈∑ and outputs the ciphertext C(4)
Dec. taking pk, skv⟶, and C as input, this decryption algorithm outputs 1 or 0 either
Consistency of PO-IPE. For correctly generating Setup1n⟶pk,msk, KeyGenmsk,v⟶⟶skv⟶, and Encpk,x⟶⟶C, for all v⟶∈F and x⟶∈Σ, the decryption algorithm Decpk,skv⟶,C outputs 1 if v⟶⋅x⟶=0, otherwise 0.
According to the definitions of T-PECK and PO-IPE, by converting the index and query keyword sets into an attribute vectorx⟶ and a predicate vector v⟶, respectively, we can take advantage of a PO-IPE scheme to create our scheme. The key to realizing the goal of conjunctive keyword search is constructing a keyword conversion method to change the query and index keyword sets into vectors.


### 2.3.2. Security Definition of PO-IPE

The security of T-PECK depends on that of PO-IPE since PO-IPE is the basis of T-PECK. To present a detailed proof for the security of T-PECK, the security definition of PO-IPE given in [19] is described as follows.Definition 4.
Given a security parameterγ, for any PPT adversary A, if A’s advantage is negligible in the game described below, we say that a PO-IPE scheme is semantically secure against chosen plaintext attacks.(1)
Setup:ℂ creates pk and msk by utilizing Setup (γ) and sends pk to A.(2)
Phase 1:A can ask ℂ for t predicate vectors v⟶1,v⟶2,…,v⟶t adaptively and obtain corresponding keys skv⟶1, skv⟶2, …, skvt⟶.(3)
Challenge: two challenge attribute vectorsx⟶0,x⟶1 are selected randomly by A under the following constraints. For secret keys skv⟶1, skv⟶2, …, skv⟶t requested in Phase 1, one of the following constraints should be satisfied.v⟶j⋅x⟶0≠0 and v⟶j⋅x⟶1≠0.v⟶j⋅x⟶0=0 and v⟶j⋅x⟶1=0, where j∈1,t.ℂ randomly chooses a bit β and sends the ciphertext Cβ⟶Encpk,x⟶β to A.(4)
Phase 2:A can continue to request keys skv⟶t+1, skv⟶t+2, …, skv⟶q, for other predicate vectors, v⟶t+1, v⟶t+2, …, v⟶q. These keys must comply with the restriction given in the challenge phase.(5)
Response: a bitβ′ is given by A. If β′=β, A wins the game.
A’s advantage under the above game is described as(2)AdvGameA=Prβ′=β−12.


## 2.3.1. Framework of PO-IPE

The original definition of PO-IPE was presented in [19]. In this definition, a ciphertext is associated with an attribute vector x⟶, and a key is associated with a predicate vector v⟶ correspondingly. The significant property of PO-IPE is that a ciphertext of x⟶ can be decrypted by a key of v⟶ if and only if v⟶⋅x⟶=0. More explicitly, the framework of PO-IPE is introduced in the following definition.Definition 3.
∑ and F are represented as an arbitrary set of attributes and predicated on ∑, respectively. There are four PPT algorithms in a PO-IPE scheme with ∑ and F, i.e.,(1)
Setup: this algorithm inputs a security parameter γ and outputs pk and master secret key (msk)(2)
KeyGen: given msk and a predicate vector v⟶∈F as input, this algorithm outputs the secret key skv⟶ of v⟶(3)
Enc: this encryption algorithm uses pk to encrypt an attribute vector x⟶∈∑ and outputs the ciphertext C(4)
Dec. taking pk, skv⟶, and C as input, this decryption algorithm outputs 1 or 0 either
Consistency of PO-IPE. For correctly generating Setup1n⟶pk,msk, KeyGenmsk,v⟶⟶skv⟶, and Encpk,x⟶⟶C, for all v⟶∈F and x⟶∈Σ, the decryption algorithm Decpk,skv⟶,C outputs 1 if v⟶⋅x⟶=0, otherwise 0.
According to the definitions of T-PECK and PO-IPE, by converting the index and query keyword sets into an attribute vectorx⟶ and a predicate vector v⟶, respectively, we can take advantage of a PO-IPE scheme to create our scheme. The key to realizing the goal of conjunctive keyword search is constructing a keyword conversion method to change the query and index keyword sets into vectors.


## 2.3.2. Security Definition of PO-IPE

The security of T-PECK depends on that of PO-IPE since PO-IPE is the basis of T-PECK. To present a detailed proof for the security of T-PECK, the security definition of PO-IPE given in [19] is described as follows.Definition 4.
Given a security parameterγ, for any PPT adversary A, if A’s advantage is negligible in the game described below, we say that a PO-IPE scheme is semantically secure against chosen plaintext attacks.(1)
Setup:ℂ creates pk and msk by utilizing Setup (γ) and sends pk to A.(2)
Phase 1:A can ask ℂ for t predicate vectors v⟶1,v⟶2,…,v⟶t adaptively and obtain corresponding keys skv⟶1, skv⟶2, …, skvt⟶.(3)
Challenge: two challenge attribute vectorsx⟶0,x⟶1 are selected randomly by A under the following constraints. For secret keys skv⟶1, skv⟶2, …, skv⟶t requested in Phase 1, one of the following constraints should be satisfied.v⟶j⋅x⟶0≠0 and v⟶j⋅x⟶1≠0.v⟶j⋅x⟶0=0 and v⟶j⋅x⟶1=0, where j∈1,t.ℂ randomly chooses a bit β and sends the ciphertext Cβ⟶Encpk,x⟶β to A.(4)
Phase 2:A can continue to request keys skv⟶t+1, skv⟶t+2, …, skv⟶q, for other predicate vectors, v⟶t+1, v⟶t+2, …, v⟶q. These keys must comply with the restriction given in the challenge phase.(5)
Response: a bitβ′ is given by A. If β′=β, A wins the game.
A’s advantage under the above game is described as(2)AdvGameA=Prβ′=β−12.


## 3. Construction of Index Tree

In this section, we introduce three methods related to building the index tree. The first method is a keyword conversion method which changes document and query keywords into an attribute vector and a predicate vector, respectively. This conversion method is used to construct leaf nodes. The second method aims to create “0-1” vectors of internal nodes of the index tree. Through randomly partitioning all the keywords in the corpus into a set of clusters, we devise a “converting and merging” algorithm to create “0-1” vectors based on these clusters. The third method is a recursive algorithm, which elaborately combines the first and second methods to create the index tree.


### 3.1. Keywords’ Conversion Method

We assume that any keywordw can be expressed as 0,1∗ and define a function H1:0,1∗⟶Zp∗. H1 is collision resistance since p is a prime larger than the number of words in a dictionary. That is to say, if i≠j, then H1wi≠H1wj, where wi and wj are two different keywords. For a document keyword set W=w1,w2,…,wn and a query Q=q1,q2,…,qm, the approach that converts W and Q into an attribute vector and a predicate vector, respectively, is described as follows:(1)
For the keyword setW=w1,w2,…,wn, we construct a function:(3)fx=x−H1w1x−H1w2…x−H1wn=anxn+an−1xn−1+⋯+a0x0.Based on coefficients offx, the vector representation a⟶=a0,a1,…,an of W is now developed.(2)
Similarly, for a queryQ=q1,q2,…,qm, we can construct a vector x⟶=x0,x1,…,xn, where xi=H1q1i+H1q2i+⋯+H1qmi and i∈0,n. x⟶ is the vector representation of Q.(3)
It is noteworthy that if there isQ⊆W, we can verify that a⟶⋅x⟶=0. This property can be used to test whether Q is a subset of W.As a result, we can convert the keyword set of each document into an attribute vectora⟶ and transform each query into a predicate vector x⟶ by adopting the keyword conversion method. These vectors will be used to create the leaf nodes.


### 3.2. Construction of “0-1” Vectors

Suppose that all the keywords in a corpus isDIC=w1,w2,…,wN; we randomly split DIC into a group of document sets S1,S2,…,Sl, where ∪i=1lSi=DIC, Si∩Sj=∅, Si≈Sj, and i≠j. For document sets, S=S1,S2,…,Sl, we give the method of how to use S to construct a vector representing for an internal node or a query as follows.For each document along with a keyword set,W=w1,w2,…,wn, the algorithm for converting a document into a “0-1” vector is described in Algorithm 1. As shown in Algorithm 1, given a document, we first create a zero vector v⟶01 whose length is l+1. Then, for each keyword, wi∈W, if wi∈Sj, the value of the jth dimension of v⟶01 is set to be 1, where i∈1,n and j∈1,l. Finally, the value of the last dimension is set to be 1. For example, if n=3 and l=5, suppose that w1∈S2, w2∈S4, and w3∈S5, and the vector v⟶01 of W=w1,w2,w3 is 0,1,0,1,1,1.For a queryQ along with a keyword set, Q=q1,q2,…,qm, the algorithm for converting a query into a “0-1” vector is described in Algorithm 2. As shown in Algorithm 2, for the query Q, we first create a zero vector q⟶01 whose length is l+1. Then, for each keyword qi∈Q, if qi∈Sj, the value of the jth dimension of q⟶01 is increased by one, where i∈1,m and j∈1,l. At last, the last dimension’s value is set to be −1×m. For example, if m=2 and l=5, suppose that q1∈S1 and q2∈S5, the vector q⟶01 of Q=q1,q2 is 1,0,0,0,1,−2. It can be verified that v⟶01⋅q⟶01=0 if Q⊆W.Moreover, taking two “0-1” vectors as input, we also give a merging algorithm to generate a new “0-1” vector, which is very useful for creating an internal node. The merging algorithm is described in Algorithm3. Suppose that v⟶ is initialized to be a zero vector; the essence of Algorithm 3 is setting v⟶i = 1 if either v⟶1i or v⟶2i equals 1, where i∈1,l+1. For example, if v⟶1=0,1,0,1,0,1 and v⟶2=1,1,0,0,0,1, the output of Algorithm 3 is v⟶=1,1,0,1,0,1.Note that, the “0-1” vector for each document is only used in “CreateTree” algorithm and discarded when the “CreateTree” algorithm is finished.Algorithm 1: Converting a document into a “0-1” vector.
Input: a keyword set W=w1,w2,…,wn of a document and a group of keyword sets S=S1,S2,…,Sl.Output: a “0-1” vector for the document.(1)
Creates a zero vectorv⟶01 whose length is l+1.(2)
fori=1;i<=n;i++do(3)
forj=1;j<=l;j++do(4)
ifwi∈Sjthen(5)
v⟶01j = 1;(6)
end if(7)
end for(8)
end for(9)
v⟶01l+1 = 1;(10)
returnv⟶01;Algorithm 2: Converting a query into a “0-1” vector.
Input: a query Q=q1,q2,…,qm and a group of keyword sets S=S1,S2,…,Sl.Output: a “0-1” vector for the query.(1)
Creates a zero vectorq⟶01 whose length is l+1.(2)
fori=1;i<=m;i++do(3)
forj=1;j<=l;j++do(4)
ifqi∈Sjthen(5)
q⟶01j+=1;(6)
end if(7)
end for(8)
end for(9)
q⟶01l+1 = −1×m;(10)
returnq⟶01;Algorithm 3: A merging algorithm for two “0-1” vectors.
Input: two “0-1” vectors v⟶1 and v⟶2Output: a new “0-1” vector obtained by merging v⟶1 and v⟶2.(1)
Creates a zero vectorv⟶ whose length is l+1.(2)
fori=1;i<=l;i++do(3)
ifv⟶1i==1or v⟶2i==1then(4)
v⟶i = 1(5)
end if(6)
end for(7)
v⟶l+1 = 1;(8)
returnv⟶


### 3.3. Tree Building Algorithm

The tree building algorithm mainly consists of two steps. The first one is to create the leaf node for each document. Each leaf node has two vectors: one is an attribute vector obtained by using keyword conversion method; the other is a “0-1” vector generated by using Algorithm1. The second step is to create the internal node in a “bottom-up” manner. The internal node contains one “0-1” vector generated by using Algorithm 3. The detailed algorithms are presented in Algorithm 4 and 5.Algorithm 4: Creating leaf nodes.
Input: a group of keyword sets W1,W2,…,Wd, where Wi is the keyword set of fi and i∈1,d.Output: A group of leaf nodes.(1)
for each i∈1,ddo(2)
Constructs a leaf nodeu of fi, sets u.ID=GenID, u.Pl=u.Pr=NULL, u.FID be the identifier of fi, and generates u⟶a and u⟶01 according to the keywords conversion method and Algorithm 1, respectively;(3)
Insertsu to CurrentNodeSet;(4)
end for(5)
returnCurrentNodeSetAlgorithm 5: The algorithm for building an index tree and declared by BuildTree (CurrentNodeSet).
Input: the CurrentNodeSet, which contains all the leaf nodes.Output: the plaintext index tree T.(1)
ifCurrentNodeSet==1then(2)
returnCurrentNodeSet;(3)
\\ This is the root node of the tree.(4)
end if(5)
Initializes an empty setTempNodeSet;(6)
Setsk=CurrentNodeSet and i=0;(7)
whilei<kdo(8)
ifi+1<kthen(9)
Creates a parent nodeu for two nodes CurrentNodeSeti and CurrentNodeSeti+1, u.ID=GenID, u.Pl=CurrentNodeSeti, u.Pr=CurrentNodeSeti+1, u.FID=NULL, u⟶a=NULL and generates u⟶01 according to the Algorithm 3;(10)
Insertu to TempNodeSet;(11)
else(12)
InsertCurrentNodeSei to TempNodeSet;(13)
end if(14)
i=i+2;(15)
end while(16)
CurrentNodeSet=BuildTreeTempNodeSet;(17)
\\ recursive calls BuildTree (Algorithm 5).(18)
returnCurrentNodeSet;Algorithm5 is for building an index tree and declared by BuildTree (CurrentNodeSet).A formal definition of the data structure of a tree nodeu is u=ID,u⟶a,u⟶01,Pl,Pr,FID, where ID is u’s identity, u⟶a and u⟶01 are the representation vectors of u, Pl and Pr are two pointers that point u’s left and right children, respectively, and FID is the identity of a document when u is a leaf node. Let GenID be a function that can generate a unique ID for each node. According to Algorithm 4, for the leaf node associated with the document fi, the algorithm runs GenID to obtain an unique ID for the node and sets the value of FID as the identifier of fi. Since there is no child for the leaf node, both Pl and Pr are set to be NULL. Based on the keyword set of fi, u⟶a and u⟶01 are generated by utilizing the keyword converting algorithm and Algorithm 1, respectively.Based on all leaf nodes generated by Algorithm4, the tree building algorithm is presented in Algorithm 5. CurrentNodeSet involves a group of nodes without a parent node. Let CurrentNodeSet be the number of nodes in CurrentNodeSet. If CurrentNodeSet equals 1, this means that the sole node in CurrentNodeSet is the root of the index tree. Otherwise, the internal nodes should be generated by using each pair of nodes in CurrentNodeSet. Concretely, TempNodeSet is initialized as an empty set which is used to store the newly generated nodes. Suppose that CurrentNodeSeti and CurrentNodeSeti+1 are a pair of nodes in CurrentNodeSet; a parent node u of these two nodes is created as follows. ID of u is generated by using the function GenID. Pl and Pr point to the nodes CurrentNodeSei and CurrentNodeSeti+1, respectively. Based on the “0-1” vectors of CurrentNodeSei and CurrentNodeSeti+1, u⟶01 is generated by utilizing Algorithm 3. Both FID and u⟶a are set to be NULL since u is an internal node. Once the node u is created, it will be added to TempNodeSet. Note that if CurrentNodeSet is not even, the last node in CurrentNodeSet is added to TempNodeSet straightforwardly. Through calling Algorithm 5 recursively, the plaintext index tree can be built.Example 1. An example of building an index tree is illustrated in Figure 2. From Figure 2, an index tree of F=f1,f2,…,f8 is given, where the dimension of the “0-1” vector for each node is 6. There are three steps for building the tree. The first step is changing the keyword set of each document into an attribute vector (denoted by ai⟶) and a “0-1” vector (denoted by a sequence of “0-1”) by using the keyword conversion method and Algorithm 1, respectively. After this step, each document is transformed into a leaf node with an attribute vector and a “0-1” vector. The second step is building the index tree based on the “0-1”vectors of the leaf nodes in a bottom-up manner by taking advantage of Algorithm 4 and 5. After this step, the index tree has been established, and each internal node in the tree owns a “0-1” vector. The third step is deleting all “0-1” vectors in the leaf nodes. The reason why we delete these vectors is that the “0-1” vectors contained in leaf nodes are only used to construct internal nodes of the index tree. In the search process, the leaf node only utilizes the attribute vector to perform keywords matching test. This step can reduce the storage cost of the index tree.Figure 2
An example of building an index tree.


## 3.1. Keywords’ Conversion Method

We assume that any keywordw can be expressed as 0,1∗ and define a function H1:0,1∗⟶Zp∗. H1 is collision resistance since p is a prime larger than the number of words in a dictionary. That is to say, if i≠j, then H1wi≠H1wj, where wi and wj are two different keywords. For a document keyword set W=w1,w2,…,wn and a query Q=q1,q2,…,qm, the approach that converts W and Q into an attribute vector and a predicate vector, respectively, is described as follows:(1)
For the keyword setW=w1,w2,…,wn, we construct a function:(3)fx=x−H1w1x−H1w2…x−H1wn=anxn+an−1xn−1+⋯+a0x0.Based on coefficients offx, the vector representation a⟶=a0,a1,…,an of W is now developed.(2)
Similarly, for a queryQ=q1,q2,…,qm, we can construct a vector x⟶=x0,x1,…,xn, where xi=H1q1i+H1q2i+⋯+H1qmi and i∈0,n. x⟶ is the vector representation of Q.(3)
It is noteworthy that if there isQ⊆W, we can verify that a⟶⋅x⟶=0. This property can be used to test whether Q is a subset of W.As a result, we can convert the keyword set of each document into an attribute vectora⟶ and transform each query into a predicate vector x⟶ by adopting the keyword conversion method. These vectors will be used to create the leaf nodes.


## 3.2. Construction of “0-1” Vectors

Suppose that all the keywords in a corpus isDIC=w1,w2,…,wN; we randomly split DIC into a group of document sets S1,S2,…,Sl, where ∪i=1lSi=DIC, Si∩Sj=∅, Si≈Sj, and i≠j. For document sets, S=S1,S2,…,Sl, we give the method of how to use S to construct a vector representing for an internal node or a query as follows.For each document along with a keyword set,W=w1,w2,…,wn, the algorithm for converting a document into a “0-1” vector is described in Algorithm 1. As shown in Algorithm 1, given a document, we first create a zero vector v⟶01 whose length is l+1. Then, for each keyword, wi∈W, if wi∈Sj, the value of the jth dimension of v⟶01 is set to be 1, where i∈1,n and j∈1,l. Finally, the value of the last dimension is set to be 1. For example, if n=3 and l=5, suppose that w1∈S2, w2∈S4, and w3∈S5, and the vector v⟶01 of W=w1,w2,w3 is 0,1,0,1,1,1.For a queryQ along with a keyword set, Q=q1,q2,…,qm, the algorithm for converting a query into a “0-1” vector is described in Algorithm 2. As shown in Algorithm 2, for the query Q, we first create a zero vector q⟶01 whose length is l+1. Then, for each keyword qi∈Q, if qi∈Sj, the value of the jth dimension of q⟶01 is increased by one, where i∈1,m and j∈1,l. At last, the last dimension’s value is set to be −1×m. For example, if m=2 and l=5, suppose that q1∈S1 and q2∈S5, the vector q⟶01 of Q=q1,q2 is 1,0,0,0,1,−2. It can be verified that v⟶01⋅q⟶01=0 if Q⊆W.Moreover, taking two “0-1” vectors as input, we also give a merging algorithm to generate a new “0-1” vector, which is very useful for creating an internal node. The merging algorithm is described in Algorithm3. Suppose that v⟶ is initialized to be a zero vector; the essence of Algorithm 3 is setting v⟶i = 1 if either v⟶1i or v⟶2i equals 1, where i∈1,l+1. For example, if v⟶1=0,1,0,1,0,1 and v⟶2=1,1,0,0,0,1, the output of Algorithm 3 is v⟶=1,1,0,1,0,1.Note that, the “0-1” vector for each document is only used in “CreateTree” algorithm and discarded when the “CreateTree” algorithm is finished.Algorithm 1: Converting a document into a “0-1” vector.
Input: a keyword set W=w1,w2,…,wn of a document and a group of keyword sets S=S1,S2,…,Sl.Output: a “0-1” vector for the document.(1)
Creates a zero vectorv⟶01 whose length is l+1.(2)
fori=1;i<=n;i++do(3)
forj=1;j<=l;j++do(4)
ifwi∈Sjthen(5)
v⟶01j = 1;(6)
end if(7)
end for(8)
end for(9)
v⟶01l+1 = 1;(10)
returnv⟶01;Algorithm 2: Converting a query into a “0-1” vector.
Input: a query Q=q1,q2,…,qm and a group of keyword sets S=S1,S2,…,Sl.Output: a “0-1” vector for the query.(1)
Creates a zero vectorq⟶01 whose length is l+1.(2)
fori=1;i<=m;i++do(3)
forj=1;j<=l;j++do(4)
ifqi∈Sjthen(5)
q⟶01j+=1;(6)
end if(7)
end for(8)
end for(9)
q⟶01l+1 = −1×m;(10)
returnq⟶01;Algorithm 3: A merging algorithm for two “0-1” vectors.
Input: two “0-1” vectors v⟶1 and v⟶2Output: a new “0-1” vector obtained by merging v⟶1 and v⟶2.(1)
Creates a zero vectorv⟶ whose length is l+1.(2)
fori=1;i<=l;i++do(3)
ifv⟶1i==1or v⟶2i==1then(4)
v⟶i = 1(5)
end if(6)
end for(7)
v⟶l+1 = 1;(8)
returnv⟶


## 3.3. Tree Building Algorithm

The tree building algorithm mainly consists of two steps. The first one is to create the leaf node for each document. Each leaf node has two vectors: one is an attribute vector obtained by using keyword conversion method; the other is a “0-1” vector generated by using Algorithm1. The second step is to create the internal node in a “bottom-up” manner. The internal node contains one “0-1” vector generated by using Algorithm 3. The detailed algorithms are presented in Algorithm 4 and 5.Algorithm 4: Creating leaf nodes.
Input: a group of keyword sets W1,W2,…,Wd, where Wi is the keyword set of fi and i∈1,d.Output: A group of leaf nodes.(1)
for each i∈1,ddo(2)
Constructs a leaf nodeu of fi, sets u.ID=GenID, u.Pl=u.Pr=NULL, u.FID be the identifier of fi, and generates u⟶a and u⟶01 according to the keywords conversion method and Algorithm 1, respectively;(3)
Insertsu to CurrentNodeSet;(4)
end for(5)
returnCurrentNodeSetAlgorithm 5: The algorithm for building an index tree and declared by BuildTree (CurrentNodeSet).
Input: the CurrentNodeSet, which contains all the leaf nodes.Output: the plaintext index tree T.(1)
ifCurrentNodeSet==1then(2)
returnCurrentNodeSet;(3)
\\ This is the root node of the tree.(4)
end if(5)
Initializes an empty setTempNodeSet;(6)
Setsk=CurrentNodeSet and i=0;(7)
whilei<kdo(8)
ifi+1<kthen(9)
Creates a parent nodeu for two nodes CurrentNodeSeti and CurrentNodeSeti+1, u.ID=GenID, u.Pl=CurrentNodeSeti, u.Pr=CurrentNodeSeti+1, u.FID=NULL, u⟶a=NULL and generates u⟶01 according to the Algorithm 3;(10)
Insertu to TempNodeSet;(11)
else(12)
InsertCurrentNodeSei to TempNodeSet;(13)
end if(14)
i=i+2;(15)
end while(16)
CurrentNodeSet=BuildTreeTempNodeSet;(17)
\\ recursive calls BuildTree (Algorithm 5).(18)
returnCurrentNodeSet;Algorithm5 is for building an index tree and declared by BuildTree (CurrentNodeSet).A formal definition of the data structure of a tree nodeu is u=ID,u⟶a,u⟶01,Pl,Pr,FID, where ID is u’s identity, u⟶a and u⟶01 are the representation vectors of u, Pl and Pr are two pointers that point u’s left and right children, respectively, and FID is the identity of a document when u is a leaf node. Let GenID be a function that can generate a unique ID for each node. According to Algorithm 4, for the leaf node associated with the document fi, the algorithm runs GenID to obtain an unique ID for the node and sets the value of FID as the identifier of fi. Since there is no child for the leaf node, both Pl and Pr are set to be NULL. Based on the keyword set of fi, u⟶a and u⟶01 are generated by utilizing the keyword converting algorithm and Algorithm 1, respectively.Based on all leaf nodes generated by Algorithm4, the tree building algorithm is presented in Algorithm 5. CurrentNodeSet involves a group of nodes without a parent node. Let CurrentNodeSet be the number of nodes in CurrentNodeSet. If CurrentNodeSet equals 1, this means that the sole node in CurrentNodeSet is the root of the index tree. Otherwise, the internal nodes should be generated by using each pair of nodes in CurrentNodeSet. Concretely, TempNodeSet is initialized as an empty set which is used to store the newly generated nodes. Suppose that CurrentNodeSeti and CurrentNodeSeti+1 are a pair of nodes in CurrentNodeSet; a parent node u of these two nodes is created as follows. ID of u is generated by using the function GenID. Pl and Pr point to the nodes CurrentNodeSei and CurrentNodeSeti+1, respectively. Based on the “0-1” vectors of CurrentNodeSei and CurrentNodeSeti+1, u⟶01 is generated by utilizing Algorithm 3. Both FID and u⟶a are set to be NULL since u is an internal node. Once the node u is created, it will be added to TempNodeSet. Note that if CurrentNodeSet is not even, the last node in CurrentNodeSet is added to TempNodeSet straightforwardly. Through calling Algorithm 5 recursively, the plaintext index tree can be built.Example 1. An example of building an index tree is illustrated in Figure 2. From Figure 2, an index tree of F=f1,f2,…,f8 is given, where the dimension of the “0-1” vector for each node is 6. There are three steps for building the tree. The first step is changing the keyword set of each document into an attribute vector (denoted by ai⟶) and a “0-1” vector (denoted by a sequence of “0-1”) by using the keyword conversion method and Algorithm 1, respectively. After this step, each document is transformed into a leaf node with an attribute vector and a “0-1” vector. The second step is building the index tree based on the “0-1”vectors of the leaf nodes in a bottom-up manner by taking advantage of Algorithm 4 and 5. After this step, the index tree has been established, and each internal node in the tree owns a “0-1” vector. The third step is deleting all “0-1” vectors in the leaf nodes. The reason why we delete these vectors is that the “0-1” vectors contained in leaf nodes are only used to construct internal nodes of the index tree. In the search process, the leaf node only utilizes the attribute vector to perform keywords matching test. This step can reduce the storage cost of the index tree.Figure 2
An example of building an index tree.


## 4. The Proposed Scheme

In this section, we give a T-PECK scheme with sublinear search complexity based on the aforementioned algorithms. After this concrete construction, a detailed proof is given to demonstrate the security of T-PECK based on the security definition.


### 4.1. Construction of T-PECK

According to Definition3, we set SetupIPE, KeyGenIPEpkIPE,mskIPE,v⟶, EncIPEpkIPE,x⟶, and DecIPEpkIPE,c,skv⟶ as four algorithms in PO-IPE, where pkIPE and mskIPE are the public key and master secret key, respectively, x⟶ and v⟶ are the attribute vector and predicate vector, respectively, and c and skv⟶ are the ciphertext and secret key generated by utilizing EncIPE and KeyGenIPE, respectively. According to the PO-IPE scheme [19], we construct our T-PECK scheme as follows.KeyGen (γ): given a security parameter γ, using the SetupIPE algorithm, this algorithm generates pkIPE and mskIPE and then sets pk=pkIPE and sk=mskIPE in which pk is given to data owner and sk is given to the data user.CreateTree (W): given a group of keyword sets W1,W2,…,Wd in which each keyword set Wi is associated with a document fi, this algorithm builds the index tree T according to Algorithm 4 and 5.IndexBuild (pk,T): in order to encrypt the index tree T, a subalgorithm “encryptNode (pk, u)” is presented in Algorithm 6, where u is a tree node. As shown in Algorithm 6, if u is a leaf node of T, “encryptNode” calls EncIPEpk,u⟶a to generate cu⟶a and replaces u⟶a with cu⟶a. Otherwise, it calls EncIPEpk,u⟶01 to generate cu⟶01 and replaces u⟶01 with cu⟶01 and then recursively traverses its children nodes. Based on Algorithm 6, the IndexBuild algorithm calls encryptNode (pk, r) to generate the encrypted index IT, where r is the root node of T, and uploads IT to the cloud server.Trapdoor (sk,pk,Q): given a keyword query Q=q1,q2,…qm, the algorithm first generates a predicate vector v⟶ and a “0-1” vector q⟶01 by utilizing the keyword conversion approach and Algorithm 2, respectively. Then, it generates t1=KeyGenIPEsk,pk,x⟶ and t2=KeyGenIPEsk,pk,q⟶01. Finally, it sends the trapdoor TQ=t1,t2 of the query Q to the cloud server.Search (pk,TQ,IT): in order to search the encrypted index tree IT, a subalgorithm “searchNode (pk, TQ, u, RList)” is given in Algorithm 7, where u is a tree node and RList is used to store the search result. Concretely, for an internal node u, “searchNode” computes R=DecIPEpk,cu⟶01,t2. If R=1, it continues to search the children nodes of u in a recursive way; Otherwise, it stops. For a leaf node u, the algorithm computes R=DecIPEpk,cu⟶01,t1. If R=1, it adds the FID of this node in RList. Based on Algorithm 7, the “Search” algorithm first initializes an empty set RList, then calls searchNode (pk, TQ, r, and RList) to obtain all documents matched to the query Q, where r is the root node of T, and finally outputs RList to the data user.Example 2. We also give Figure 3 to illustrate the search process. From Figure 3, we convert the query Q=w3,w6,w15 into a “0-1” vector and a predicate vector v⟶ by using Algorithm 2 and the keyword conversion method, respectively. Based on the index tree given in example 1, the search process begins with the root node and first reaches to leaf nodes f3 and f4 since “0-1” vectors of r11 and r22 are both matching the “0-1” vector of the query Q. Then, the search algorithm computes values of a⟶3⋅v⟶ and a⟶4⋅v⟶ and adds f3 to the result list RList due to a⟶3⋅v⟶=0 and a⟶4⋅v⟶≠0. After that, the search algorithm checks the internal node r12. Since the “0-1” vector of the query fails to match that of the node r12, the children of r12 will not be reached. Finally, the algorithm outputs RList=f3.Figure 3
An example of search process.Algorithm 6: The algorithm for encrypting each node in the index tree, declared by encryptNode (pk, u).
Input: a tree node u and the public key pk.Output: an encrypted node u.(1)
ifu is NULLthen(2)
return(3)
end if(4)
ifu is a leaf node then(5)
callsEncIPEpk,u⟶a to generate cua⟶, and replaces u⟶a with cu⟶a;(6)
else\\ This means u is an internal node.(7)
callsEncIPEpk,u⟶01 to generate cu⟶01, and replaces u⟶01 with cu⟶01;(8)
calls encryptNode (pk, u.Pl);(9)
calls encryptNode (pk, u.Pr);(10)
end if(11)
returnAlgorithm 7: The algorithm for searching each node in the index tree: searchNode (pk, TQ, u, RList).
Input: the public key pk, a trapdoor TQ for query Q, an encrypted node u, and a matched document set RList.Output:RList.(1)
ifu is NULLthen(2)
return(3)
end if(4)
ifu is a leaf node then(5)
computesR=Decpk,cu⟶a,t1;(6)
ifR==1then(7)
addsu.FID to the RList;(8)
end if(9)
else\\ This means u is an internal node.(10)
callsR=Decpk,cu⟶01,t2;(11)
ifR==1then(12)
searchNode (pk, TQ, u.Pl, RList);(13)
searchNode (pk, TQ, u.Pr, RList);(14)
end if(15)
end if(16)
return


### 4.2. Security Proof

Our T-PECK scheme is constructed over the PO-IPE scheme. Thus, T-PECK’s security is guaranteed by the fully secure PO-IPE scheme. To demonstrate the security of T-PECK, we give Proposition1.Proposition 1.
If the PO-IPE scheme is semantically secure against chosen plaintext attacks, our T-PECK scheme isL-semantically secure against chosen plaintext attacks, where L is the leakage function given in Section 2.2.Proof.
We can argue that a PPT algorithmA can break the PO-IPE scheme if A can break the T-PECK scheme. The proof process is given as follows.(1)
Setup: the challengerℂ utilizes the SetupIPE algorithm to generate pkIPE and mskIPE and sets pk=pkIPE and sk=mskIPE, where pk and sk are the public key and secret key of T-PECK.(2)
Phase 1:A can adaptively request trapdoors of queries Q1,Q2,…,Qt. For each query Qi, the challenger ℂ first generates two vectors v⟶i and q⟶01i and then uses the KeyGenIPE algorithm to generate the trapdoor TQi=t1i,t2i in which t1i=KeyGenIPEpk,sk,v⟶i and t2i=KeyGenIPEpk,sk,q⟶01i, where i∈1,t. Note that, each trapdoor can be seen as two decryption keys of PO-IPE.(3)
Challenge: after phase 1,A generates two plaintext trees T0 and T1 under the restriction that LT0,Qi=LT1,Qi, where i∈1,t, and sends these two trees to ℂ. Note that, ℂ can select two leaf nodes u0 and u1 from T0 and T1, respectively, as two challenge nodes of PO-IPE. After receiving them, flipping a coin β∈0,1, ℂ generates an index tree ITβ by running IndexBuildpk,Tβ and sends it to A. According to the IndexBuild algorithm, we know that each node in this encrypted index tree is a ciphertext of PO-IPE. Thus, we can use the encrypted vector of uβ in ITβ as the challenge ciphertext of PO-IPE.(4)
Phase 2:A can continue to ask ℂ for trapdoors under the restriction described above. Since each trapdoor is generated by using KeyGenIPE algorithm, these trapdoors can still be reckoned as a set of decryption keys of PO-IPE.(5)
Response:A outputs a guess β′. This guess is used as the guess of the security game of PO-IPE.
According to the above game, we can find that the security game in T-PECK is consistent to that in PO-IPE. If this is a PPT adversaryA which can distinguish two encrypted index trees of the T-PECK, we can use A to distinguish two encrypted vectors of PO-IPE. Thus, we can state that our T-PECK is secure if PO-IPE is secure.


### 4.3. Dynamic Update Operations

Previous PECK schemes usually utilized forward index structure, which enables dynamic update for documents inherently. Considering that dynamic update is crucial for the usability of PECK, it is necessary to enable the T-PECK scheme to support some dynamic operations such as document insertion, deletion, and modification. Since utilizing the tree-based index structure, we realize update operations by updating the tree’s nodes. Inspired by the update approach given in [16], we devise the update algorithm as follows:(1)
Deletion: if one data owner wants to delete a documentfi from the index tree, he/she first finds the leaf node related to fi and sets this leaf node as a fake one rather than deleting it. Then, he/she encrypts this fake node and sends it to the cloud server along with the location information of this leaf node. When the cloud server receives this node, it can perform the deletion operation by replacing the target leaf node with the fake one.(2)
Insertion: if a data owner wants to insert a documentfi to the tree, he/she first creates a leaf node for fi by using Algorithm 4. Then, the data owner will find a fake leaf node and substitute the fake node with the new leaf node. After this, according to the leaf node, the data owner updates all internal nodes on the path from the root node to the new leaf node. Finally, the data owner encrypts the leaf node and the corresponding internal nodes and then sends them along with the position information to the cloud server. When the cloud server receives these nodes, it realizes the insertion operation by replacing these nodes according to the position information. In addition, if there is no fake leaf node that can be replaced, the data owner will generate a new encrypted index tree with many fake leaf nodes and one target leaf node. After receiving this index tree, the cloud server will combine these two index trees as a new one.(3)
Modification: if the data owner wants to modify a leaf node, he/she can delete this leaf node first and then insert a new leaf node according to the modification information.The keywords in the dictionary will be changed after a period of documents insertion and deletion. Fortunately, this situation does not have much impact on the T-PECK scheme. For the leaf node of a documentfi, the attribute vector of this leaf node is constructed by using the keyword set Wi of fi, which means that the keyword conversion method can still work well even Wi contains some new keywords. For the “0-1” vector of an internal node, we first review the process of creating a “0-1” vector. The dictionary is divided into a set of keyword sets, and each keyword set is associated with one dimension of the “0-1” vector. When a new keyword is added to the dictionary, we can put this keyword into any keyword set, which will not affect the “0-1” vectors generated before. For example, suppose that the dictionary is w1,w2,w3,w4,w5 and is divided into three sets w1,w2, w3,w4, and w5 and the new keyword sets are w1,w2, w3,w4, and w5,w6 after adding a keyword w6 in the dictionary. Note that the “0-1” vectors for w1,w5 are both “101” before and after adding w6. Thus, according to the above analysis, the dynamic update method of our scheme is practicable.


## 4.1. Construction of T-PECK

According to Definition3, we set SetupIPE, KeyGenIPEpkIPE,mskIPE,v⟶, EncIPEpkIPE,x⟶, and DecIPEpkIPE,c,skv⟶ as four algorithms in PO-IPE, where pkIPE and mskIPE are the public key and master secret key, respectively, x⟶ and v⟶ are the attribute vector and predicate vector, respectively, and c and skv⟶ are the ciphertext and secret key generated by utilizing EncIPE and KeyGenIPE, respectively. According to the PO-IPE scheme [19], we construct our T-PECK scheme as follows.KeyGen (γ): given a security parameter γ, using the SetupIPE algorithm, this algorithm generates pkIPE and mskIPE and then sets pk=pkIPE and sk=mskIPE in which pk is given to data owner and sk is given to the data user.CreateTree (W): given a group of keyword sets W1,W2,…,Wd in which each keyword set Wi is associated with a document fi, this algorithm builds the index tree T according to Algorithm 4 and 5.IndexBuild (pk,T): in order to encrypt the index tree T, a subalgorithm “encryptNode (pk, u)” is presented in Algorithm 6, where u is a tree node. As shown in Algorithm 6, if u is a leaf node of T, “encryptNode” calls EncIPEpk,u⟶a to generate cu⟶a and replaces u⟶a with cu⟶a. Otherwise, it calls EncIPEpk,u⟶01 to generate cu⟶01 and replaces u⟶01 with cu⟶01 and then recursively traverses its children nodes. Based on Algorithm 6, the IndexBuild algorithm calls encryptNode (pk, r) to generate the encrypted index IT, where r is the root node of T, and uploads IT to the cloud server.Trapdoor (sk,pk,Q): given a keyword query Q=q1,q2,…qm, the algorithm first generates a predicate vector v⟶ and a “0-1” vector q⟶01 by utilizing the keyword conversion approach and Algorithm 2, respectively. Then, it generates t1=KeyGenIPEsk,pk,x⟶ and t2=KeyGenIPEsk,pk,q⟶01. Finally, it sends the trapdoor TQ=t1,t2 of the query Q to the cloud server.Search (pk,TQ,IT): in order to search the encrypted index tree IT, a subalgorithm “searchNode (pk, TQ, u, RList)” is given in Algorithm 7, where u is a tree node and RList is used to store the search result. Concretely, for an internal node u, “searchNode” computes R=DecIPEpk,cu⟶01,t2. If R=1, it continues to search the children nodes of u in a recursive way; Otherwise, it stops. For a leaf node u, the algorithm computes R=DecIPEpk,cu⟶01,t1. If R=1, it adds the FID of this node in RList. Based on Algorithm 7, the “Search” algorithm first initializes an empty set RList, then calls searchNode (pk, TQ, r, and RList) to obtain all documents matched to the query Q, where r is the root node of T, and finally outputs RList to the data user.Example 2. We also give Figure 3 to illustrate the search process. From Figure 3, we convert the query Q=w3,w6,w15 into a “0-1” vector and a predicate vector v⟶ by using Algorithm 2 and the keyword conversion method, respectively. Based on the index tree given in example 1, the search process begins with the root node and first reaches to leaf nodes f3 and f4 since “0-1” vectors of r11 and r22 are both matching the “0-1” vector of the query Q. Then, the search algorithm computes values of a⟶3⋅v⟶ and a⟶4⋅v⟶ and adds f3 to the result list RList due to a⟶3⋅v⟶=0 and a⟶4⋅v⟶≠0. After that, the search algorithm checks the internal node r12. Since the “0-1” vector of the query fails to match that of the node r12, the children of r12 will not be reached. Finally, the algorithm outputs RList=f3.Figure 3
An example of search process.Algorithm 6: The algorithm for encrypting each node in the index tree, declared by encryptNode (pk, u).
Input: a tree node u and the public key pk.Output: an encrypted node u.(1)
ifu is NULLthen(2)
return(3)
end if(4)
ifu is a leaf node then(5)
callsEncIPEpk,u⟶a to generate cua⟶, and replaces u⟶a with cu⟶a;(6)
else\\ This means u is an internal node.(7)
callsEncIPEpk,u⟶01 to generate cu⟶01, and replaces u⟶01 with cu⟶01;(8)
calls encryptNode (pk, u.Pl);(9)
calls encryptNode (pk, u.Pr);(10)
end if(11)
returnAlgorithm 7: The algorithm for searching each node in the index tree: searchNode (pk, TQ, u, RList).
Input: the public key pk, a trapdoor TQ for query Q, an encrypted node u, and a matched document set RList.Output:RList.(1)
ifu is NULLthen(2)
return(3)
end if(4)
ifu is a leaf node then(5)
computesR=Decpk,cu⟶a,t1;(6)
ifR==1then(7)
addsu.FID to the RList;(8)
end if(9)
else\\ This means u is an internal node.(10)
callsR=Decpk,cu⟶01,t2;(11)
ifR==1then(12)
searchNode (pk, TQ, u.Pl, RList);(13)
searchNode (pk, TQ, u.Pr, RList);(14)
end if(15)
end if(16)
return


## 4.2. Security Proof

Our T-PECK scheme is constructed over the PO-IPE scheme. Thus, T-PECK’s security is guaranteed by the fully secure PO-IPE scheme. To demonstrate the security of T-PECK, we give Proposition1.Proposition 1.
If the PO-IPE scheme is semantically secure against chosen plaintext attacks, our T-PECK scheme isL-semantically secure against chosen plaintext attacks, where L is the leakage function given in Section 2.2.Proof.
We can argue that a PPT algorithmA can break the PO-IPE scheme if A can break the T-PECK scheme. The proof process is given as follows.(1)
Setup: the challengerℂ utilizes the SetupIPE algorithm to generate pkIPE and mskIPE and sets pk=pkIPE and sk=mskIPE, where pk and sk are the public key and secret key of T-PECK.(2)
Phase 1:A can adaptively request trapdoors of queries Q1,Q2,…,Qt. For each query Qi, the challenger ℂ first generates two vectors v⟶i and q⟶01i and then uses the KeyGenIPE algorithm to generate the trapdoor TQi=t1i,t2i in which t1i=KeyGenIPEpk,sk,v⟶i and t2i=KeyGenIPEpk,sk,q⟶01i, where i∈1,t. Note that, each trapdoor can be seen as two decryption keys of PO-IPE.(3)
Challenge: after phase 1,A generates two plaintext trees T0 and T1 under the restriction that LT0,Qi=LT1,Qi, where i∈1,t, and sends these two trees to ℂ. Note that, ℂ can select two leaf nodes u0 and u1 from T0 and T1, respectively, as two challenge nodes of PO-IPE. After receiving them, flipping a coin β∈0,1, ℂ generates an index tree ITβ by running IndexBuildpk,Tβ and sends it to A. According to the IndexBuild algorithm, we know that each node in this encrypted index tree is a ciphertext of PO-IPE. Thus, we can use the encrypted vector of uβ in ITβ as the challenge ciphertext of PO-IPE.(4)
Phase 2:A can continue to ask ℂ for trapdoors under the restriction described above. Since each trapdoor is generated by using KeyGenIPE algorithm, these trapdoors can still be reckoned as a set of decryption keys of PO-IPE.(5)
Response:A outputs a guess β′. This guess is used as the guess of the security game of PO-IPE.
According to the above game, we can find that the security game in T-PECK is consistent to that in PO-IPE. If this is a PPT adversaryA which can distinguish two encrypted index trees of the T-PECK, we can use A to distinguish two encrypted vectors of PO-IPE. Thus, we can state that our T-PECK is secure if PO-IPE is secure.


## 4.3. Dynamic Update Operations

Previous PECK schemes usually utilized forward index structure, which enables dynamic update for documents inherently. Considering that dynamic update is crucial for the usability of PECK, it is necessary to enable the T-PECK scheme to support some dynamic operations such as document insertion, deletion, and modification. Since utilizing the tree-based index structure, we realize update operations by updating the tree’s nodes. Inspired by the update approach given in [16], we devise the update algorithm as follows:(1)
Deletion: if one data owner wants to delete a documentfi from the index tree, he/she first finds the leaf node related to fi and sets this leaf node as a fake one rather than deleting it. Then, he/she encrypts this fake node and sends it to the cloud server along with the location information of this leaf node. When the cloud server receives this node, it can perform the deletion operation by replacing the target leaf node with the fake one.(2)
Insertion: if a data owner wants to insert a documentfi to the tree, he/she first creates a leaf node for fi by using Algorithm 4. Then, the data owner will find a fake leaf node and substitute the fake node with the new leaf node. After this, according to the leaf node, the data owner updates all internal nodes on the path from the root node to the new leaf node. Finally, the data owner encrypts the leaf node and the corresponding internal nodes and then sends them along with the position information to the cloud server. When the cloud server receives these nodes, it realizes the insertion operation by replacing these nodes according to the position information. In addition, if there is no fake leaf node that can be replaced, the data owner will generate a new encrypted index tree with many fake leaf nodes and one target leaf node. After receiving this index tree, the cloud server will combine these two index trees as a new one.(3)
Modification: if the data owner wants to modify a leaf node, he/she can delete this leaf node first and then insert a new leaf node according to the modification information.The keywords in the dictionary will be changed after a period of documents insertion and deletion. Fortunately, this situation does not have much impact on the T-PECK scheme. For the leaf node of a documentfi, the attribute vector of this leaf node is constructed by using the keyword set Wi of fi, which means that the keyword conversion method can still work well even Wi contains some new keywords. For the “0-1” vector of an internal node, we first review the process of creating a “0-1” vector. The dictionary is divided into a set of keyword sets, and each keyword set is associated with one dimension of the “0-1” vector. When a new keyword is added to the dictionary, we can put this keyword into any keyword set, which will not affect the “0-1” vectors generated before. For example, suppose that the dictionary is w1,w2,w3,w4,w5 and is divided into three sets w1,w2, w3,w4, and w5 and the new keyword sets are w1,w2, w3,w4, and w5,w6 after adding a keyword w6 in the dictionary. Note that the “0-1” vectors for w1,w5 are both “101” before and after adding w6. Thus, according to the above analysis, the dynamic update method of our scheme is practicable.


## 5. Performance Evaluation

We will analyze the theoretical and experimental performance of our scheme in this section by comparing other recent PECK schemes.


### 5.1. Theoretical Analysis

The theoretical analysis of the proposed T-PECK scheme is evaluated and compared with the previous PECK schemes in terms of space and computation complexity. We choose four representative PECK schemes proposed recently for comparison. For simplicity, we denote these four PECK schemes introduced in [8, 10, 13] by SPE-CKS, SPE-SMKS, SA-SCF-PECKS, and PMSEHS, respectively. For clarity, we define three important parameters associated with these PECK schemes. The first parameter is the number of keywords in an index, denoted by n; the second one is the number of keywords in a query, denoted by m; the third one is the number of documents in a corpus, denoted by d. In addition, for PMSEHS, since the search process only accesses the documents containing the first keyword in the query, we denote the number of documents matching the first keyword in the query by r1. For T-PECK, we denote the number of keyword sets by k, and the number of documents whose “0-1” vector matches the query vector by r2 since only these documents will be verified in the search process. According to these denotations, we present Table 3 to show the comparison of time and space complexities among T-PECK and other previous PECK schemes.Table 3
Comparison with previous PECK schemes on time and space complexity.
SchemeT1T2T3S1S2SPE-CKS [8]2ndPnPndEndGnGSPE-SMKS [9]2n+4dPn+4Pn+1dP+3dEn+3dG3GT+n+1ZP∗SA-SCF-PECKS [10]2dE+n+4dPn+2P4dP+n+2dEn+2dG+dGTn+2G+ZP∗PMSEHS [13]2ndP+n2dE3mP2mr1E4ndG+n2dGT2mGT-PECK2n+2kdP+2dEn+kPnr2log2dP+3r2log2dEnd+nkG+2dGT3n+3kGDenotationG and GT are two cyclic groups of a large prime order, and e^:G×G⟶GT is a bilinear map [35]P and PT: the time cost of one exponentiation computation in G, and GT, respectivelyE: the time cost of one pairing operationZP∗, G and GT: the size of an element of ZP∗, G and GT, respectivelyT1, T2, and T3 represent the time complexity of index building, trapdoor generation, and search, respectivelyS1 and S2 represent the space complexity of index and trapdoor, respectivelyAs shown in Table3, the time complexities of search in SPE-CKS, SPE-SMKS, and SA-SCF-PECKS are all linear with d since these three schemes adopt the forward index, while that in our scheme is linear with log2d due to utilizing tree index structure. According to the tree building algorithm (Algorithm 5), we can evaluate that the search algorithm needs at most access r2∗log2d nodes in the index tree. Since the search algorithm requires the pairing operations three times for each node, T-PECK will perform pairing operations at most 3r2∗log2d times. Because d is a large number and commonly much bigger than n and r2, we can reckon that the proposed scheme is more efficient than SPE-CKS, SPE-SMKS, and SA-SCF-PECKS in the search process. In addition, because the tree index structure contains many internal nodes to accelerate the search process, the time and storage consumption of our scheme is more than that in SPE-CKS, SPE-SMKS, and SA-SCF-PECKS.Table3 also shows that the time complexity of search in PMSEHS is linear with r1 since it utilizes a hidden structure to build the index. Compared with PMSEHS, the T-PECK scheme needs less search time when r2log2d<r1. According to the definition of r1, r2, and d, we know our scheme is more efficient when the term frequency of query keywords is high and d is relatively small. Moreover, PMSEHS needs much more time and storage overhead for index generation and storage than T-PECK since the hidden structure requires many group elements of GT to speed up the query process. As shown in Table 3, the time complexity of index building and the space complexity of index storage in PMSEHS are both linear with On2 while that in T-PECK are both linear with On. Thus, we argue that our scheme can achieve a sublinear search complexity without sacrificing the index generation time and storage space.


### 5.2. Experimental Results

Based on Java Pairing-Based Cryptography (JPBC) library [36], our scheme is implemented on an environment in which the CPU is Intel (R) Core (TM) i7-4570 at 3.60 GHz and the memory size is 16 GB. A type A pair is used to realize the bilinear map in our scheme. The base field size of this pair is 128 bits, and the security level of this pair is equivalent to 1024 bits of DLOG [36]. The real-world corpus that our experiment adopts is an e-mail dataset named by Enron [37]. To quantify the efficiency of our scheme, we mainly focus on three parameters related to PECK in the experiment. These three parameters are n, d, and m mentioned in Section 5.1. To demonstrate the advantages of T-PECK, two previous PECK schemes, that is, SPE-CKS and PMSEHS, are compared with our scheme. The reason for choosing these two schemes is that SPE-CKS adopts a forward index, while PMSEHS utilizes a hidden structure. The comparison experiment involves the time overhead of index building, trapdoor generation, and search.


#### 5.2.1. Impact of the Number of Keywords in a Document (n) on Performance

For a query with 6 keywords (m=6) and a corpus with 300 documents (d=300), as n increases, Figure 4 shows the following facts.(1)
The execution time of index building in PMSEHS far exceeds than that in SPE-CKS and T-PECK since PMSEHS performs lots of pairing operations for accelerating the search process. T-PECK needs more index building time than SPE-CKS since requiring encrypting internal nodes.(2)
The trapdoor generation time in PMSEHS is independent ofn and is better than other two scheme for m<n. T-PECK needs less time for trapdoor generation than SPE-CKS since it requires less time for exponentiation computation over group elements.(3)
The search complexity in SPE-CKS is linear withn while other two schemes are sublinear with n. As n increases, the search time of PMSEHS and T-PECK grows slightly due to the growth of parameters r1 and r2. In addition, the reason why T-PECK needs more time than PMSEHS in search phase is that r2 grows faster than r1 as n increases.Figure 4
Impact ofn on the time cost of index building (a), trapdoor generation (b), and search (c) (d=300, m=6, k=60, and n=20,40,60,80,100).
(a)(b)(c)


#### 5.2.2. Impact of the Number of Documents in a Corpus (d) on Performance

According to the analysis in Section5.1, the time cost for index building in PMSEHS, SPE-CKS, and T-PECK is linear with d, which is confirmed by the experiment result. PMSEHS costs more time for index building due to requiring more pairing operations for encrypting documents. The time consumption of T-PECK is slightly more than that of SPE-CKS in index building phase since T-PECK needs encrypt extra internal nodes. As shown in Figure 5, we can find that the time cost of trapdoor generation of these three schemes is independent with d. Moreover, Figure 5 also shows that the search complexity in SPE-CKS is linear with d while that in PMSEHS and T-PECK are both sublinear with d. The search time in T-PECK is more than that in PMSEHS, since T-PECK requires more pairing operations than PMSEHS as d increases, which is identical to our theoretical analysis.Figure 5
Impact ofd on the time cost of index building (a), trapdoor generation (b), and search (c) (n=60, m=6, k=60, and d=100,200,300,400,500).
(a)(b)(c)


#### 5.2.3. Impact of the Number of Keywords in a Query (m) on Performance

According to the analysis in Section5.1, the parameter m only impacts trapdoor generation and testing. For an index with 60 keywords (n=60), as shown in Figure 6, the time overhead of trapdoor generation in PMSEHS is linearly with Om, while that in SPE-CKS and T-PECK is independent with m. Moreover, as expected, the time consumption of search in SPE-CKS is independent with m while that in PMSEHS is linear with m. As m increases, T-PECK has better search performance than PMSEHS since the number of documents, whose “0-1” vectors match the query (r2), is reduced. So, we can say that T-PECK is more efficient than PMSEHS when m is large.Figure 6
Impact ofm on the time cost of trapdoor generation (a) and search (b) (D=300,n=60,k=60,andm=2,4,6,8,10).
(a)(b)


### 5.3. More Discussion

According to experimental results, whenn=60,d=500,andm=6, the time consumption of search in T-PECK is 41 s while that in SPE-CKS is 162 s. As compensation, the time overhead of index building in T-PECK is 460 s while that in SPE-CKS is 265 s. According to this result, we can argue that the search performance of our scheme is better than that of SPE-CKS without sacrificing the time complexity of index building. Compared with PMSEHS, when n=60,d=500,andm=6, the time cost of index building in T-PECK is 460 s while that in PMSEHS is 9538 s. Accordingly, our scheme costs twice as much search time as PMSEHS. Thus, our scheme requires much less time cost in the index building process while ensuring the sublinear search efficiency. In practice, the index building algorithm is usually performed by data owners while the search algorithm is run by the cloud server. Thus, considering that the cloud server owns much more computing and storage resources than data owner, we reckon that it is worth to sacrifice a little query efficiency to reduce time and space costs of index building and storage.To summarize, it is clear that our scheme maintains a high query efficiency without increasing the time cost of index generation too much. Considering the fact that our scheme holds a good trade-off between query and index generation, we reckon that T-PECK is practicable in applications in which data users use resource-constrained mobile devices.


## 5.1. Theoretical Analysis

The theoretical analysis of the proposed T-PECK scheme is evaluated and compared with the previous PECK schemes in terms of space and computation complexity. We choose four representative PECK schemes proposed recently for comparison. For simplicity, we denote these four PECK schemes introduced in [8, 10, 13] by SPE-CKS, SPE-SMKS, SA-SCF-PECKS, and PMSEHS, respectively. For clarity, we define three important parameters associated with these PECK schemes. The first parameter is the number of keywords in an index, denoted by n; the second one is the number of keywords in a query, denoted by m; the third one is the number of documents in a corpus, denoted by d. In addition, for PMSEHS, since the search process only accesses the documents containing the first keyword in the query, we denote the number of documents matching the first keyword in the query by r1. For T-PECK, we denote the number of keyword sets by k, and the number of documents whose “0-1” vector matches the query vector by r2 since only these documents will be verified in the search process. According to these denotations, we present Table 3 to show the comparison of time and space complexities among T-PECK and other previous PECK schemes.Table 3
Comparison with previous PECK schemes on time and space complexity.
SchemeT1T2T3S1S2SPE-CKS [8]2ndPnPndEndGnGSPE-SMKS [9]2n+4dPn+4Pn+1dP+3dEn+3dG3GT+n+1ZP∗SA-SCF-PECKS [10]2dE+n+4dPn+2P4dP+n+2dEn+2dG+dGTn+2G+ZP∗PMSEHS [13]2ndP+n2dE3mP2mr1E4ndG+n2dGT2mGT-PECK2n+2kdP+2dEn+kPnr2log2dP+3r2log2dEnd+nkG+2dGT3n+3kGDenotationG and GT are two cyclic groups of a large prime order, and e^:G×G⟶GT is a bilinear map [35]P and PT: the time cost of one exponentiation computation in G, and GT, respectivelyE: the time cost of one pairing operationZP∗, G and GT: the size of an element of ZP∗, G and GT, respectivelyT1, T2, and T3 represent the time complexity of index building, trapdoor generation, and search, respectivelyS1 and S2 represent the space complexity of index and trapdoor, respectivelyAs shown in Table3, the time complexities of search in SPE-CKS, SPE-SMKS, and SA-SCF-PECKS are all linear with d since these three schemes adopt the forward index, while that in our scheme is linear with log2d due to utilizing tree index structure. According to the tree building algorithm (Algorithm 5), we can evaluate that the search algorithm needs at most access r2∗log2d nodes in the index tree. Since the search algorithm requires the pairing operations three times for each node, T-PECK will perform pairing operations at most 3r2∗log2d times. Because d is a large number and commonly much bigger than n and r2, we can reckon that the proposed scheme is more efficient than SPE-CKS, SPE-SMKS, and SA-SCF-PECKS in the search process. In addition, because the tree index structure contains many internal nodes to accelerate the search process, the time and storage consumption of our scheme is more than that in SPE-CKS, SPE-SMKS, and SA-SCF-PECKS.Table3 also shows that the time complexity of search in PMSEHS is linear with r1 since it utilizes a hidden structure to build the index. Compared with PMSEHS, the T-PECK scheme needs less search time when r2log2d<r1. According to the definition of r1, r2, and d, we know our scheme is more efficient when the term frequency of query keywords is high and d is relatively small. Moreover, PMSEHS needs much more time and storage overhead for index generation and storage than T-PECK since the hidden structure requires many group elements of GT to speed up the query process. As shown in Table 3, the time complexity of index building and the space complexity of index storage in PMSEHS are both linear with On2 while that in T-PECK are both linear with On. Thus, we argue that our scheme can achieve a sublinear search complexity without sacrificing the index generation time and storage space.


## 5.2. Experimental Results

Based on Java Pairing-Based Cryptography (JPBC) library [36], our scheme is implemented on an environment in which the CPU is Intel (R) Core (TM) i7-4570 at 3.60 GHz and the memory size is 16 GB. A type A pair is used to realize the bilinear map in our scheme. The base field size of this pair is 128 bits, and the security level of this pair is equivalent to 1024 bits of DLOG [36]. The real-world corpus that our experiment adopts is an e-mail dataset named by Enron [37]. To quantify the efficiency of our scheme, we mainly focus on three parameters related to PECK in the experiment. These three parameters are n, d, and m mentioned in Section 5.1. To demonstrate the advantages of T-PECK, two previous PECK schemes, that is, SPE-CKS and PMSEHS, are compared with our scheme. The reason for choosing these two schemes is that SPE-CKS adopts a forward index, while PMSEHS utilizes a hidden structure. The comparison experiment involves the time overhead of index building, trapdoor generation, and search.


### 5.2.1. Impact of the Number of Keywords in a Document (n) on Performance

For a query with 6 keywords (m=6) and a corpus with 300 documents (d=300), as n increases, Figure 4 shows the following facts.(1)
The execution time of index building in PMSEHS far exceeds than that in SPE-CKS and T-PECK since PMSEHS performs lots of pairing operations for accelerating the search process. T-PECK needs more index building time than SPE-CKS since requiring encrypting internal nodes.(2)
The trapdoor generation time in PMSEHS is independent ofn and is better than other two scheme for m<n. T-PECK needs less time for trapdoor generation than SPE-CKS since it requires less time for exponentiation computation over group elements.(3)
The search complexity in SPE-CKS is linear withn while other two schemes are sublinear with n. As n increases, the search time of PMSEHS and T-PECK grows slightly due to the growth of parameters r1 and r2. In addition, the reason why T-PECK needs more time than PMSEHS in search phase is that r2 grows faster than r1 as n increases.Figure 4
Impact ofn on the time cost of index building (a), trapdoor generation (b), and search (c) (d=300, m=6, k=60, and n=20,40,60,80,100).
(a)(b)(c)


### 5.2.2. Impact of the Number of Documents in a Corpus (d) on Performance

According to the analysis in Section5.1, the time cost for index building in PMSEHS, SPE-CKS, and T-PECK is linear with d, which is confirmed by the experiment result. PMSEHS costs more time for index building due to requiring more pairing operations for encrypting documents. The time consumption of T-PECK is slightly more than that of SPE-CKS in index building phase since T-PECK needs encrypt extra internal nodes. As shown in Figure 5, we can find that the time cost of trapdoor generation of these three schemes is independent with d. Moreover, Figure 5 also shows that the search complexity in SPE-CKS is linear with d while that in PMSEHS and T-PECK are both sublinear with d. The search time in T-PECK is more than that in PMSEHS, since T-PECK requires more pairing operations than PMSEHS as d increases, which is identical to our theoretical analysis.Figure 5
Impact ofd on the time cost of index building (a), trapdoor generation (b), and search (c) (n=60, m=6, k=60, and d=100,200,300,400,500).
(a)(b)(c)


### 5.2.3. Impact of the Number of Keywords in a Query (m) on Performance

According to the analysis in Section5.1, the parameter m only impacts trapdoor generation and testing. For an index with 60 keywords (n=60), as shown in Figure 6, the time overhead of trapdoor generation in PMSEHS is linearly with Om, while that in SPE-CKS and T-PECK is independent with m. Moreover, as expected, the time consumption of search in SPE-CKS is independent with m while that in PMSEHS is linear with m. As m increases, T-PECK has better search performance than PMSEHS since the number of documents, whose “0-1” vectors match the query (r2), is reduced. So, we can say that T-PECK is more efficient than PMSEHS when m is large.Figure 6
Impact ofm on the time cost of trapdoor generation (a) and search (b) (D=300,n=60,k=60,andm=2,4,6,8,10).
(a)(b)


## 5.2.1. Impact of the Number of Keywords in a Document (n) on Performance

For a query with 6 keywords (m=6) and a corpus with 300 documents (d=300), as n increases, Figure 4 shows the following facts.(1)
The execution time of index building in PMSEHS far exceeds than that in SPE-CKS and T-PECK since PMSEHS performs lots of pairing operations for accelerating the search process. T-PECK needs more index building time than SPE-CKS since requiring encrypting internal nodes.(2)
The trapdoor generation time in PMSEHS is independent ofn and is better than other two scheme for m<n. T-PECK needs less time for trapdoor generation than SPE-CKS since it requires less time for exponentiation computation over group elements.(3)
The search complexity in SPE-CKS is linear withn while other two schemes are sublinear with n. As n increases, the search time of PMSEHS and T-PECK grows slightly due to the growth of parameters r1 and r2. In addition, the reason why T-PECK needs more time than PMSEHS in search phase is that r2 grows faster than r1 as n increases.Figure 4
Impact ofn on the time cost of index building (a), trapdoor generation (b), and search (c) (d=300, m=6, k=60, and n=20,40,60,80,100).
(a)(b)(c)


## 5.2.2. Impact of the Number of Documents in a Corpus (d) on Performance

According to the analysis in Section5.1, the time cost for index building in PMSEHS, SPE-CKS, and T-PECK is linear with d, which is confirmed by the experiment result. PMSEHS costs more time for index building due to requiring more pairing operations for encrypting documents. The time consumption of T-PECK is slightly more than that of SPE-CKS in index building phase since T-PECK needs encrypt extra internal nodes. As shown in Figure 5, we can find that the time cost of trapdoor generation of these three schemes is independent with d. Moreover, Figure 5 also shows that the search complexity in SPE-CKS is linear with d while that in PMSEHS and T-PECK are both sublinear with d. The search time in T-PECK is more than that in PMSEHS, since T-PECK requires more pairing operations than PMSEHS as d increases, which is identical to our theoretical analysis.Figure 5
Impact ofd on the time cost of index building (a), trapdoor generation (b), and search (c) (n=60, m=6, k=60, and d=100,200,300,400,500).
(a)(b)(c)


## 5.2.3. Impact of the Number of Keywords in a Query (m) on Performance

According to the analysis in Section5.1, the parameter m only impacts trapdoor generation and testing. For an index with 60 keywords (n=60), as shown in Figure 6, the time overhead of trapdoor generation in PMSEHS is linearly with Om, while that in SPE-CKS and T-PECK is independent with m. Moreover, as expected, the time consumption of search in SPE-CKS is independent with m while that in PMSEHS is linear with m. As m increases, T-PECK has better search performance than PMSEHS since the number of documents, whose “0-1” vectors match the query (r2), is reduced. So, we can say that T-PECK is more efficient than PMSEHS when m is large.Figure 6
Impact ofm on the time cost of trapdoor generation (a) and search (b) (D=300,n=60,k=60,andm=2,4,6,8,10).
(a)(b)


## 5.3. More Discussion

According to experimental results, whenn=60,d=500,andm=6, the time consumption of search in T-PECK is 41 s while that in SPE-CKS is 162 s. As compensation, the time overhead of index building in T-PECK is 460 s while that in SPE-CKS is 265 s. According to this result, we can argue that the search performance of our scheme is better than that of SPE-CKS without sacrificing the time complexity of index building. Compared with PMSEHS, when n=60,d=500,andm=6, the time cost of index building in T-PECK is 460 s while that in PMSEHS is 9538 s. Accordingly, our scheme costs twice as much search time as PMSEHS. Thus, our scheme requires much less time cost in the index building process while ensuring the sublinear search efficiency. In practice, the index building algorithm is usually performed by data owners while the search algorithm is run by the cloud server. Thus, considering that the cloud server owns much more computing and storage resources than data owner, we reckon that it is worth to sacrifice a little query efficiency to reduce time and space costs of index building and storage.To summarize, it is clear that our scheme maintains a high query efficiency without increasing the time cost of index generation too much. Considering the fact that our scheme holds a good trade-off between query and index generation, we reckon that T-PECK is practicable in applications in which data users use resource-constrained mobile devices.


## 6. Conclusion

In this paper, we proposed a novel algorithm for building an index tree. Through elaborately combining the index tree and an efficient PO-IPE scheme, we proposed a PECK scheme based on a tree-based index structure. The search efficiency in the proposed scheme is sublinear with the number of documents, and our scheme is proven to beL-semantically secure against chosen plaintext attacks.To evaluate the efficiency of T-PECK, a detailed theoretical and experimental analysis is proposed. This analysis shows that compared with previous PECK schemes, T-PECK is more practical such as requiring less time for index building and search. In real-world applications, the query of data users is usually more complex than conjunctive keyword search, such as Boolean keyword search, fuzzy search, and range search. Thus, it is necessary to build a tree-based SPE scheme supporting more expressive search function.



---

*Source: 7034944-2021-11-05.xml*