# Achieve Efficient and Privacy-Preserving Compound Substring Query over Cloud

Authors: Fan Yin; Rongxing Lu; Yandong Zheng; Xiaohu Tang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The cloud computing technique, which was initially used to mitigate the explosive growth of data, has been required to take both data privacy and users’ query functionality into consideration. Searchable symmetric encryption (SSE) is a popular solution that can support efficient attribute queries over encrypted datasets in the cloud. In particular, some SSE schemes focus on the substring query, which deals with the situation that the user only remembers the substring of the queried attribute. However, all of them just consider substring queries on a single attribute, which cannot be used to achieve compound substring queries on multiple attributes. This paper aims to address this issue by proposing an efficient and privacy-preserving SSE scheme supporting compound substring queries. In specific, we first employ the position heap technique to design a novel tree-based index to support substring queries on a single attribute and employ pseudorandom function (PRF) and fully homomorphic encryption (FHE) techniques to protect its privacy. Then, based on the homomorphism of FHE, we design a filter algorithm to calculate the intersection of search results for different attributes, which can be used to support compound substring queries on multiple attributes. Detailed security analysis shows that our proposed scheme is privacy-preserving. In addition, extensive performance evaluations are also conducted, and the results demonstrate the efficiency of our proposed scheme.


---

## Body

## 1. Introduction

The rapid development of information techniques has been promoting the explosive growth of data. In order to mitigate the local storage and computing pressure, an increasing number of individuals and organizations tend to store and process their databases in the cloud [1, 2]. However, since the cloud server may not be fully trustable, those databases with some sensitive information (e.g., electronic health records) have to be encrypted before being outsourced to the cloud. Although the encryption technique can preserve database privacy, it also hides some critical information such that the cloud server cannot well support some users’ query functionality over the encrypted database, e.g., attribute query, which returns a collection of records containing a specific queried attribute.To deal with the above challenge, the concept of searchable symmetric encryption (SSE) [3] was introduced, which enables the cloud server to search on encrypted records in a very efficient way. Over the past year, in order to improve the query efficiency of SSE, a series of secure index techniques have been designed to match the attributes to corresponding records, such as inverted index [4–7] and tree-based index [8]. Since these index techniques are built with exact attributes, the corresponding SSE schemes can only support the exact attribute query; i.e., the queried attribute must be exactly the same attribute as that stored in cloud.Recently, to solve the situation that a user only remembers a substring of an attribute rather than the exact attribute, some studies [9–11] designed SSE schemes to support substring queries. However, they just considered a substring query on a single attribute, which cannot be used to achieve a compound substring query on multiple attributes, i.e., the queried records match multiple substring queries for multiple attributes at the same time. Considering an example of the compound query that a database DB includes n records f1,f2,…,fn and each record in it has ρ attributes A1,A2,…,Aρ, a user can send a compound substring query on two attributes: select f from DB where Ajlike∗s1∗andAklike∗s2∗, to query records whose attributes Aj and Ak contain substring s1 and s2, respectively, where j and k belong to 1,ρ. A straightforward solution to support the compound query is that users query substrings separately and then calculate the intersection of results. Unfortunately, this solution is inefficient because it leads to a large number of communication overheads and computational costs for the data user.To address the above problems, in this paper, we propose a privacy-preserving SSE scheme, which can efficiently support compound substring queries on multiple attributes. In specific, the main contributions of this paper are threefold:(i)
First, based on the position heap technique, we design a tree-based index to support substring queries on a single attribute. This tree-based index can support two types of substring patterns:∗s∗ and s1∗s2, where s, s1, and s2 represent queried substrings and ∗ represents any string of any length. In addition, we employ pseudorandom functions and fully homomorphic encryption techniques to encrypt this tree-based index, which can well preserve the privacy of records.(ii)
Second, based on the homomorphism of fully homomorphic encryption, we design an algorithm (see Section 4.2.3) to calculate the intersection of search results for different attributes and therefore achieve the compound substring query on multiple attributes.(iii)
Finally, we analyze the security of our proposed scheme and conduct extensive experiments to evaluate its performance. The results show that our proposed scheme is efficient in terms of computational cost and storage overhead.The remainder of the paper is organized as follows. We formalize the system model, security model, and design goals in Section2. Then, we introduce some preliminaries including the position heap technique [12] and the security notion of substring-of-attribute query in Section 3. After that, we present our proposed scheme in Section 4, followed by security analyses and performance evaluation in Section 5 and Section 6, respectively. Some related works are discussed in Section 7. Finally, we draw our conclusions in Section 8.


## 2. Models and Design Goals

In this section, we formalize the system model, security model, and identify our design goals.


### 2.1. System Model

In our system model, we consider two entities, namely, a data user and a cloud server, as shown in Figure1.(i)
Data user: the data user has a database DB withn records f1,f2,…,fn and ρ attributes A1,A2,…,Aρ. Each record fi1≤i≤n in DB includes a unique identifier idi and a set of string-type attributes αi1,αi2,…,αiρ. Due to the limited storage space and computational capability, the data user intends to outsource the database DB and its index, i.e., I, to the cloud server. Later, the data user submits a compound substring query token Q=Ω,q1,…,qρ to the cloud server to retrieve a set of records ℱ matching Q, where qj1≤j≤ρ is a substring query for attribute Aj and Ω is a compound formula consisting of conjunctive expressions (i.e., ∩) and disjunctive expressions (i.e., ∪) on q1,…,qρ. For example, Ω=q1∩⋯∩qρ means matching records’ attribute Aj contains substring qj for 1≤j≤ρ at the same time.(ii)
Cloud server: the cloud server is considered to be powerful in storage space and computational capability. The duties of the cloud server include the following: (i) efficiently store database DB and indexI and (ii) process compound substring query token Q and respond a set of matching records ℱ⊆DB to the data user.Figure 1
System model under consideration.


### 2.2. Security Model

In our security model, the data user is considered as trusted, while the cloud server is assumed as honest-but-curious, which means that the cloud server will (i) honestly execute the query processing, return the query results without tampering it and (ii) curiously infer as much sensitive information as possible from the available data. The sensitive information could include the database DB, the indexI, and the compound substring query token Q. The formal simulated-based definition for this security model is described in Section 3.4.


### 2.3. Design Goals

In this work, our design goal is to achieve an efficient and privacy-preserving SSE scheme supporting compound substring queries for the database. In particular, the following two requirements should be achieved.(i)
Privacy Preservation. In the proposed scheme, all the data obtained by the cloud server, i.e., DB,I,Q, should be privacy-preserving during the outsourcing and query phases. Formally, the proposed scheme needs to satisfy security Definition 1 in Section 3.4.(ii)
Efficiency. In order to achieve the above privacy requirement, additional computational costs will inevitably be incurred. Therefore, in this work, we also aim to reduce the query time to be linear with the length of the query token plus the size of matching results.


## 2.1. System Model

In our system model, we consider two entities, namely, a data user and a cloud server, as shown in Figure1.(i)
Data user: the data user has a database DB withn records f1,f2,…,fn and ρ attributes A1,A2,…,Aρ. Each record fi1≤i≤n in DB includes a unique identifier idi and a set of string-type attributes αi1,αi2,…,αiρ. Due to the limited storage space and computational capability, the data user intends to outsource the database DB and its index, i.e., I, to the cloud server. Later, the data user submits a compound substring query token Q=Ω,q1,…,qρ to the cloud server to retrieve a set of records ℱ matching Q, where qj1≤j≤ρ is a substring query for attribute Aj and Ω is a compound formula consisting of conjunctive expressions (i.e., ∩) and disjunctive expressions (i.e., ∪) on q1,…,qρ. For example, Ω=q1∩⋯∩qρ means matching records’ attribute Aj contains substring qj for 1≤j≤ρ at the same time.(ii)
Cloud server: the cloud server is considered to be powerful in storage space and computational capability. The duties of the cloud server include the following: (i) efficiently store database DB and indexI and (ii) process compound substring query token Q and respond a set of matching records ℱ⊆DB to the data user.Figure 1
System model under consideration.


## 2.2. Security Model

In our security model, the data user is considered as trusted, while the cloud server is assumed as honest-but-curious, which means that the cloud server will (i) honestly execute the query processing, return the query results without tampering it and (ii) curiously infer as much sensitive information as possible from the available data. The sensitive information could include the database DB, the indexI, and the compound substring query token Q. The formal simulated-based definition for this security model is described in Section 3.4.


## 2.3. Design Goals

In this work, our design goal is to achieve an efficient and privacy-preserving SSE scheme supporting compound substring queries for the database. In particular, the following two requirements should be achieved.(i)
Privacy Preservation. In the proposed scheme, all the data obtained by the cloud server, i.e., DB,I,Q, should be privacy-preserving during the outsourcing and query phases. Formally, the proposed scheme needs to satisfy security Definition 1 in Section 3.4.(ii)
Efficiency. In order to achieve the above privacy requirement, additional computational costs will inevitably be incurred. Therefore, in this work, we also aim to reduce the query time to be linear with the length of the query token plus the size of matching results.


## 3. Preliminary

In this section, we give some preliminaries including position heap [12], symmetric key encryption scheme, fully homomorphic encryption, and the security definition of our proposed scheme, which will serve as the basis of our proposed scheme.


### 3.1. The (Original) Position Heap Technique

Intuitively speaking, the (original) position heapPt is a trie built from all the suffixes of t and can be used to achieve efficient substring search for t. To construct the position heap Pt from a string t=c1c2…cp, a set of suffixes ti:p=ci…cpi∈p,…,1 are chosen and inserted to the Pt, which is initialized as a root node. To do this, for each suffix ti:pi∈p,…,1, its longest prefix ti:ji≤j≤p that is already represented by a path in Pt is found and a new leaf child is added to the last node of this path. The new leaf child is labeled with i and its edge is labeled with tj+1 (see Figure 2). Compared to other data structures to achieve substring search, such as suffix tree [9] and suffix array [13], the position heap [12] can achieve high efficiency in both storage and query time.Figure 2
An example of building position heapPt for string t=bbabbbaaba. The solid edges in Pt reflect the insertion for suffix t1:10.In the following, we formally describe thePHBuild and PHSearch algorithms of the position heap, which will be used to build a position heap and search on it. Note that we consider each node in the position heap stores two types of data: edge and pos, which present the label of the node’s edge and the label of the node, respectively.


#### 3.1.1.PHBuild Algorithm

Given a stringt=c1c2…cp, the PHBuild (i.e., Algorithm 1) visits the t from the right to left and inserts each position i∈p,p−1,…,1 to the position heap Pt. In particular, for each position i, the algorithm first finds the longest path from the root node of Pt, where its path label is a prefix of ci…cm (lines 4–7). Assume that the last node of this longest path is N. Then, the algorithm appends a new leaf child N′ to the N, where N′⋅edge=cj+1 and N′⋅pos=i (lines 8–11). Figure 2 depicts an example to build such a position heap for a string t=bbabbbaaba. During inserting position i=1, this algorithm first finds the longest path (shown in bold) in Pt and appends a new leaf child N′ to the last node of this path, where N′⋅edge=a and N′⋅pos=1.Algorithm 1: Build a position heap Pt for the string t=c1c2…cp.
(1)
initialize a root nodeR as the position heap Pt, where R⋅edge=Null and R⋅pos=Null;(2)
for each i in p,p−1,…,1do(3)
N=R;(4)
for each j in i,i+1,…,pdo(5)
find the childN′ of N, where N′.edge=cj;(6)
ifN′ does exist then(7)
N=N′(8)
else(9)
insert a new child nodeN′ for the N;(10)
N′⋅edge=cj,N′⋅pos=i;(11)
break;(12)
end if(13)
end for(14)
end for(15)
returnPt;


#### 3.1.2.PHSearch Algorithm

Given a substrings and a position heap Pt, the PHSearch (i.e., Algorithm 2) is supposed to find all the positions in t that are occurrences of s. The time complexity of this algorithm is Os2+dr, where s is the length of the queried substring and dr is the number of matching occurrences. The details are as follows:(i)
The algorithm first finds the longest path from the root node ofPt, where its path label denoted by s′ is a prefix of s. We refer to this longest path as a search path in the rest of the article. Then, the algorithm lets L1 be the set of positions stored in the intermediate nodes along the search path and L2 be the set of positions stored in the descendants of the last node of the search path (lines 3–18). In particular, if s′≠s, the position stored in the last node of the search path is included in L1. Otherwise, it is included in L2.(ii)
After completing the previous step, elements inL2 must be the matching positions, and elements in L1 may or may not be the matching positions. Next, the algorithm reviews each position i∈L1 in the string t to filter out unmatching positions and removes them from the L1. Finally, this algorithm returns L1∪L2 (lines 19–23).Algorithm 2: Search substring s in a position heap Pt, where s=h1h2…hl and t=c1c2…cp.
(1)
initial empty setsL1 and L2;(2)
letN be the root node of the Pt;(3)
for each i in 1,2,…,ldo(4)
find the childN′ of N, where N′⋅edge=hi;(5)
ifN′ does exist then(6)
ifi=lthen(7)
L2⋅addN′⋅pos;(8)
for each descendant X of N′do(9)
L2⋅addX⋅pos;(10)
end for(11)
else(12)
L1⋅addN′⋅pos;(13)
end if(14)
N=N′;(15)
else(16)
break;(17)
end if(18)
end for(19)
for each i in L1do(20)
ifcici+1…ci+l−1 is not equal to h1h2…hlthen(21)
L1⋅removei;(22)
end if(23)
end for(24)
returnL1∪L2;Take an example with Figure2. Given a substring s=bb, the PHSearch algorithm first finds the search path labeled with bb. In this way, L1 and L2 are equal to 9 and 5,1,4. Then, this algorithm reviews the string t and makes sure i=9∈L1 is not an occurrence of s. Therefore, position 9 is removed from L1, and L1 is an empty set now. Finally, this algorithm returns all the positions in L1∪L2=5,1,4.


### 3.2. Symmetric Key Encryption Scheme

A symmetric key encryption scheme (SKE) consists of the following three polynomial-time algorithmsKeyGen,Enc,Dec.(i)
K←KeyGen1λ: it takes a security parameter λ as input and outputs a secret key K(ii)
C←EncK,M: it takes a key K and a message M as inputs and then outputs a ciphertext C(iii)
M←DecK,C: it takes a key K and a ciphertext C as inputs and then outputs M


#### 3.2.1. Correctness

For any messageM in plaintext space, it holds that DecK,EncK,M=M.


#### 3.2.2. Security

In this paper, we consider that the SKE is indistinguishable under a chosen-plaintext attack (IND-CPA) [14], which guarantees that the ciphertext does not leak any information about the plaintext even an adversary can query an encryption oracle. We note that common private-key encryption schemes such as AES in counter mode satisfy this definition.


### 3.3. (Leveled) Fully Homomorphic Encryption

A leveled fully homomorphic encryption (FHE) scheme [15] consists of four polynomial-time algorithms KeyGen,Enc,Dec,Eval. The details are described as follows:(i)
pk,sk←KeyGen1λ,L: it takes a security parameter λ and a maximum multiplicative depth L as inputs and outputs a public key pk and a secret key sk. We assume that a public key pk specifies both the plaintext space P and the ciphertext space C.(ii)
m¯←Encpk,m: given the public key pk and a plaintext m, it outputs a ciphertext m¯. For simplicity, we omit the randomness used for encryption.(iii)
m←Decsk,m¯: given the secret key sk and a ciphertext m¯, it outputs a message m. m¯ϕ←Evalpk,ϕ,m¯1,…,m¯l. It takes the public key pk, a function ϕ:Pl⟶P, and a set of ciphertexts m¯1,…,m¯l as inputs and outputs a ciphertext m¯ϕ.


#### 3.3.1. Correctness

For anymi∈P1≤i≤l and any function ϕ:Pl⟶P which can be evaluated by a circuit with depth at most L, if pk,sk←KenGen1λ, m¯←Encpk,mi, and m¯ϕ←Evalpk,ϕ,m¯1,…,m¯l, then it holds that Decsk,m¯ϕ=ϕm1,…,ml.


#### 3.3.2. Security

In this work, we consider an FHE scheme is indistinguishable under a chosen-plaintext attack (IND-CPA), which is described in [15].


#### 3.3.3. Homomorphic Operations

In general, an FHE scheme can directly support homomorphic bitwise addition+ and multiplication ⋅. Other advanced homomorphic operations can be realized by arithmetic circuits based on ⋅ and +. In this paper, we consider three types of advanced homomorphic operations: bitwise AND, bitwise OR, and integer equality. In specific, if the FHE ciphertexts of two μ-bit integers x=xμ−1…x0 and y=yμ−1…y0 are x¯=x0¯,…,xμ−1¯ and y¯=y0¯,…,yμ−1¯, these arithmetic circuits are defined as follows:(i)
Bitwise AND&: x¯&y¯=s0,…,sμ−1, where si=xi¯⋅yi¯ for i∈0,μ−1.(ii)
Bitwise OR|: x¯|y¯=s0,…,sμ−1, where si=xi¯+yi¯+xi¯⋅yi¯ for i∈0,μ−1.(iii)
Integer equality:EQx¯,y¯=∏i=0μ−11+xi¯+yi¯. The output of EQx¯,y¯ is 1¯ in the case of x=y and 0¯ otherwise, where 1¯ and 0¯ are FHE ciphertexts of 1-bit message 1 and 0, respectively.


### 3.4. Security Definition of Our Proposed Scheme

In this section, we follow the security definition in [5] to formalize the simulated-based security definition of our proposed scheme by using the following two experiments: RealA,Cλ and IdealA,Sλ. In the former, the adversary A, who represents the cloud server, executes the proposed scheme with a challenger C that represents the data user. In the latter, A also executes the proposed scheme with a simulator S that simulates the output of the challenger C through the leakage of the proposed scheme. The leakage is parameterized by a leakage function collection ℒ=ℒO,ℒQ, which describes the information leaked to the adversary A in the data outsourcing phase and query phase, respectively. If any polynomial adversary A cannot distinguish the output information between the challenger C and the simulator S, then we can say there is no other information leaked to the adversary A, i.e., the cloud server, except the information that can be inferred from the ℒ. More formally,(i)
RealA,C1λ=b∈0,1: given a database DB chosen by the adversary A, the challenger C outputs encrypted index I by following the data outsourcing phase of the proposed scheme. Then, A can adaptively send a polynomial number of compound substring query tokens to the C, which outputs corresponding encrypted compound substring query tokens. Eventually, A returns a bit b as the output of this experiment.(ii)
IdealA,S1λ=b∈0,1: given the leakage function ℒO, the simulator outputs simulated encrypted index I′ and simulated encrypted database DB′. Then, for each query token, the adversary A sends its leakage function ℒQ to the simulator S, which generates the corresponding simulated encrypted compound substring query token. Eventually, A returns a bit b as the output of this experiment.Definition 1.
Our proposed scheme isℒ-secure against adaptive attacks (i.e., ℒ-adaptively secure) if, for any probabilistic polynomial-time adversary A, there exists an efficient simulator S such that PrRealA,C1λ⟶1−PrIdealA,S1λ⟶1≤neglλ.


## 3.1. The (Original) Position Heap Technique

Intuitively speaking, the (original) position heapPt is a trie built from all the suffixes of t and can be used to achieve efficient substring search for t. To construct the position heap Pt from a string t=c1c2…cp, a set of suffixes ti:p=ci…cpi∈p,…,1 are chosen and inserted to the Pt, which is initialized as a root node. To do this, for each suffix ti:pi∈p,…,1, its longest prefix ti:ji≤j≤p that is already represented by a path in Pt is found and a new leaf child is added to the last node of this path. The new leaf child is labeled with i and its edge is labeled with tj+1 (see Figure 2). Compared to other data structures to achieve substring search, such as suffix tree [9] and suffix array [13], the position heap [12] can achieve high efficiency in both storage and query time.Figure 2
An example of building position heapPt for string t=bbabbbaaba. The solid edges in Pt reflect the insertion for suffix t1:10.In the following, we formally describe thePHBuild and PHSearch algorithms of the position heap, which will be used to build a position heap and search on it. Note that we consider each node in the position heap stores two types of data: edge and pos, which present the label of the node’s edge and the label of the node, respectively.


### 3.1.1.PHBuild Algorithm

Given a stringt=c1c2…cp, the PHBuild (i.e., Algorithm 1) visits the t from the right to left and inserts each position i∈p,p−1,…,1 to the position heap Pt. In particular, for each position i, the algorithm first finds the longest path from the root node of Pt, where its path label is a prefix of ci…cm (lines 4–7). Assume that the last node of this longest path is N. Then, the algorithm appends a new leaf child N′ to the N, where N′⋅edge=cj+1 and N′⋅pos=i (lines 8–11). Figure 2 depicts an example to build such a position heap for a string t=bbabbbaaba. During inserting position i=1, this algorithm first finds the longest path (shown in bold) in Pt and appends a new leaf child N′ to the last node of this path, where N′⋅edge=a and N′⋅pos=1.Algorithm 1: Build a position heap Pt for the string t=c1c2…cp.
(1)
initialize a root nodeR as the position heap Pt, where R⋅edge=Null and R⋅pos=Null;(2)
for each i in p,p−1,…,1do(3)
N=R;(4)
for each j in i,i+1,…,pdo(5)
find the childN′ of N, where N′.edge=cj;(6)
ifN′ does exist then(7)
N=N′(8)
else(9)
insert a new child nodeN′ for the N;(10)
N′⋅edge=cj,N′⋅pos=i;(11)
break;(12)
end if(13)
end for(14)
end for(15)
returnPt;


### 3.1.2.PHSearch Algorithm

Given a substrings and a position heap Pt, the PHSearch (i.e., Algorithm 2) is supposed to find all the positions in t that are occurrences of s. The time complexity of this algorithm is Os2+dr, where s is the length of the queried substring and dr is the number of matching occurrences. The details are as follows:(i)
The algorithm first finds the longest path from the root node ofPt, where its path label denoted by s′ is a prefix of s. We refer to this longest path as a search path in the rest of the article. Then, the algorithm lets L1 be the set of positions stored in the intermediate nodes along the search path and L2 be the set of positions stored in the descendants of the last node of the search path (lines 3–18). In particular, if s′≠s, the position stored in the last node of the search path is included in L1. Otherwise, it is included in L2.(ii)
After completing the previous step, elements inL2 must be the matching positions, and elements in L1 may or may not be the matching positions. Next, the algorithm reviews each position i∈L1 in the string t to filter out unmatching positions and removes them from the L1. Finally, this algorithm returns L1∪L2 (lines 19–23).Algorithm 2: Search substring s in a position heap Pt, where s=h1h2…hl and t=c1c2…cp.
(1)
initial empty setsL1 and L2;(2)
letN be the root node of the Pt;(3)
for each i in 1,2,…,ldo(4)
find the childN′ of N, where N′⋅edge=hi;(5)
ifN′ does exist then(6)
ifi=lthen(7)
L2⋅addN′⋅pos;(8)
for each descendant X of N′do(9)
L2⋅addX⋅pos;(10)
end for(11)
else(12)
L1⋅addN′⋅pos;(13)
end if(14)
N=N′;(15)
else(16)
break;(17)
end if(18)
end for(19)
for each i in L1do(20)
ifcici+1…ci+l−1 is not equal to h1h2…hlthen(21)
L1⋅removei;(22)
end if(23)
end for(24)
returnL1∪L2;Take an example with Figure2. Given a substring s=bb, the PHSearch algorithm first finds the search path labeled with bb. In this way, L1 and L2 are equal to 9 and 5,1,4. Then, this algorithm reviews the string t and makes sure i=9∈L1 is not an occurrence of s. Therefore, position 9 is removed from L1, and L1 is an empty set now. Finally, this algorithm returns all the positions in L1∪L2=5,1,4.


## 3.1.1.PHBuild Algorithm

Given a stringt=c1c2…cp, the PHBuild (i.e., Algorithm 1) visits the t from the right to left and inserts each position i∈p,p−1,…,1 to the position heap Pt. In particular, for each position i, the algorithm first finds the longest path from the root node of Pt, where its path label is a prefix of ci…cm (lines 4–7). Assume that the last node of this longest path is N. Then, the algorithm appends a new leaf child N′ to the N, where N′⋅edge=cj+1 and N′⋅pos=i (lines 8–11). Figure 2 depicts an example to build such a position heap for a string t=bbabbbaaba. During inserting position i=1, this algorithm first finds the longest path (shown in bold) in Pt and appends a new leaf child N′ to the last node of this path, where N′⋅edge=a and N′⋅pos=1.Algorithm 1: Build a position heap Pt for the string t=c1c2…cp.
(1)
initialize a root nodeR as the position heap Pt, where R⋅edge=Null and R⋅pos=Null;(2)
for each i in p,p−1,…,1do(3)
N=R;(4)
for each j in i,i+1,…,pdo(5)
find the childN′ of N, where N′.edge=cj;(6)
ifN′ does exist then(7)
N=N′(8)
else(9)
insert a new child nodeN′ for the N;(10)
N′⋅edge=cj,N′⋅pos=i;(11)
break;(12)
end if(13)
end for(14)
end for(15)
returnPt;


## 3.1.2.PHSearch Algorithm

Given a substrings and a position heap Pt, the PHSearch (i.e., Algorithm 2) is supposed to find all the positions in t that are occurrences of s. The time complexity of this algorithm is Os2+dr, where s is the length of the queried substring and dr is the number of matching occurrences. The details are as follows:(i)
The algorithm first finds the longest path from the root node ofPt, where its path label denoted by s′ is a prefix of s. We refer to this longest path as a search path in the rest of the article. Then, the algorithm lets L1 be the set of positions stored in the intermediate nodes along the search path and L2 be the set of positions stored in the descendants of the last node of the search path (lines 3–18). In particular, if s′≠s, the position stored in the last node of the search path is included in L1. Otherwise, it is included in L2.(ii)
After completing the previous step, elements inL2 must be the matching positions, and elements in L1 may or may not be the matching positions. Next, the algorithm reviews each position i∈L1 in the string t to filter out unmatching positions and removes them from the L1. Finally, this algorithm returns L1∪L2 (lines 19–23).Algorithm 2: Search substring s in a position heap Pt, where s=h1h2…hl and t=c1c2…cp.
(1)
initial empty setsL1 and L2;(2)
letN be the root node of the Pt;(3)
for each i in 1,2,…,ldo(4)
find the childN′ of N, where N′⋅edge=hi;(5)
ifN′ does exist then(6)
ifi=lthen(7)
L2⋅addN′⋅pos;(8)
for each descendant X of N′do(9)
L2⋅addX⋅pos;(10)
end for(11)
else(12)
L1⋅addN′⋅pos;(13)
end if(14)
N=N′;(15)
else(16)
break;(17)
end if(18)
end for(19)
for each i in L1do(20)
ifcici+1…ci+l−1 is not equal to h1h2…hlthen(21)
L1⋅removei;(22)
end if(23)
end for(24)
returnL1∪L2;Take an example with Figure2. Given a substring s=bb, the PHSearch algorithm first finds the search path labeled with bb. In this way, L1 and L2 are equal to 9 and 5,1,4. Then, this algorithm reviews the string t and makes sure i=9∈L1 is not an occurrence of s. Therefore, position 9 is removed from L1, and L1 is an empty set now. Finally, this algorithm returns all the positions in L1∪L2=5,1,4.


## 3.2. Symmetric Key Encryption Scheme

A symmetric key encryption scheme (SKE) consists of the following three polynomial-time algorithmsKeyGen,Enc,Dec.(i)
K←KeyGen1λ: it takes a security parameter λ as input and outputs a secret key K(ii)
C←EncK,M: it takes a key K and a message M as inputs and then outputs a ciphertext C(iii)
M←DecK,C: it takes a key K and a ciphertext C as inputs and then outputs M


### 3.2.1. Correctness

For any messageM in plaintext space, it holds that DecK,EncK,M=M.


### 3.2.2. Security

In this paper, we consider that the SKE is indistinguishable under a chosen-plaintext attack (IND-CPA) [14], which guarantees that the ciphertext does not leak any information about the plaintext even an adversary can query an encryption oracle. We note that common private-key encryption schemes such as AES in counter mode satisfy this definition.


## 3.2.1. Correctness

For any messageM in plaintext space, it holds that DecK,EncK,M=M.


## 3.2.2. Security

In this paper, we consider that the SKE is indistinguishable under a chosen-plaintext attack (IND-CPA) [14], which guarantees that the ciphertext does not leak any information about the plaintext even an adversary can query an encryption oracle. We note that common private-key encryption schemes such as AES in counter mode satisfy this definition.


## 3.3. (Leveled) Fully Homomorphic Encryption

A leveled fully homomorphic encryption (FHE) scheme [15] consists of four polynomial-time algorithms KeyGen,Enc,Dec,Eval. The details are described as follows:(i)
pk,sk←KeyGen1λ,L: it takes a security parameter λ and a maximum multiplicative depth L as inputs and outputs a public key pk and a secret key sk. We assume that a public key pk specifies both the plaintext space P and the ciphertext space C.(ii)
m¯←Encpk,m: given the public key pk and a plaintext m, it outputs a ciphertext m¯. For simplicity, we omit the randomness used for encryption.(iii)
m←Decsk,m¯: given the secret key sk and a ciphertext m¯, it outputs a message m. m¯ϕ←Evalpk,ϕ,m¯1,…,m¯l. It takes the public key pk, a function ϕ:Pl⟶P, and a set of ciphertexts m¯1,…,m¯l as inputs and outputs a ciphertext m¯ϕ.


### 3.3.1. Correctness

For anymi∈P1≤i≤l and any function ϕ:Pl⟶P which can be evaluated by a circuit with depth at most L, if pk,sk←KenGen1λ, m¯←Encpk,mi, and m¯ϕ←Evalpk,ϕ,m¯1,…,m¯l, then it holds that Decsk,m¯ϕ=ϕm1,…,ml.


### 3.3.2. Security

In this work, we consider an FHE scheme is indistinguishable under a chosen-plaintext attack (IND-CPA), which is described in [15].


### 3.3.3. Homomorphic Operations

In general, an FHE scheme can directly support homomorphic bitwise addition+ and multiplication ⋅. Other advanced homomorphic operations can be realized by arithmetic circuits based on ⋅ and +. In this paper, we consider three types of advanced homomorphic operations: bitwise AND, bitwise OR, and integer equality. In specific, if the FHE ciphertexts of two μ-bit integers x=xμ−1…x0 and y=yμ−1…y0 are x¯=x0¯,…,xμ−1¯ and y¯=y0¯,…,yμ−1¯, these arithmetic circuits are defined as follows:(i)
Bitwise AND&: x¯&y¯=s0,…,sμ−1, where si=xi¯⋅yi¯ for i∈0,μ−1.(ii)
Bitwise OR|: x¯|y¯=s0,…,sμ−1, where si=xi¯+yi¯+xi¯⋅yi¯ for i∈0,μ−1.(iii)
Integer equality:EQx¯,y¯=∏i=0μ−11+xi¯+yi¯. The output of EQx¯,y¯ is 1¯ in the case of x=y and 0¯ otherwise, where 1¯ and 0¯ are FHE ciphertexts of 1-bit message 1 and 0, respectively.


## 3.3.1. Correctness

For anymi∈P1≤i≤l and any function ϕ:Pl⟶P which can be evaluated by a circuit with depth at most L, if pk,sk←KenGen1λ, m¯←Encpk,mi, and m¯ϕ←Evalpk,ϕ,m¯1,…,m¯l, then it holds that Decsk,m¯ϕ=ϕm1,…,ml.


## 3.3.2. Security

In this work, we consider an FHE scheme is indistinguishable under a chosen-plaintext attack (IND-CPA), which is described in [15].


## 3.3.3. Homomorphic Operations

In general, an FHE scheme can directly support homomorphic bitwise addition+ and multiplication ⋅. Other advanced homomorphic operations can be realized by arithmetic circuits based on ⋅ and +. In this paper, we consider three types of advanced homomorphic operations: bitwise AND, bitwise OR, and integer equality. In specific, if the FHE ciphertexts of two μ-bit integers x=xμ−1…x0 and y=yμ−1…y0 are x¯=x0¯,…,xμ−1¯ and y¯=y0¯,…,yμ−1¯, these arithmetic circuits are defined as follows:(i)
Bitwise AND&: x¯&y¯=s0,…,sμ−1, where si=xi¯⋅yi¯ for i∈0,μ−1.(ii)
Bitwise OR|: x¯|y¯=s0,…,sμ−1, where si=xi¯+yi¯+xi¯⋅yi¯ for i∈0,μ−1.(iii)
Integer equality:EQx¯,y¯=∏i=0μ−11+xi¯+yi¯. The output of EQx¯,y¯ is 1¯ in the case of x=y and 0¯ otherwise, where 1¯ and 0¯ are FHE ciphertexts of 1-bit message 1 and 0, respectively.


## 3.4. Security Definition of Our Proposed Scheme

In this section, we follow the security definition in [5] to formalize the simulated-based security definition of our proposed scheme by using the following two experiments: RealA,Cλ and IdealA,Sλ. In the former, the adversary A, who represents the cloud server, executes the proposed scheme with a challenger C that represents the data user. In the latter, A also executes the proposed scheme with a simulator S that simulates the output of the challenger C through the leakage of the proposed scheme. The leakage is parameterized by a leakage function collection ℒ=ℒO,ℒQ, which describes the information leaked to the adversary A in the data outsourcing phase and query phase, respectively. If any polynomial adversary A cannot distinguish the output information between the challenger C and the simulator S, then we can say there is no other information leaked to the adversary A, i.e., the cloud server, except the information that can be inferred from the ℒ. More formally,(i)
RealA,C1λ=b∈0,1: given a database DB chosen by the adversary A, the challenger C outputs encrypted index I by following the data outsourcing phase of the proposed scheme. Then, A can adaptively send a polynomial number of compound substring query tokens to the C, which outputs corresponding encrypted compound substring query tokens. Eventually, A returns a bit b as the output of this experiment.(ii)
IdealA,S1λ=b∈0,1: given the leakage function ℒO, the simulator outputs simulated encrypted index I′ and simulated encrypted database DB′. Then, for each query token, the adversary A sends its leakage function ℒQ to the simulator S, which generates the corresponding simulated encrypted compound substring query token. Eventually, A returns a bit b as the output of this experiment.Definition 1.
Our proposed scheme isℒ-secure against adaptive attacks (i.e., ℒ-adaptively secure) if, for any probabilistic polynomial-time adversary A, there exists an efficient simulator S such that PrRealA,C1λ⟶1−PrIdealA,S1λ⟶1≤neglλ.


## 4. Our Proposed Scheme

In this section, we will present our SSE scheme. Before delving into the details, we first introduce our basic index structure, which is the basic building block of our proposed scheme.


### 4.1. Basic Index Structure

In order to process efficient compound substring queries, we build an indexIAj for each attribute Aj1≤j≤ρ in database DB. The index IAj is a modified position heap and can support two types of substring patterns: ∗s∗ and s1∗s2. Next, we introduce algorithm Index Build and Index Search, which are used to build index IAj and search on it.


#### 4.1.1.Index Build Algorithm

Given an attribute columnAj=α1j,α2j,…,αnj of database DB, the IndexBuild algorithm outputs an index IAj as follows. It first transforms Aj to a string tAj=α1j#α2j#⋯#αnj, where # denotes a character that does not appear in Aj. In the rest of this paper, we call tAj attribute string. Then, it follows PHBuild algorithm to insert all the positions in tAj, except positions of character #, to a position heap PtAj. Finally, this algorithm builds an index IAj from PtAj by replacing its nodes’ position data (i.e., pos) to corresponding identifiers (i.e., id).Figure3 gives an example of building an index IA1 for the first attribute column of database DB.Figure 3
An example of building an indexIA1. (a) A1 is the first attribute column of database DB, where α11=bbab, α21=bba, and α31=aba. (b) To get attribute string tA1, concatenate all the attributes in A1 with character #. (c) Build a position heap PtA1 for tA1. (d) For each node N in PtA1, replace its N⋅pos with the corresponding identifier, called N⋅id.


#### 4.1.2.Index Search Algorithm

Given a substrings and an index IAj, the Index Search algorithm follows the PHSearch algorithm to search and outputs a set of identifiers.


### 4.2. Description of Our Proposed Scheme

In this subsection, we will describe our proposed scheme, which mainly consists of three phases: (i) system initialization; (ii) data outsourcing; (iii) compound substring query. To make the description simple, we first introduce a basic scheme which only supports substring query with∗s∗ pattern, and then extend it to support substring query with s1∗s2 pattern.


#### 4.2.1. System Initialization

Given a security parameterλ, the data user first initializes a pseudorandom function (PRF) H:0,1λ×0,1∗⟶0,1λ, an IND-CPA secure SKE Π=KeyGen,Enc,Dec, and an IND-CPA secure FHE ∑=KeyGen,Enc,Dec,Eval. Then, the data user generates keys k1←R0,1λ, k2=Π⋅KeyGen1λ, and pk,sk=∑⋅KeyGen1λ.


#### 4.2.2. Data Outsourcing

Assume that the data user has a database DB withn records f1,f2,…,fn, where each record fi1≤i≤n includes ρ string-type attributes αi1,αi2,…,αiρ. Then, the data user generates a secure index I and an encrypted database as the following steps:Step 1: the data user first uses theIndex Build algorithm to build IAj1≤j≤ρ for each attribute Aj and then encrypts it as follows:(i)
For each nodeN (except the root), the data user encrypts its N⋅id to N⋅id¯=∑⋅Encpk,N⋅id(ii)
For each nodeN (except the root), the data user concatenates all the edge labels, i.e., N⋅edge, along the path from the root to this node, and calculates the PRF output of the concatenation through pseudorandom function Hk1,∗Consider the example in Figure4, which is encrypted from the index IA1 in Figure 3(d).Step 2: the data user encrypts each recordfj∈DB through Π⋅Enck2,∗ and sends these encrypted records to the cloud server with an encrypted index I=IA1,IA2,…,IAρ.Figure 4
An example of the encrypted indexIA1, which is encrypted from Figure 3(d).


#### 4.2.3. Compound Substring Query

Given a set of substringsS=s1,…,sρ and a compound formula Ω on S, where Ω consists of conjunctive expressions (i.e., ∩) and disjunctive expressions (i.e., ∪), the data user launches a compound substring query with the cloud server as follows:Step 1: for each substringsj=c1c2…cl with 1≤j≤ρ, the data user calculates qj=Hk1,c1,Hk1,c1c2,…,Hk1,c1…cl and sends a compound substring query token Q=Ω,q1,…,qρ to the cloud server.Step 2: for eachqj∈Q, the cloud server performs algorithm Index Search to search over IAj and outputs a set Rj=idj1¯,…,idjRj¯.Step 3: the cloud server generates a functionϕ:0,1ρ⟶0,1 according to the compound formula Ω. In specific, all the ∩ and ∪ in Ω are replaced by bitwise AND & and bitwise OR |, respectively. For example, if compound formula Ω=q1∪q2∩⋯∩qρ, then ϕ=t1|t2&…&tρ, where tj∈0,1 for j∈0,ρ.Step 4: the cloud server performs Algorithm3 to filter matching elements in R1,…,Rρ according to function ϕ. In specific, assuming that Rmin is the minimum-size element in R1,…,Rρ, for each encrypted identifier id¯ in Rmin, this algorithm traverses all encrypted identifiers in R1,…,Rρ\Rmin to calculate an encrypted flag t¯∈0¯,1¯, which is 1¯ if id matches the compound formula Ω and 0¯ otherwise. Then, the cloud server inserts all the id¯,t¯ to an empty set ℱ and returns it to the data user. Figure 5 depicts an example of this step where the compound formula Ω=q1∩q2∩q3. In this example, id1 is the only identifier that matches the formula Ω. Note that, since an EQ algorithm consumes logμ multiplicative depth and an AND/OR operation consumes 1 multiplicative depth, this step requires at most ⌈logμ⌉+⌈lognμ−1⌉+⌈logρ−1⌉ multiplicative depth, where μ is the average attribute length of database and n is the number of records in the database.Step 5: for eachid¯,t¯∈ℱ, the data user calculates t=∑⋅Decsk,t¯. If t=1, then the data user calculates id=∑⋅Decsk,id¯ and requests a corresponding encrypted record from the cloud server.Algorithm 3: Filter elements in R1,…,Rρ according to function ϕ.
(1)
letRmin be the minimum-size element in R1,…,Rρ.(2)
letℱ be an empty set.(3)
for each id¯∈Rmindo(4)
tmin¯←1¯(5)
for each j∈1,…,ρ/mindo(6)
tj¯←0¯(7)
for each id′¯∈Rjdo(8)
tj′¯←EQid¯,id′¯(9)
tj¯=tj¯|tj′¯(10)
end for(11)
end for(12)
t¯←∑⋅Evalpk,ϕ,t1¯,…,tρ¯(13)
insertid¯,t¯ to ℱ;(14)
end for(15)
returnℱFigure 5
An example of Algorithm3, where the number of attributes ρ=3 and the compound formula Ω=q1∩q2∩q3.


#### 4.2.4. Query withs1∗s2 Substring

We extend our scheme to support substring queries withs1∗s2 pattern. The extension is very simple, which only makes some small changes in the processes of the outsourcing phase and compound substring query phase. In specific, when the data user builds index IAj for the attribute column Aj=α1j,α2j,…,αnj, the attribute string tAj=α1j#α2j#⋯#αnj is replaced by tAj=α1j_α1j#α2j_α2j#⋯#αnj_αnj. In other words, each attribute in Aj is copied once and concatenated to its replica with character _, and every two adjacent attributes in Aj are concatenated with character #, where _ and # denote two separate characters that do not appear in Aj. In this way, the substring query with s1∗s2 pattern can be transferred to ∗s∗ pattern where s=s2_s1. Meanwhile, this method leads to double the storage cost of index IAj since the size of the attribute string tAj is twice longer than before.


## 4.1. Basic Index Structure

In order to process efficient compound substring queries, we build an indexIAj for each attribute Aj1≤j≤ρ in database DB. The index IAj is a modified position heap and can support two types of substring patterns: ∗s∗ and s1∗s2. Next, we introduce algorithm Index Build and Index Search, which are used to build index IAj and search on it.


### 4.1.1.Index Build Algorithm

Given an attribute columnAj=α1j,α2j,…,αnj of database DB, the IndexBuild algorithm outputs an index IAj as follows. It first transforms Aj to a string tAj=α1j#α2j#⋯#αnj, where # denotes a character that does not appear in Aj. In the rest of this paper, we call tAj attribute string. Then, it follows PHBuild algorithm to insert all the positions in tAj, except positions of character #, to a position heap PtAj. Finally, this algorithm builds an index IAj from PtAj by replacing its nodes’ position data (i.e., pos) to corresponding identifiers (i.e., id).Figure3 gives an example of building an index IA1 for the first attribute column of database DB.Figure 3
An example of building an indexIA1. (a) A1 is the first attribute column of database DB, where α11=bbab, α21=bba, and α31=aba. (b) To get attribute string tA1, concatenate all the attributes in A1 with character #. (c) Build a position heap PtA1 for tA1. (d) For each node N in PtA1, replace its N⋅pos with the corresponding identifier, called N⋅id.


### 4.1.2.Index Search Algorithm

Given a substrings and an index IAj, the Index Search algorithm follows the PHSearch algorithm to search and outputs a set of identifiers.


## 4.1.1.Index Build Algorithm

Given an attribute columnAj=α1j,α2j,…,αnj of database DB, the IndexBuild algorithm outputs an index IAj as follows. It first transforms Aj to a string tAj=α1j#α2j#⋯#αnj, where # denotes a character that does not appear in Aj. In the rest of this paper, we call tAj attribute string. Then, it follows PHBuild algorithm to insert all the positions in tAj, except positions of character #, to a position heap PtAj. Finally, this algorithm builds an index IAj from PtAj by replacing its nodes’ position data (i.e., pos) to corresponding identifiers (i.e., id).Figure3 gives an example of building an index IA1 for the first attribute column of database DB.Figure 3
An example of building an indexIA1. (a) A1 is the first attribute column of database DB, where α11=bbab, α21=bba, and α31=aba. (b) To get attribute string tA1, concatenate all the attributes in A1 with character #. (c) Build a position heap PtA1 for tA1. (d) For each node N in PtA1, replace its N⋅pos with the corresponding identifier, called N⋅id.


## 4.1.2.Index Search Algorithm

Given a substrings and an index IAj, the Index Search algorithm follows the PHSearch algorithm to search and outputs a set of identifiers.


## 4.2. Description of Our Proposed Scheme

In this subsection, we will describe our proposed scheme, which mainly consists of three phases: (i) system initialization; (ii) data outsourcing; (iii) compound substring query. To make the description simple, we first introduce a basic scheme which only supports substring query with∗s∗ pattern, and then extend it to support substring query with s1∗s2 pattern.


### 4.2.1. System Initialization

Given a security parameterλ, the data user first initializes a pseudorandom function (PRF) H:0,1λ×0,1∗⟶0,1λ, an IND-CPA secure SKE Π=KeyGen,Enc,Dec, and an IND-CPA secure FHE ∑=KeyGen,Enc,Dec,Eval. Then, the data user generates keys k1←R0,1λ, k2=Π⋅KeyGen1λ, and pk,sk=∑⋅KeyGen1λ.


### 4.2.2. Data Outsourcing

Assume that the data user has a database DB withn records f1,f2,…,fn, where each record fi1≤i≤n includes ρ string-type attributes αi1,αi2,…,αiρ. Then, the data user generates a secure index I and an encrypted database as the following steps:Step 1: the data user first uses theIndex Build algorithm to build IAj1≤j≤ρ for each attribute Aj and then encrypts it as follows:(i)
For each nodeN (except the root), the data user encrypts its N⋅id to N⋅id¯=∑⋅Encpk,N⋅id(ii)
For each nodeN (except the root), the data user concatenates all the edge labels, i.e., N⋅edge, along the path from the root to this node, and calculates the PRF output of the concatenation through pseudorandom function Hk1,∗Consider the example in Figure4, which is encrypted from the index IA1 in Figure 3(d).Step 2: the data user encrypts each recordfj∈DB through Π⋅Enck2,∗ and sends these encrypted records to the cloud server with an encrypted index I=IA1,IA2,…,IAρ.Figure 4
An example of the encrypted indexIA1, which is encrypted from Figure 3(d).


### 4.2.3. Compound Substring Query

Given a set of substringsS=s1,…,sρ and a compound formula Ω on S, where Ω consists of conjunctive expressions (i.e., ∩) and disjunctive expressions (i.e., ∪), the data user launches a compound substring query with the cloud server as follows:Step 1: for each substringsj=c1c2…cl with 1≤j≤ρ, the data user calculates qj=Hk1,c1,Hk1,c1c2,…,Hk1,c1…cl and sends a compound substring query token Q=Ω,q1,…,qρ to the cloud server.Step 2: for eachqj∈Q, the cloud server performs algorithm Index Search to search over IAj and outputs a set Rj=idj1¯,…,idjRj¯.Step 3: the cloud server generates a functionϕ:0,1ρ⟶0,1 according to the compound formula Ω. In specific, all the ∩ and ∪ in Ω are replaced by bitwise AND & and bitwise OR |, respectively. For example, if compound formula Ω=q1∪q2∩⋯∩qρ, then ϕ=t1|t2&…&tρ, where tj∈0,1 for j∈0,ρ.Step 4: the cloud server performs Algorithm3 to filter matching elements in R1,…,Rρ according to function ϕ. In specific, assuming that Rmin is the minimum-size element in R1,…,Rρ, for each encrypted identifier id¯ in Rmin, this algorithm traverses all encrypted identifiers in R1,…,Rρ\Rmin to calculate an encrypted flag t¯∈0¯,1¯, which is 1¯ if id matches the compound formula Ω and 0¯ otherwise. Then, the cloud server inserts all the id¯,t¯ to an empty set ℱ and returns it to the data user. Figure 5 depicts an example of this step where the compound formula Ω=q1∩q2∩q3. In this example, id1 is the only identifier that matches the formula Ω. Note that, since an EQ algorithm consumes logμ multiplicative depth and an AND/OR operation consumes 1 multiplicative depth, this step requires at most ⌈logμ⌉+⌈lognμ−1⌉+⌈logρ−1⌉ multiplicative depth, where μ is the average attribute length of database and n is the number of records in the database.Step 5: for eachid¯,t¯∈ℱ, the data user calculates t=∑⋅Decsk,t¯. If t=1, then the data user calculates id=∑⋅Decsk,id¯ and requests a corresponding encrypted record from the cloud server.Algorithm 3: Filter elements in R1,…,Rρ according to function ϕ.
(1)
letRmin be the minimum-size element in R1,…,Rρ.(2)
letℱ be an empty set.(3)
for each id¯∈Rmindo(4)
tmin¯←1¯(5)
for each j∈1,…,ρ/mindo(6)
tj¯←0¯(7)
for each id′¯∈Rjdo(8)
tj′¯←EQid¯,id′¯(9)
tj¯=tj¯|tj′¯(10)
end for(11)
end for(12)
t¯←∑⋅Evalpk,ϕ,t1¯,…,tρ¯(13)
insertid¯,t¯ to ℱ;(14)
end for(15)
returnℱFigure 5
An example of Algorithm3, where the number of attributes ρ=3 and the compound formula Ω=q1∩q2∩q3.


### 4.2.4. Query withs1∗s2 Substring

We extend our scheme to support substring queries withs1∗s2 pattern. The extension is very simple, which only makes some small changes in the processes of the outsourcing phase and compound substring query phase. In specific, when the data user builds index IAj for the attribute column Aj=α1j,α2j,…,αnj, the attribute string tAj=α1j#α2j#⋯#αnj is replaced by tAj=α1j_α1j#α2j_α2j#⋯#αnj_αnj. In other words, each attribute in Aj is copied once and concatenated to its replica with character _, and every two adjacent attributes in Aj are concatenated with character #, where _ and # denote two separate characters that do not appear in Aj. In this way, the substring query with s1∗s2 pattern can be transferred to ∗s∗ pattern where s=s2_s1. Meanwhile, this method leads to double the storage cost of index IAj since the size of the attribute string tAj is twice longer than before.


## 4.2.1. System Initialization

Given a security parameterλ, the data user first initializes a pseudorandom function (PRF) H:0,1λ×0,1∗⟶0,1λ, an IND-CPA secure SKE Π=KeyGen,Enc,Dec, and an IND-CPA secure FHE ∑=KeyGen,Enc,Dec,Eval. Then, the data user generates keys k1←R0,1λ, k2=Π⋅KeyGen1λ, and pk,sk=∑⋅KeyGen1λ.


## 4.2.2. Data Outsourcing

Assume that the data user has a database DB withn records f1,f2,…,fn, where each record fi1≤i≤n includes ρ string-type attributes αi1,αi2,…,αiρ. Then, the data user generates a secure index I and an encrypted database as the following steps:Step 1: the data user first uses theIndex Build algorithm to build IAj1≤j≤ρ for each attribute Aj and then encrypts it as follows:(i)
For each nodeN (except the root), the data user encrypts its N⋅id to N⋅id¯=∑⋅Encpk,N⋅id(ii)
For each nodeN (except the root), the data user concatenates all the edge labels, i.e., N⋅edge, along the path from the root to this node, and calculates the PRF output of the concatenation through pseudorandom function Hk1,∗Consider the example in Figure4, which is encrypted from the index IA1 in Figure 3(d).Step 2: the data user encrypts each recordfj∈DB through Π⋅Enck2,∗ and sends these encrypted records to the cloud server with an encrypted index I=IA1,IA2,…,IAρ.Figure 4
An example of the encrypted indexIA1, which is encrypted from Figure 3(d).


## 4.2.3. Compound Substring Query

Given a set of substringsS=s1,…,sρ and a compound formula Ω on S, where Ω consists of conjunctive expressions (i.e., ∩) and disjunctive expressions (i.e., ∪), the data user launches a compound substring query with the cloud server as follows:Step 1: for each substringsj=c1c2…cl with 1≤j≤ρ, the data user calculates qj=Hk1,c1,Hk1,c1c2,…,Hk1,c1…cl and sends a compound substring query token Q=Ω,q1,…,qρ to the cloud server.Step 2: for eachqj∈Q, the cloud server performs algorithm Index Search to search over IAj and outputs a set Rj=idj1¯,…,idjRj¯.Step 3: the cloud server generates a functionϕ:0,1ρ⟶0,1 according to the compound formula Ω. In specific, all the ∩ and ∪ in Ω are replaced by bitwise AND & and bitwise OR |, respectively. For example, if compound formula Ω=q1∪q2∩⋯∩qρ, then ϕ=t1|t2&…&tρ, where tj∈0,1 for j∈0,ρ.Step 4: the cloud server performs Algorithm3 to filter matching elements in R1,…,Rρ according to function ϕ. In specific, assuming that Rmin is the minimum-size element in R1,…,Rρ, for each encrypted identifier id¯ in Rmin, this algorithm traverses all encrypted identifiers in R1,…,Rρ\Rmin to calculate an encrypted flag t¯∈0¯,1¯, which is 1¯ if id matches the compound formula Ω and 0¯ otherwise. Then, the cloud server inserts all the id¯,t¯ to an empty set ℱ and returns it to the data user. Figure 5 depicts an example of this step where the compound formula Ω=q1∩q2∩q3. In this example, id1 is the only identifier that matches the formula Ω. Note that, since an EQ algorithm consumes logμ multiplicative depth and an AND/OR operation consumes 1 multiplicative depth, this step requires at most ⌈logμ⌉+⌈lognμ−1⌉+⌈logρ−1⌉ multiplicative depth, where μ is the average attribute length of database and n is the number of records in the database.Step 5: for eachid¯,t¯∈ℱ, the data user calculates t=∑⋅Decsk,t¯. If t=1, then the data user calculates id=∑⋅Decsk,id¯ and requests a corresponding encrypted record from the cloud server.Algorithm 3: Filter elements in R1,…,Rρ according to function ϕ.
(1)
letRmin be the minimum-size element in R1,…,Rρ.(2)
letℱ be an empty set.(3)
for each id¯∈Rmindo(4)
tmin¯←1¯(5)
for each j∈1,…,ρ/mindo(6)
tj¯←0¯(7)
for each id′¯∈Rjdo(8)
tj′¯←EQid¯,id′¯(9)
tj¯=tj¯|tj′¯(10)
end for(11)
end for(12)
t¯←∑⋅Evalpk,ϕ,t1¯,…,tρ¯(13)
insertid¯,t¯ to ℱ;(14)
end for(15)
returnℱFigure 5
An example of Algorithm3, where the number of attributes ρ=3 and the compound formula Ω=q1∩q2∩q3.


## 4.2.4. Query withs1∗s2 Substring

We extend our scheme to support substring queries withs1∗s2 pattern. The extension is very simple, which only makes some small changes in the processes of the outsourcing phase and compound substring query phase. In specific, when the data user builds index IAj for the attribute column Aj=α1j,α2j,…,αnj, the attribute string tAj=α1j#α2j#⋯#αnj is replaced by tAj=α1j_α1j#α2j_α2j#⋯#αnj_αnj. In other words, each attribute in Aj is copied once and concatenated to its replica with character _, and every two adjacent attributes in Aj are concatenated with character #, where _ and # denote two separate characters that do not appear in Aj. In this way, the substring query with s1∗s2 pattern can be transferred to ∗s∗ pattern where s=s2_s1. Meanwhile, this method leads to double the storage cost of index IAj since the size of the attribute string tAj is twice longer than before.


## 5. Security Analysis

In this section, we prove the security of our proposed scheme based on the security definition described in Section3.4.


### 5.1. Leakage Function Collection

We first define the leakage function collectionℒ=ℒO,ℒQ of our proposed scheme.(i)
Outsourcing Phase: given the indexI=IA1,IA2,…,IAρ and the encrypted database DB, the leakage ℒO consists of the following information:(a)
n: the number of records in DB(b)
fi1≤i≤n: the size of record fi∈DB(c)
ρ: the number of attributes in DB(d)
IAj1≤j≤ρ: the number of nodes in IAj(e)
Γj1≤j≤ρ: the structural dependencies between nodes in IAj(ii)
Query Phase: given the indexI=IA1,IA2,…,IAρ and a compound substring query token Q, the leakage ℒQ consists of the following information:(a)
path pattern: search paths in IAj1≤j≤ρ corresponding to the query token Q(b)
Ω: compound formula in Q


### 5.2. Security Proof

Now, we prove the security of our proposed scheme based on the leakage function collectionℒ=ℒO,ℒQ. Intuitively, we first define a simulator S based on the leakage function collection ℒ and then analyze the indistinguishability between the output of the S in the ideal world and the challenger C (i.e., the data user) in the real world. Finally, we conclude that our proposed scheme does not reveal any information beyond the leakage function collection ℒ to the server. The details are as follows.Theorem 1.
LetH be a pseudorandom function (PRF), let Π be an IND-CPA secure symmetric key encryption scheme (SKE), and let ∑ be an IND-CPA secure fully homomorphic encryption (FHE). Then, our proposed scheme is ℒ-adaptively secure.Proof.
Based on the leakage function collectionℒ, we can build a simulator S as follows:(i)
Data outsourcing: given the leakage functionℒO=n,fi1≤i≤n,ρ,IAj1≤j≤ρ,Γj1≤j≤ρ, the simulator S is supposed to generate a simulated index I′=IA1′,IA2′,…,IAρ′ and a simulated encrypted database DB′. To build IAj′∈I′, the simulator S first generates IAj empty nodes and constructs these nodes to a tree (i.e., IAj′) based on Γj, which means that IAj′ has the same tree structure as IAj. Then, for each node N in IAj′, the simulator S randomly chooses N⋅edge∈0,1λ and N⋅id∈0,1d. Since the outputs of H and ∑⋅Enc are pseudorandom, the adversary A cannot distinguish between I′ and I. To build DB′, the simulator S chooses a random value ri←0,1fi for each record fi∈DB and lets DB′=r1,…,rn. Since Π is an IND-CPA secure SKE, the adversary A cannot distinguish between DB′ and DB.(2)
Compound substring query: given the leakage functionℒQ for a compound substring query token Q=Ω,q1,….,qρ, the simulator S is supposed to generate a simulated encrypted compound substring query token Q′=Ω,q1′,…,qρ′. Note that, at this moment, the simulator S has not only ℒQ but also ℒO and I′ from the data outsourcing phase. Therefore, for each IAj′∈I′, the simulator S can follow the corresponding path pattern in ℒQ to find its search path and output all the N⋅edge stored in the nodes along the search path as Q′. Since H is a pseudorandom function, the adversary A cannot distinguish between Q′ and Q.
In summary, as the adversaryA cannot distinguish between the outputs from the simulator S in the ideal world and the challenger C in the real world, we can conclude that our proposed scheme is ℒ-adaptively secure.


## 5.1. Leakage Function Collection

We first define the leakage function collectionℒ=ℒO,ℒQ of our proposed scheme.(i)
Outsourcing Phase: given the indexI=IA1,IA2,…,IAρ and the encrypted database DB, the leakage ℒO consists of the following information:(a)
n: the number of records in DB(b)
fi1≤i≤n: the size of record fi∈DB(c)
ρ: the number of attributes in DB(d)
IAj1≤j≤ρ: the number of nodes in IAj(e)
Γj1≤j≤ρ: the structural dependencies between nodes in IAj(ii)
Query Phase: given the indexI=IA1,IA2,…,IAρ and a compound substring query token Q, the leakage ℒQ consists of the following information:(a)
path pattern: search paths in IAj1≤j≤ρ corresponding to the query token Q(b)
Ω: compound formula in Q


## 5.2. Security Proof

Now, we prove the security of our proposed scheme based on the leakage function collectionℒ=ℒO,ℒQ. Intuitively, we first define a simulator S based on the leakage function collection ℒ and then analyze the indistinguishability between the output of the S in the ideal world and the challenger C (i.e., the data user) in the real world. Finally, we conclude that our proposed scheme does not reveal any information beyond the leakage function collection ℒ to the server. The details are as follows.Theorem 1.
LetH be a pseudorandom function (PRF), let Π be an IND-CPA secure symmetric key encryption scheme (SKE), and let ∑ be an IND-CPA secure fully homomorphic encryption (FHE). Then, our proposed scheme is ℒ-adaptively secure.Proof.
Based on the leakage function collectionℒ, we can build a simulator S as follows:(i)
Data outsourcing: given the leakage functionℒO=n,fi1≤i≤n,ρ,IAj1≤j≤ρ,Γj1≤j≤ρ, the simulator S is supposed to generate a simulated index I′=IA1′,IA2′,…,IAρ′ and a simulated encrypted database DB′. To build IAj′∈I′, the simulator S first generates IAj empty nodes and constructs these nodes to a tree (i.e., IAj′) based on Γj, which means that IAj′ has the same tree structure as IAj. Then, for each node N in IAj′, the simulator S randomly chooses N⋅edge∈0,1λ and N⋅id∈0,1d. Since the outputs of H and ∑⋅Enc are pseudorandom, the adversary A cannot distinguish between I′ and I. To build DB′, the simulator S chooses a random value ri←0,1fi for each record fi∈DB and lets DB′=r1,…,rn. Since Π is an IND-CPA secure SKE, the adversary A cannot distinguish between DB′ and DB.(2)
Compound substring query: given the leakage functionℒQ for a compound substring query token Q=Ω,q1,….,qρ, the simulator S is supposed to generate a simulated encrypted compound substring query token Q′=Ω,q1′,…,qρ′. Note that, at this moment, the simulator S has not only ℒQ but also ℒO and I′ from the data outsourcing phase. Therefore, for each IAj′∈I′, the simulator S can follow the corresponding path pattern in ℒQ to find its search path and output all the N⋅edge stored in the nodes along the search path as Q′. Since H is a pseudorandom function, the adversary A cannot distinguish between Q′ and Q.
In summary, as the adversaryA cannot distinguish between the outputs from the simulator S in the ideal world and the challenger C in the real world, we can conclude that our proposed scheme is ℒ-adaptively secure.


## 6. Performance Evaluation

In this section, we evaluate the performance of our proposed scheme from both theoretical and experimental perspectives. To the best of our knowledge, we are the first to discuss the compound substring query. Although some existing works [9–11] focus on the substring query, they cannot directly support the compound substring query. Therefore, a fair comparison is quite difficult and we just evaluate our proposed scheme in this section.


### 6.1. Theoretical Analysis

First, we theoretically analyze the query computational cost and storage overhead of our proposed scheme.For the query computational cost, we analyze the server and user separately. In specific, the query computational cost of the server comes from two steps: search over indexI to get a set of collections R1,…,Rρ and filter matching elements in R1,…,Rρ. The former consumes at most ∑j=1ρsj integer comparison operations and the latter consumes at most ρ⋅Rmin⋅Rmax FHE multiplication operations, where Rmin and Rmax are the minimum-size and maximum-size elements in R1,…,Rρ. Meanwhile, the query computational cost of the user also comes from two steps: generate query token Q and decrypt the returned FHE ciphertexts, which consumes ∑j=1ρsj hash operations and Rmin FHE decryption operations, respectively. Compared with the above operations, we can see that ρ⋅Rmin⋅Rmax FHE multiplication operations on the server dominate the query computational cost.For the storage overhead, most of the storage overhead in our proposed scheme comes from the encrypted identifiers inI=IA1,IA2,…,IAρ, which consumes ∑j=1ρIAj⋅logn/ℓ FHE ciphertexts, where IAj is the number of nodes in IAj and ℓ is the decomposition parameter in FHE (see next subsection).


### 6.2. Experimental Analysis

Then, we experimentally analyze our proposed scheme. In specific, we implement our proposed scheme in C++ (our code is open source [16]) and conduct experiments on a 64-bit machine with an Intel(R) Core(TM) i5-4300M CPU at 2.6GHZ and 4 GB RAM, running Ubuntu 18.4. Note that we implement the data user and cloud server on the same machine, which means there is no network delay between them. The underlying database in our experiment was extracted from Kaggle [17]. It contains 31,087 movies and 153,584 movie tags. The average length of all these movie tags is about 10. We treat each movie as a record with corresponding tags as its attributes.


#### 6.2.1. FHE Implementation

In order to reduce the storage overhead of FHE, we use the SIMD technique [18] in experiments. Before describing our packing method, we first review the underlying structure of FHE. Specifically, the plaintext space of FHE is P=Fpx/Φmx for a positive integer p≥2 where Φmx is the mth cyclotomic polynomial. When the plaintext modulus p is prime and not divisible by m, the Φmx decomposes into ℓ irreducible factors f1x,…,fℓx of degree d modulo p. This induces an isomorphism, via the Chinese Remainder Theorem, between the algebra of the plaintext space P=Fpx/Φmx and the product of ℓ finite fields Li≅Fpd for i∈1,…,ℓ,(1)P≅Fpxf1x×⋯×Fpxflx=L1×⋯×Lℓ≅Fpdℓ.With this decomposition, the plaintext of compatible FHE schemes can be regarded as a lengthℓ vector m=m1,…,mℓ, where mi∈Fpd for i∈1,..,ℓ. Addition and multiplication on ciphertext m¯ correspond to component-wise addition and multiplication over the mi for i∈1,…,ℓ.Now we give our packing method. In our proposed scheme, each indexIAj for j∈1,ρ includes a set of identifiers IDj=id1,id2,…,idIAj, where each identifier idk in it can be seen as a bit-array idk,1,idk,2,…,idk,logn. In the experiments, we pack each IDj to IAj/ℓ×logn FHE ciphertexts, which means each idk,l for k∈1,Aj and l∈1,logn is encoded to an element in F2d and therefore an FHE ciphertext contains ℓ bits in IDj.


#### 6.2.2. HElib Parameters

We utilize the HElib library [19] to implement the FHE described above. For the parameters, we choose p=2 and m=18631, which lead to φm=18000, d=25, and ℓ=720. Meanwhile, the recent version of the HElib library (commit c74ffab in [19]) uses a concept of ciphertext capacity instead of depth. The ciphertext capacity of a ciphertext is defined in [20] as logQ/η, where Q is the current modulus, and η is the current noise bound. In practice, an EQ algorithm costs about 60-bit capacity and an AND/OR operation costs about 25-bit capacity when p=2 and m=18631. Since n in our experiments does not exceed 25000, ρ does not exceed 5, and the average attribute length μ=10, we set the initial ciphertext capacity to 60+⌈log2500⋅10−1⌉⋅25+⌈log5−1⌉⋅25=485, which leads to 84-bit security.In the following, we evaluate the computational cost and storage overhead of our proposed scheme in terms of two phases: data outsourcing and compound substring query.


#### 6.2.3. Data Outsourcing

First, we consider the computational cost and storage overhead of the data outsourcing phase, which mainly comes from the building runtime and storage overhead of indexI=IA1,IA2,…,IAρ. Figures 6 and 7 plot the building runtime and storage overhead of the data outsourcing versus the number of records n and the number of attributes ρ. From these figures, we can see that both computational cost and storage overhead increase linearly with n and ρ.Figure 6
The data outsourcing runtime versus the number of recordsn, where the number of attributes ρ is fixed to 3.Figure 7
The storage overhead versus the number of recordsn, where the number of attributes ρ is chosen from 2 to 5.


#### 6.2.4. Compound Substring Query

Next, we consider the computational cost of the compound substring query phase. As mentioned in the last subsection, most of the query computational cost is fromρ⋅Rmin⋅Rmax FHE multiplication operations on the server, where Rmin and Rmax are the minimum-size and maximum-size elements in R1,…,Rρ. As shown in Figures 8 and 9, the query time is indeed linear with Rmin⋅Rmax and ρ. Meanwhile, it is not affected by the number of records n.Figure 8
The query runtime versus the size ofRmin⋅Rmax, where the number of records is chosen from 500 to 2000 and the number of attributes ρ is fixed to 3.Figure 9
The query runtime versus the size ofRmin⋅Rmax, where the number of attributes ρ is chosen from 2 to 5 and the number of records n is fixed to 500.


## 6.1. Theoretical Analysis

First, we theoretically analyze the query computational cost and storage overhead of our proposed scheme.For the query computational cost, we analyze the server and user separately. In specific, the query computational cost of the server comes from two steps: search over indexI to get a set of collections R1,…,Rρ and filter matching elements in R1,…,Rρ. The former consumes at most ∑j=1ρsj integer comparison operations and the latter consumes at most ρ⋅Rmin⋅Rmax FHE multiplication operations, where Rmin and Rmax are the minimum-size and maximum-size elements in R1,…,Rρ. Meanwhile, the query computational cost of the user also comes from two steps: generate query token Q and decrypt the returned FHE ciphertexts, which consumes ∑j=1ρsj hash operations and Rmin FHE decryption operations, respectively. Compared with the above operations, we can see that ρ⋅Rmin⋅Rmax FHE multiplication operations on the server dominate the query computational cost.For the storage overhead, most of the storage overhead in our proposed scheme comes from the encrypted identifiers inI=IA1,IA2,…,IAρ, which consumes ∑j=1ρIAj⋅logn/ℓ FHE ciphertexts, where IAj is the number of nodes in IAj and ℓ is the decomposition parameter in FHE (see next subsection).


## 6.2. Experimental Analysis

Then, we experimentally analyze our proposed scheme. In specific, we implement our proposed scheme in C++ (our code is open source [16]) and conduct experiments on a 64-bit machine with an Intel(R) Core(TM) i5-4300M CPU at 2.6GHZ and 4 GB RAM, running Ubuntu 18.4. Note that we implement the data user and cloud server on the same machine, which means there is no network delay between them. The underlying database in our experiment was extracted from Kaggle [17]. It contains 31,087 movies and 153,584 movie tags. The average length of all these movie tags is about 10. We treat each movie as a record with corresponding tags as its attributes.


### 6.2.1. FHE Implementation

In order to reduce the storage overhead of FHE, we use the SIMD technique [18] in experiments. Before describing our packing method, we first review the underlying structure of FHE. Specifically, the plaintext space of FHE is P=Fpx/Φmx for a positive integer p≥2 where Φmx is the mth cyclotomic polynomial. When the plaintext modulus p is prime and not divisible by m, the Φmx decomposes into ℓ irreducible factors f1x,…,fℓx of degree d modulo p. This induces an isomorphism, via the Chinese Remainder Theorem, between the algebra of the plaintext space P=Fpx/Φmx and the product of ℓ finite fields Li≅Fpd for i∈1,…,ℓ,(1)P≅Fpxf1x×⋯×Fpxflx=L1×⋯×Lℓ≅Fpdℓ.With this decomposition, the plaintext of compatible FHE schemes can be regarded as a lengthℓ vector m=m1,…,mℓ, where mi∈Fpd for i∈1,..,ℓ. Addition and multiplication on ciphertext m¯ correspond to component-wise addition and multiplication over the mi for i∈1,…,ℓ.Now we give our packing method. In our proposed scheme, each indexIAj for j∈1,ρ includes a set of identifiers IDj=id1,id2,…,idIAj, where each identifier idk in it can be seen as a bit-array idk,1,idk,2,…,idk,logn. In the experiments, we pack each IDj to IAj/ℓ×logn FHE ciphertexts, which means each idk,l for k∈1,Aj and l∈1,logn is encoded to an element in F2d and therefore an FHE ciphertext contains ℓ bits in IDj.


### 6.2.2. HElib Parameters

We utilize the HElib library [19] to implement the FHE described above. For the parameters, we choose p=2 and m=18631, which lead to φm=18000, d=25, and ℓ=720. Meanwhile, the recent version of the HElib library (commit c74ffab in [19]) uses a concept of ciphertext capacity instead of depth. The ciphertext capacity of a ciphertext is defined in [20] as logQ/η, where Q is the current modulus, and η is the current noise bound. In practice, an EQ algorithm costs about 60-bit capacity and an AND/OR operation costs about 25-bit capacity when p=2 and m=18631. Since n in our experiments does not exceed 25000, ρ does not exceed 5, and the average attribute length μ=10, we set the initial ciphertext capacity to 60+⌈log2500⋅10−1⌉⋅25+⌈log5−1⌉⋅25=485, which leads to 84-bit security.In the following, we evaluate the computational cost and storage overhead of our proposed scheme in terms of two phases: data outsourcing and compound substring query.


### 6.2.3. Data Outsourcing

First, we consider the computational cost and storage overhead of the data outsourcing phase, which mainly comes from the building runtime and storage overhead of indexI=IA1,IA2,…,IAρ. Figures 6 and 7 plot the building runtime and storage overhead of the data outsourcing versus the number of records n and the number of attributes ρ. From these figures, we can see that both computational cost and storage overhead increase linearly with n and ρ.Figure 6
The data outsourcing runtime versus the number of recordsn, where the number of attributes ρ is fixed to 3.Figure 7
The storage overhead versus the number of recordsn, where the number of attributes ρ is chosen from 2 to 5.


### 6.2.4. Compound Substring Query

Next, we consider the computational cost of the compound substring query phase. As mentioned in the last subsection, most of the query computational cost is fromρ⋅Rmin⋅Rmax FHE multiplication operations on the server, where Rmin and Rmax are the minimum-size and maximum-size elements in R1,…,Rρ. As shown in Figures 8 and 9, the query time is indeed linear with Rmin⋅Rmax and ρ. Meanwhile, it is not affected by the number of records n.Figure 8
The query runtime versus the size ofRmin⋅Rmax, where the number of records is chosen from 500 to 2000 and the number of attributes ρ is fixed to 3.Figure 9
The query runtime versus the size ofRmin⋅Rmax, where the number of attributes ρ is chosen from 2 to 5 and the number of records n is fixed to 500.


## 6.2.1. FHE Implementation

In order to reduce the storage overhead of FHE, we use the SIMD technique [18] in experiments. Before describing our packing method, we first review the underlying structure of FHE. Specifically, the plaintext space of FHE is P=Fpx/Φmx for a positive integer p≥2 where Φmx is the mth cyclotomic polynomial. When the plaintext modulus p is prime and not divisible by m, the Φmx decomposes into ℓ irreducible factors f1x,…,fℓx of degree d modulo p. This induces an isomorphism, via the Chinese Remainder Theorem, between the algebra of the plaintext space P=Fpx/Φmx and the product of ℓ finite fields Li≅Fpd for i∈1,…,ℓ,(1)P≅Fpxf1x×⋯×Fpxflx=L1×⋯×Lℓ≅Fpdℓ.With this decomposition, the plaintext of compatible FHE schemes can be regarded as a lengthℓ vector m=m1,…,mℓ, where mi∈Fpd for i∈1,..,ℓ. Addition and multiplication on ciphertext m¯ correspond to component-wise addition and multiplication over the mi for i∈1,…,ℓ.Now we give our packing method. In our proposed scheme, each indexIAj for j∈1,ρ includes a set of identifiers IDj=id1,id2,…,idIAj, where each identifier idk in it can be seen as a bit-array idk,1,idk,2,…,idk,logn. In the experiments, we pack each IDj to IAj/ℓ×logn FHE ciphertexts, which means each idk,l for k∈1,Aj and l∈1,logn is encoded to an element in F2d and therefore an FHE ciphertext contains ℓ bits in IDj.


## 6.2.2. HElib Parameters

We utilize the HElib library [19] to implement the FHE described above. For the parameters, we choose p=2 and m=18631, which lead to φm=18000, d=25, and ℓ=720. Meanwhile, the recent version of the HElib library (commit c74ffab in [19]) uses a concept of ciphertext capacity instead of depth. The ciphertext capacity of a ciphertext is defined in [20] as logQ/η, where Q is the current modulus, and η is the current noise bound. In practice, an EQ algorithm costs about 60-bit capacity and an AND/OR operation costs about 25-bit capacity when p=2 and m=18631. Since n in our experiments does not exceed 25000, ρ does not exceed 5, and the average attribute length μ=10, we set the initial ciphertext capacity to 60+⌈log2500⋅10−1⌉⋅25+⌈log5−1⌉⋅25=485, which leads to 84-bit security.In the following, we evaluate the computational cost and storage overhead of our proposed scheme in terms of two phases: data outsourcing and compound substring query.


## 6.2.3. Data Outsourcing

First, we consider the computational cost and storage overhead of the data outsourcing phase, which mainly comes from the building runtime and storage overhead of indexI=IA1,IA2,…,IAρ. Figures 6 and 7 plot the building runtime and storage overhead of the data outsourcing versus the number of records n and the number of attributes ρ. From these figures, we can see that both computational cost and storage overhead increase linearly with n and ρ.Figure 6
The data outsourcing runtime versus the number of recordsn, where the number of attributes ρ is fixed to 3.Figure 7
The storage overhead versus the number of recordsn, where the number of attributes ρ is chosen from 2 to 5.


## 6.2.4. Compound Substring Query

Next, we consider the computational cost of the compound substring query phase. As mentioned in the last subsection, most of the query computational cost is fromρ⋅Rmin⋅Rmax FHE multiplication operations on the server, where Rmin and Rmax are the minimum-size and maximum-size elements in R1,…,Rρ. As shown in Figures 8 and 9, the query time is indeed linear with Rmin⋅Rmax and ρ. Meanwhile, it is not affected by the number of records n.Figure 8
The query runtime versus the size ofRmin⋅Rmax, where the number of records is chosen from 500 to 2000 and the number of attributes ρ is fixed to 3.Figure 9
The query runtime versus the size ofRmin⋅Rmax, where the number of attributes ρ is chosen from 2 to 5 and the number of records n is fixed to 500.


## 7. Related Work

A searchable encryption scheme can be realized with optimal security via powerful cryptographic tools, such as fully homomorphic encryption (FHE) [21, 22] and Oblivious Random Access Memory (ORAM) [23, 24]. However, these tools are extraordinarily impractical. Another set of works utilize property-preserving encryption (PPE) [25–28] to achieve searchable encryption, which encrypts messages in a way that inevitably leaks certain properties of the underlying message. For balancing the leakage and efficiency, many studies focus on searchable symmetric encryption (SSE). Song et al. [3] first used symmetric encryption to facilitate attribute queries over the encrypted data. Then, Curtmola et al. [5] gave a formal definition of SSE and proposed an efficient SSE scheme. Later, Kamara et al. [29] proposed the first dynamic SSE scheme, which uses a deletion array and a homomorphically encrypted pointer technique to securely update files. Unfortunately, due to the use of fully homomorphic encryption, the update efficiency is very low. In a more recent paper [7], Cash et al. described a simple dynamic inverted index based on [5], which utilizes the data unlinkability of the hash table to achieve secure insertion. Meanwhile, to prevent the file-injection attacks [30], many works [31–34] focused on forward security, which ensures that newly updated attributes cannot be related to previous queried results.Nevertheless, these above works only can support the exact attribute query. If the queried attribute does not match a preset attribute, the query will fail. Fortunately, the fuzzy query can deal with this problem as it can tolerate minor typos and formatting inconsistencies. Li et al. [35] first proposed a fuzzy query scheme, which used an edit distance with a wildcard-based technique to construct fuzzy attribute sets. For instance, the set of CAT with 1 edit distance is CAT,∗CAT,∗AT,C∗AT,C∗T,CA∗T,CA∗,CAT∗. Then, Kuzu et al. [36] used LSH (Local Sensitive Hash) and Bloom filter to construct a similarity query scheme. Since an honest-but-curious server may only return a fraction of the results, Wang et al. [37] proposed a verifiable fuzzy query scheme that not only supports fuzzy query service but also provides proof to verify whether the server returns all the queried results. However, these fuzzy query schemes only support single fuzzy attribute queries and address problems of minor typos and formatting inconsistency, which cannot be directly used to achieve substring queries.In [9], Chase and Shen designed an SSE scheme based on the suffix tree to support substring queries. Although this scheme can be used to implement the substring query and allows for substring query in Os+ds time, its storage cost Om has a big constant factor. The reason is that the suffix tree only stores position data in leaf nodes and does not utilize the space of inner nodes effectively. This makes the number of nodes in the suffix tree can be up to 2m, where m is the size of the dataset. In order to reduce the storage cost as much as possible, Leontiadis and Li [13] leveraged Burrows-Wheeler Transform (BWT) to build an auxiliary data structure called a suffix array, which can achieve storage cost Om with a lower constant factor. However, its query time is relatively large. Later, Mainardi et al. [11] optimize the query algorithm in [13] to achieve Os+ds at the cost of higher index space, i.e., OΣ⋅m, where Σ is the number of distinct characters in the dictionary. In addition to suffix tree and suffix array, there are some other auxiliary data structures that can be used to support substring queries. In 2018, Hahn et al. [38] designed an index based on k-grams. When a user needs to perform a substring query, the cloud performs a conjunctive keyword query for all the k-grams of the queried substring. In the same year, Moataz et al. [10] proposed a new substring query scheme based on the idea of letter orthogonalization, which allows testing of string membership by performing an efficient inner product. Although the above schemes can support substring queries, they can only solve the substring query problem for a single attribute, which cannot be used to achieve compound substring queries efficiently.


## 8. Conclusion

In this paper, we have proposed a novel efficient and privacy-preserving compound substring query scheme. Specifically, based on the position heap technique, we first designed a tree-based index to support a substring query on a single attribute and then applied PRF and FHE techniques to protect its privacy. In addition, based on the homomorphism of fully homomorphic encryption, we designed an algorithm to support compound substring queries on multiple attributes. Detailed security analysis and performance evaluation show that our proposed scheme is indeed privacy-preserving and efficient. In our future work, we will consider extending the proposed scheme to support wildcard queries.



---

*Source: 7941233-2021-12-03.xml*