# Semantic-Based Multi-Keyword Ranked Search Schemes over Encrypted Cloud Data

Authors: Zheng Hu; Hua Dai; Geng Yang; Xun Yi; Wenjie Sheng
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Traditional searchable encryption schemes construct document vectors based on the term frequency-inverse document frequency (TF-IDF) model. Such vectors are not only high-dimensional and sparse but also ignore the semantic information of the documents. The Sentence Bidirectional Encoder Representations from Transformers (SBERT) model can be used to train vectors containing document semantic information to realize semantic-aware multi-keyword search. In this paper, we propose a privacy-preserving searchable encryption scheme based on the SBERT model. The SBERT model is used to train vectors containing the semantic information of documents, and these document vectors are then used as input to the Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) clustering algorithm. The HDBSCAN algorithm generates a soft cluster membership vector for each document. We treat each cluster as a topic, and the vector represents the probability that the document belongs to each topic. According to the clustering process in the schemes, the topic-term frequency-inverse topic frequency (TTF-ITF) model is proposed to generate keyword topic vectors. Through the SBERT model, searchable encryption scheme can achieve more precise semantic-aware keyword search. At the same time, the special index tree is used to improve search efficiency. The experimental results on real datasets prove the effectiveness of our scheme.


---

## Body

## 1. Introduction

Cloud computing is an Internet-based business computing model that provides fast and secure cloud computing services and data storage. Cloud computing uses the transmission capabilities of the Internet to transfer data storage and processing from local servers to the Internet. It is a product of the development and integration of traditional IT technologies such as distributed computing, parallel computing, network storage, and virtualization. Cloud computing distributes computing tasks on a resource pool composed of a large number of computers, enabling various application systems to obtain computing power, storage space, and various software services as needed. Cloud computing can solve the problems of enterprises’ dynamic demand for resources and storage costs, so more and more enterprises choose to outsource data to the cloud. Although cloud computing has many advantages, there are also some problems, such as data privacy issues. In order to protect the privacy of outsourced cloud data, the usual solution is to encrypt the data before outsourcing or use blockchain to achieve privacy protection [1]. However, the encrypted data hardly meet general application requirements, such as search. Therefore, research on searchable encryption schemes is necessary.In recent years, researchers have done a lot of research on searchable encryption, such as searchable encryption for documents [2–40] and searchable encryption for images [41, 42]. The research in this paper focuses on searchable encryption of documents; many searchable encryption schemes have been proposed, such as single keyword search [2–10], multi-keyword search [11–26], fuzzy keyword search [27–31], conjunctive keyword search [32–35], and search based on semantic expansion [36–40]. Most of these searchable encryption schemes are based on the term frequency-inverse document frequency (TF-IDF) model; they use secure KNN [11] to generate encrypted document vectors and encrypted indexes, and the data owner outsources the encrypted documents and indexes to the cloud. Once the search begins, a trapdoor for the query keyword is generated and used to perform the search using the encrypted index. In the search process, the smaller the inner product between a query vector and a document vector, the closer a query is to a document. However, the TF-IDF model is a statistical model used to evaluate the importance of keywords to a set of documents, which ignores the semantic association between keywords and documents, resulting in search results that do not meet the needs of users. At the same time, due to the large number of keywords in the dictionary, the vector generated by the TF-IDF model has an extremely high dimension and sparsity, so the existing search scheme has a large search time and space cost, but the effect is not satisfactory.In order to enable the document vector to better express the semantic information of the document, we introduced the Bidirectional Encoder Representations from Transformers (BERT) model and the SBERT model. BERT is designed to pretrain deep bidirectional representations from unlabeled text by jointly conditioning on both left and right contexts in all layers. Therefore, it is only necessary to add an output layer to fine-tune the pretrained BERT model to create state-of-the-art models suitable for various tasks. A common method to solve clustering and semantic search is to map each sentence to a vector space so that semantically similar sentences are very close. Someone has tried to input the entire sentence into the BERT pretraining model to get the vector representation of the sentence. However, it is pointed out in Ref. [43] that the sentence vectors thus obtained do not have semantic information. In other words, two similar sentences may have very different sentence vectors. Aiming at the problem of the abovementioned pretraining model on the regression task of sentence pairs such as text semantic similarity, Ref. [44] proposed the SBERT model. The SBERT model uses Siamese and triplet network structures to obtain sentence embeddings with semantic information, and uses cosine similarity or Manhattan/Euclidean distance to compare and find semantically similar sentences.In this paper, we proposed a semantic-aware searchable encryption scheme based on the SBERT model (SBERT-SRSE). The data owner first uses the SBERT model to train documents to get document embedding matrixΩ. Then, Ω is used as the input of the Hierarchical Density-Based Spatial Clustering of Applications with Noise (HBSCAN) clustering algorithm to generate a soft membership vector for each document. We regard each cluster as a topic, so the document topic association matrix (DTA-matrix) can be obtained. We use Topic-Term Frequency-Inverse Topic Frequency (TTF-ITF) to get keyword topic association matrix (KTA-matrix). In order to further improve search efficiency, we construct a tree index. Finally, encrypt the documents and index tree and outsource to the cloud. When starting a multi-keyword ranked search to retrieve the k most relevant documents, the data user converts the query keywords into a query topic vector, and encrypts the topic vector as a trapdoor. The cloud executes the search on the encrypted index tree and returns encrypted documents with the top-k relevance scores as the search result. Our contributions are summarized as follows:(1)
Based on the SBERT model, UMAP dimension reduction algorithm, and HDBSCAN clustering algorithm, we propose a document vectorization method that contains the topic semantic information of documents.(2)
We propose the Topic-Term Frequency-Inverse Topic Frequency (TTF-ITF) model to measure the importance of keywords to topics, and generate keyword topic vectors according to this model.(3)
We construct an index tree based on the semantic-related document list; the index further improves the efficiency of searches.


## 2. Related Work

In recent years, searchable encryption has been widely studied, and many searchable encryption schemes have been proposed, including single keyword searchable encryption schemes [2–10], multi-keyword searchable encryption schemes [11–24, 32–35], and multi-keyword searchable encryption schemes with semantic expansion [36–40]. We discussed the work related to the performance and functionality development of searchable encryption schemes.


### 2.1. Single Keyword Searchable Encryption Schemes

Song et al. [7] first proposed a single keyword searchable encryption scheme in 2000, in which the search time of the scheme is linearly related to the size of data collection. Goh [8] formally defined a secure index structure and designed an index scheme based on Bloom filter. However, because Bloom filters can have false positives, the cloud server may return documents that do not contain the search keywords. Due to the lack of a ranking mechanism for the searchable encryption scheme described above, it can take a long time for users to select what they want when a large number of documents contain queried keywords. Wang et al. [5] proposed a searchable single keyword ranked search encryption scheme in 2010, which is based on the TF-IDF model and uses inverted index. During the search, the cloud server computes relevance scores between documents and queries, sorts related documents according to their relevance score, and the user can get the top-k results. Some other ranked search schemes in literature [3, 9]. The above searchable encryption scheme only supports single keyword search.


### 2.2. Multi-Keyword Searchable Encryption Schemes

The multi-keyword searchable encryption scheme allows users to submit multiple query keywords to retrieve related documents. Among them, the conjunctive keyword search schemes [32–35] only return documents containing all query keywords, while the disjunctive keyword search scheme [23, 24] returns all documents containing subsets of query keywords. None of the above schemes support the ranking function of search results. Cao et al. [11] first proposed a private multi-keyword ranked search scheme in 2011, and Sun et al. [12] proposed a secure multi-keyword search scheme on the basis of Ref. [11]. They used TFIDF model and cosine distance measure to construct MDB-tree [45], which improved the search efficiency. Xia et al. [20] proposed a multi-keyword ranked search scheme based on KBB tree, which supports the dynamic updating and deletion of documents. Chen et al. [16] and Zhu et al. [21] proposed an efficient ranked search scheme, and they both used clustering algorithm to improve search efficiency.


### 2.3. Multi-Keyword Searchable Encryption Schemes with Semantic Extension

Since the traditional searchable encryption schemes based on TF-IDF model do not consider the semantic association between keywords and documents, this may result in search results that do not match the users’ search intention. In order to overcome the lack of semantics, a searchable encryption scheme based on semantic extension was proposed. Xia et al. [36] implemented a multi-keyword searchable encryption scheme using inverted index and extended queried keywords and synonyms. Fu et al. [37] used synonym extensions of dictionary keywords to implement a multi-keyword searchable encryption scheme. Xia et al. [36] and Fu et al. [37] are based on the TF-IDF model, which is not a semantic model, so it is difficult for their scheme to improve the semantic accuracy of the search. Fu et al. [38, 39] adopted different semantic models, which required supervised learning of datasets, and could not be directly applied to different datasets. Dai et al. [40] first introduced the LDA topic model into searchable encryption. Through LDA topic model training, documents are transformed into topic vectors. Compared with the document features extracted by the TF-IDF model, the topic vector has a smaller dimension and can extract the semantic features contained in the document. When the search begins, the queried keywords are transformed into topic vector to better identify the users’ search intent.


## 2.1. Single Keyword Searchable Encryption Schemes

Song et al. [7] first proposed a single keyword searchable encryption scheme in 2000, in which the search time of the scheme is linearly related to the size of data collection. Goh [8] formally defined a secure index structure and designed an index scheme based on Bloom filter. However, because Bloom filters can have false positives, the cloud server may return documents that do not contain the search keywords. Due to the lack of a ranking mechanism for the searchable encryption scheme described above, it can take a long time for users to select what they want when a large number of documents contain queried keywords. Wang et al. [5] proposed a searchable single keyword ranked search encryption scheme in 2010, which is based on the TF-IDF model and uses inverted index. During the search, the cloud server computes relevance scores between documents and queries, sorts related documents according to their relevance score, and the user can get the top-k results. Some other ranked search schemes in literature [3, 9]. The above searchable encryption scheme only supports single keyword search.


## 2.2. Multi-Keyword Searchable Encryption Schemes

The multi-keyword searchable encryption scheme allows users to submit multiple query keywords to retrieve related documents. Among them, the conjunctive keyword search schemes [32–35] only return documents containing all query keywords, while the disjunctive keyword search scheme [23, 24] returns all documents containing subsets of query keywords. None of the above schemes support the ranking function of search results. Cao et al. [11] first proposed a private multi-keyword ranked search scheme in 2011, and Sun et al. [12] proposed a secure multi-keyword search scheme on the basis of Ref. [11]. They used TFIDF model and cosine distance measure to construct MDB-tree [45], which improved the search efficiency. Xia et al. [20] proposed a multi-keyword ranked search scheme based on KBB tree, which supports the dynamic updating and deletion of documents. Chen et al. [16] and Zhu et al. [21] proposed an efficient ranked search scheme, and they both used clustering algorithm to improve search efficiency.


## 2.3. Multi-Keyword Searchable Encryption Schemes with Semantic Extension

Since the traditional searchable encryption schemes based on TF-IDF model do not consider the semantic association between keywords and documents, this may result in search results that do not match the users’ search intention. In order to overcome the lack of semantics, a searchable encryption scheme based on semantic extension was proposed. Xia et al. [36] implemented a multi-keyword searchable encryption scheme using inverted index and extended queried keywords and synonyms. Fu et al. [37] used synonym extensions of dictionary keywords to implement a multi-keyword searchable encryption scheme. Xia et al. [36] and Fu et al. [37] are based on the TF-IDF model, which is not a semantic model, so it is difficult for their scheme to improve the semantic accuracy of the search. Fu et al. [38, 39] adopted different semantic models, which required supervised learning of datasets, and could not be directly applied to different datasets. Dai et al. [40] first introduced the LDA topic model into searchable encryption. Through LDA topic model training, documents are transformed into topic vectors. Compared with the document features extracted by the TF-IDF model, the topic vector has a smaller dimension and can extract the semantic features contained in the document. When the search begins, the queried keywords are transformed into topic vector to better identify the users’ search intent.


## 3. Notations and Preliminaries

### 3.1. Notations

D: The set of n plaintext documents, D=d1,d2,…,dn.D˜: The set of n encrypted documents, D˜=d˜1,d˜2,…,d˜n.T: The set of m topics, T=t1,t2,…,tm.W: The dictionary contains h keywords, W=w1,w2,…,wh.Ω: The document vector matrix is obtained by SBERT training.Ω′: The document vector matrix after dimension reduction.Φ: The n×m-dimensional document topic association matrix (DTA-matrix).Φ˜: The n×m-dimensional encrypted DTA-matrix which is the encrypted index.Θ: The h×m-dimensional keyword topic association matrix (KTA-matrix).PD: The m-dimensional topic probability vector.PW: The h-dimensional keyword probability vector.Q: The ranked search with multiple queried keywords, Q=w1,w2,…,wp⊆W, where wi is the i the keyword in W.VQ: The m-dimensional plaintext query vector.V˜Q: The m-dimensional encrypted query vector of VQ.TD: The trapdoor of the query.


### 3.2. BERT Model and Sentence-BERT Model

Bidirectional Encoder Representations from Transformers (BERT) [43] has set a new state-of-the-art performance on sentence-pair regression tasks, such as semantic textual similarity (STS). BERT uses a cross-encoder, two sentences are passed to the transformer network and the target value is predicted. However, this setup is unsuitable for various pair regression tasks due to huge computational overhead. A common method to solve clustering and semantic search is to map each sentence to a vector space so that semantically similar sentences are close. Researchers have begun to input a single sentence into BERT and to derive fixed-size sentence embeddings. This approach produces quite bad sentence embeddings. Sentence-BERT (SBERT) adds a pooling operation to the output of BERT to generate a fixed-size sentence embedding vector. In Ref. [44], three pooling strategies are adopted for comparison: (1) Using the output of the CLS-token; (2) Computing the mean of all output vectors (MEAN-strategy); (3) Computing a max-over-time of the output vectors (MAX-strategy). Among of them, MEAN-strategy has the best effect. So in Ref. [44], MEAN-strategy is used as the default configuration.In order to be able to fine-tune BERT/RoBERTa, SBERT uses the Siamese and triplet networks to update the weight parameters, so that the generated sentence vector has semantic information. The embedding vectors’ distance of sentences with similar semantics is closer, so it can be used for similarity calculation (Cosine similarity, Manhattan Distance, Euclidean Distance). When classification is used as the objective function, the structure of SBERT is shown in Figure1.Figure 1
SBERT model with classification.


### 3.3. Uniform Manifold Approximation and Projection

Uniform Manifold Approximation and Projection (UMAP) [46] is a novel manifold learning technique for dimension reduction. UMAP is constructed based on the theoretical framework of Riemannian geometry and algebraic topology, which makes it a scalable algorithm used for real-world data. The UMAP algorithm is competitive with the t-SNE algorithm in terms of visualization quality and retains more global structure with excellent runtime performance. In addition, UMAP has no computational limitations on the embedding dimension.


### 3.4. Hierarchical Density-Based Spatial Clustering of Applications with Noise

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a density-based spatial clustering algorithm. The algorithm divides the regions with sufficient density into clusters, and finds clusters of arbitrary shapes in the noisy spatial database. It defines the clusters as the largest collection of densely connected points. Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) [47] extends DBSCAN to a hierarchical clustering algorithm. The difference from traditional DBSCAN is that HDBSCAN can handle clustering problems with different densities. HDBSCAN defines the distance between the sample point x and the k-th nearest neighbor sample point as the core distance, which is expressed as follows:(1)corekx=dx,Nkx.The mutual reach distance of two sample points is defined as follows:(2)dmra,b=maxcoreka,corekb,da,b.HDBSCAN provides a method to generate soft cluster membership vector for each sample point. The method not only considers the distance from the point to the cluster but also considers the outlier value of the point relative to each other. The generated vector can be interpretable as a probability of being a member of that cluster.


### 3.5. Hadamard Product

Assuming that two matricesA,B∈ℝm×n and A=aij, B=bij. The Hadamard Product between A and B is denoted as A°B, which is obtained by equation (3).(3)A°B=a11b11a12b12⋯a1nb1na21b21a22b22⋯a2nb2n⋮⋮⋮am1bm1am2bm2⋯amnbmn,where ° is the Hadamard operator. The result of A°B is also a m×n-dimensional matrix.


### 3.6. Relevance Score Measurement

The relevance score between a pair of documents or between a document and a ranked search is calculated by performing the inner product of the corresponding vectors. Assuming thatp and q are two n-dimensional vectors, the relevance score between p and q is shown in equation (4),(4)Scorep,q=p·q=∑i=1npi×pi.In this paper, both the document vectors and the query vectors contain topic semantic information, thus the inner product of two vectors is a semantic relevance score between a document and a ranked search.


### 3.7. Secure Inner Product Operation

The secure inner product is implemented by a homomorphic matrix encryption scheme proposed in Ref. [11]. We assume that p and q are two n-dimensional vectors, and M is a random n×n invertible matrix used as a secure key. The encrypted vectors of p and q are denoted as p˜ and q˜, respectively, where p˜=MT·p and q˜=M−1·q. The inner product of p and q is equal to the inner product of p˜·q˜, i.e., p˜·q˜ = p·q. The proof is shown in equation (5). It indicates that we can get the inner product of two vectors without knowing their plaintext.(5)p˜·q˜=MTpT·M−1q=pTMM−1q=p·q.


## 3.1. Notations

D: The set of n plaintext documents, D=d1,d2,…,dn.D˜: The set of n encrypted documents, D˜=d˜1,d˜2,…,d˜n.T: The set of m topics, T=t1,t2,…,tm.W: The dictionary contains h keywords, W=w1,w2,…,wh.Ω: The document vector matrix is obtained by SBERT training.Ω′: The document vector matrix after dimension reduction.Φ: The n×m-dimensional document topic association matrix (DTA-matrix).Φ˜: The n×m-dimensional encrypted DTA-matrix which is the encrypted index.Θ: The h×m-dimensional keyword topic association matrix (KTA-matrix).PD: The m-dimensional topic probability vector.PW: The h-dimensional keyword probability vector.Q: The ranked search with multiple queried keywords, Q=w1,w2,…,wp⊆W, where wi is the i the keyword in W.VQ: The m-dimensional plaintext query vector.V˜Q: The m-dimensional encrypted query vector of VQ.TD: The trapdoor of the query.


## 3.2. BERT Model and Sentence-BERT Model

Bidirectional Encoder Representations from Transformers (BERT) [43] has set a new state-of-the-art performance on sentence-pair regression tasks, such as semantic textual similarity (STS). BERT uses a cross-encoder, two sentences are passed to the transformer network and the target value is predicted. However, this setup is unsuitable for various pair regression tasks due to huge computational overhead. A common method to solve clustering and semantic search is to map each sentence to a vector space so that semantically similar sentences are close. Researchers have begun to input a single sentence into BERT and to derive fixed-size sentence embeddings. This approach produces quite bad sentence embeddings. Sentence-BERT (SBERT) adds a pooling operation to the output of BERT to generate a fixed-size sentence embedding vector. In Ref. [44], three pooling strategies are adopted for comparison: (1) Using the output of the CLS-token; (2) Computing the mean of all output vectors (MEAN-strategy); (3) Computing a max-over-time of the output vectors (MAX-strategy). Among of them, MEAN-strategy has the best effect. So in Ref. [44], MEAN-strategy is used as the default configuration.In order to be able to fine-tune BERT/RoBERTa, SBERT uses the Siamese and triplet networks to update the weight parameters, so that the generated sentence vector has semantic information. The embedding vectors’ distance of sentences with similar semantics is closer, so it can be used for similarity calculation (Cosine similarity, Manhattan Distance, Euclidean Distance). When classification is used as the objective function, the structure of SBERT is shown in Figure1.Figure 1
SBERT model with classification.


## 3.3. Uniform Manifold Approximation and Projection

Uniform Manifold Approximation and Projection (UMAP) [46] is a novel manifold learning technique for dimension reduction. UMAP is constructed based on the theoretical framework of Riemannian geometry and algebraic topology, which makes it a scalable algorithm used for real-world data. The UMAP algorithm is competitive with the t-SNE algorithm in terms of visualization quality and retains more global structure with excellent runtime performance. In addition, UMAP has no computational limitations on the embedding dimension.


## 3.4. Hierarchical Density-Based Spatial Clustering of Applications with Noise

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) is a density-based spatial clustering algorithm. The algorithm divides the regions with sufficient density into clusters, and finds clusters of arbitrary shapes in the noisy spatial database. It defines the clusters as the largest collection of densely connected points. Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) [47] extends DBSCAN to a hierarchical clustering algorithm. The difference from traditional DBSCAN is that HDBSCAN can handle clustering problems with different densities. HDBSCAN defines the distance between the sample point x and the k-th nearest neighbor sample point as the core distance, which is expressed as follows:(1)corekx=dx,Nkx.The mutual reach distance of two sample points is defined as follows:(2)dmra,b=maxcoreka,corekb,da,b.HDBSCAN provides a method to generate soft cluster membership vector for each sample point. The method not only considers the distance from the point to the cluster but also considers the outlier value of the point relative to each other. The generated vector can be interpretable as a probability of being a member of that cluster.


## 3.5. Hadamard Product

Assuming that two matricesA,B∈ℝm×n and A=aij, B=bij. The Hadamard Product between A and B is denoted as A°B, which is obtained by equation (3).(3)A°B=a11b11a12b12⋯a1nb1na21b21a22b22⋯a2nb2n⋮⋮⋮am1bm1am2bm2⋯amnbmn,where ° is the Hadamard operator. The result of A°B is also a m×n-dimensional matrix.


## 3.6. Relevance Score Measurement

The relevance score between a pair of documents or between a document and a ranked search is calculated by performing the inner product of the corresponding vectors. Assuming thatp and q are two n-dimensional vectors, the relevance score between p and q is shown in equation (4),(4)Scorep,q=p·q=∑i=1npi×pi.In this paper, both the document vectors and the query vectors contain topic semantic information, thus the inner product of two vectors is a semantic relevance score between a document and a ranked search.


## 3.7. Secure Inner Product Operation

The secure inner product is implemented by a homomorphic matrix encryption scheme proposed in Ref. [11]. We assume that p and q are two n-dimensional vectors, and M is a random n×n invertible matrix used as a secure key. The encrypted vectors of p and q are denoted as p˜ and q˜, respectively, where p˜=MT·p and q˜=M−1·q. The inner product of p and q is equal to the inner product of p˜·q˜, i.e., p˜·q˜ = p·q. The proof is shown in equation (5). It indicates that we can get the inner product of two vectors without knowing their plaintext.(5)p˜·q˜=MTpT·M−1q=pTMM−1q=p·q.


## 4. Model and Problem Statement

### 4.1. System Model

The system considered in this paper is the same as Refs. [14, 20]. As shown in Figure 2, the system model in this paper involves three different entities: data owner (DO), data user (DU), and cloud server (CS). They collaborate as follows:(1)
DO owns a collection of documentsD. In our scheme, DO first applies the SBERT training [44] on D to generate the document embedding vectors Ω1,Ω2,…,Ωn. DO uses the UMAP algorithm to reduce the dimensionality of the document embedding vectors to generate Ω′1,Ω′2,…,Ω′n. According to the document embedding vectors Ω′1,Ω′2,…,Ω′n, DO performs the HDBSCAN algorithm on D to generate a soft membership vector for each document, which is treated as the topic vector. These topic vectors form the document topic association matrix (DTA-matrix) Φ. Then, DO generates keyword topic association matrix (KTA-matrix) Θ according to the TTF-ITF model. After that, DO encrypts the document set D and the DTA-matrix Φ into ciphertext, D˜ and Φ˜. Φ˜ is a secure and searchable index of encrypted documents. At last, DO outsources D˜ and Φ˜ to CS.(2)
DU is a user authorized to perform searches on documents of DO. Once a multi-keyword searchQ is started, DU generates a trapdoor V˜Q of Q. Then, V˜Q is submitted to CS as the search command. When DO receives a search result from CS, he/she decrypts the result with the secret key shared with DO to obtain the plaintext search result.(3)
CS provides storage and computation services for users. In our scheme, CS stores the encrypted documentsD˜ and the secure index Φ˜ outsourced by DO. Upon receiving a trapdoor V˜Q from DU, CS processes the ranked search over the encrypted index Φ˜. After obtaining the search result in ciphertext, CS returns it to DU and gets ready for the next search request.Figure 2
System model.


### 4.2. Ranked Search Model

In this paper, a ranked search is conducted to obtain the ranked top-k documents from D which has the k highest relevance scores to a search request. Formally, a ranked search is defined as follows:(6)Query=D,Q,k,where Q=w1,w2,…,wp are the queried keywords from W and k is the number of requested documents, k≪n. For simplicity, we use Q to represent a search. Assuming that R is the ranked search result of Q, then we have:(7)R=k∧∀di,djdi∈R∧dj∈D−R,⟶Φi·VQ>Φj·VQ,where VQ is the query topic vector of Q, and Φi and Φj are the document topic vectors of di and dj, respectively.


### 4.3. Security definition

The security definition of our scheme is realized through simulation games. For simplicity,Π is used to represent the scheme. A and S are the adversary and the simulator, respectively. Specifically, we designed two games involving PPT (Probabilistic Polynomial-Time) A, namely RealAΠλ and IdealA,SΠλ. The first game is the execution of the scheme, and the second game is the S simulation using the leakage function ℱΠ in the plan. If A cannot distinguish between the output of RealAΠλ and IdealA,SΠλ, the scheme is ℱ-adaptively secure. The detailed description of the simulated games can be found in Ref. [48]. ℱΠ is a set of leak functions whose formal definition is described in the Security Analysis section. The security definition is shown in Definition 1.Definition 1.
A schemeΠ is ℱ-adaptively secure if for an adversary A, there exists a simulator S such that(8)PrRealAΠλ=1−PrIdealA,SΠλ=1≤neglλ,where neglλ is a negligible function.


### 4.4. Design Goals

Given a search requestQ, the proposed ranked search scheme has the following design goals:Multi-keywords ranked search. In this scheme, CS can return the k document that is the most relevant to the query and has the highest ranking in the form of ciphertext.Search efficiency and effectiveness. The scheme realizes efficient and accurate search by using special tree-based index and efficient search algorithm.Privacy-preserving. The scheme is designed to prevent CS from learning additional information about the document set, index tree, and query. Specific requirements are as follows:Document confidentiality. The plaintext of the documents should be protected.Index confidentiality and query confidentiality. The index and queried keywords should be protected.Trapdoor unlinkability [20]. CS should not determine whether two trapdoors are generated from the same query.Keyword privacy. CS should not identify specific keywords in documents or trapdoors.


## 4.1. System Model

The system considered in this paper is the same as Refs. [14, 20]. As shown in Figure 2, the system model in this paper involves three different entities: data owner (DO), data user (DU), and cloud server (CS). They collaborate as follows:(1)
DO owns a collection of documentsD. In our scheme, DO first applies the SBERT training [44] on D to generate the document embedding vectors Ω1,Ω2,…,Ωn. DO uses the UMAP algorithm to reduce the dimensionality of the document embedding vectors to generate Ω′1,Ω′2,…,Ω′n. According to the document embedding vectors Ω′1,Ω′2,…,Ω′n, DO performs the HDBSCAN algorithm on D to generate a soft membership vector for each document, which is treated as the topic vector. These topic vectors form the document topic association matrix (DTA-matrix) Φ. Then, DO generates keyword topic association matrix (KTA-matrix) Θ according to the TTF-ITF model. After that, DO encrypts the document set D and the DTA-matrix Φ into ciphertext, D˜ and Φ˜. Φ˜ is a secure and searchable index of encrypted documents. At last, DO outsources D˜ and Φ˜ to CS.(2)
DU is a user authorized to perform searches on documents of DO. Once a multi-keyword searchQ is started, DU generates a trapdoor V˜Q of Q. Then, V˜Q is submitted to CS as the search command. When DO receives a search result from CS, he/she decrypts the result with the secret key shared with DO to obtain the plaintext search result.(3)
CS provides storage and computation services for users. In our scheme, CS stores the encrypted documentsD˜ and the secure index Φ˜ outsourced by DO. Upon receiving a trapdoor V˜Q from DU, CS processes the ranked search over the encrypted index Φ˜. After obtaining the search result in ciphertext, CS returns it to DU and gets ready for the next search request.Figure 2
System model.


## 4.2. Ranked Search Model

In this paper, a ranked search is conducted to obtain the ranked top-k documents from D which has the k highest relevance scores to a search request. Formally, a ranked search is defined as follows:(6)Query=D,Q,k,where Q=w1,w2,…,wp are the queried keywords from W and k is the number of requested documents, k≪n. For simplicity, we use Q to represent a search. Assuming that R is the ranked search result of Q, then we have:(7)R=k∧∀di,djdi∈R∧dj∈D−R,⟶Φi·VQ>Φj·VQ,where VQ is the query topic vector of Q, and Φi and Φj are the document topic vectors of di and dj, respectively.


## 4.3. Security definition

The security definition of our scheme is realized through simulation games. For simplicity,Π is used to represent the scheme. A and S are the adversary and the simulator, respectively. Specifically, we designed two games involving PPT (Probabilistic Polynomial-Time) A, namely RealAΠλ and IdealA,SΠλ. The first game is the execution of the scheme, and the second game is the S simulation using the leakage function ℱΠ in the plan. If A cannot distinguish between the output of RealAΠλ and IdealA,SΠλ, the scheme is ℱ-adaptively secure. The detailed description of the simulated games can be found in Ref. [48]. ℱΠ is a set of leak functions whose formal definition is described in the Security Analysis section. The security definition is shown in Definition 1.Definition 1.
A schemeΠ is ℱ-adaptively secure if for an adversary A, there exists a simulator S such that(8)PrRealAΠλ=1−PrIdealA,SΠλ=1≤neglλ,where neglλ is a negligible function.


## 4.4. Design Goals

Given a search requestQ, the proposed ranked search scheme has the following design goals:Multi-keywords ranked search. In this scheme, CS can return the k document that is the most relevant to the query and has the highest ranking in the form of ciphertext.Search efficiency and effectiveness. The scheme realizes efficient and accurate search by using special tree-based index and efficient search algorithm.Privacy-preserving. The scheme is designed to prevent CS from learning additional information about the document set, index tree, and query. Specific requirements are as follows:Document confidentiality. The plaintext of the documents should be protected.Index confidentiality and query confidentiality. The index and queried keywords should be protected.Trapdoor unlinkability [20]. CS should not determine whether two trapdoors are generated from the same query.Keyword privacy. CS should not identify specific keywords in documents or trapdoors.


## 5. Secure Search Scheme Based on the Sentence-BERT Model

In this section, we propose a semantic-aware multi-keyword ranked search scheme based on the SBERT model (SBERT-SRSE). We first present the framework of our scheme shown in Figure3. Two modules are contained in the framework of SBERT-SRSE, the setup module and the search module, respectively. In the setup module, DO performs four algorithms to build the system, which are GenKey, GenMatrix, GenPB, and EncData. DO outsources the generated encrypted index and documents to CS, and shares the security keys and the necessary information for generating trapdoor with DU. When a ranked search is started, the search module will be activated between DU and CS. In the search module, GenTrapdoor is executed to generate trapdoor, SASearch is executed to return search results. We give the detailed description of the algorithms in the two modules in the following two subsections.Figure 3
The framework of the proposed schemes.


### 5.1. Algorithms in Setup Module

SK⟵GenKey(1ln). DO generates the secured key S​K=S,M1,M2,g, where S is an n-bit random vector, M1 and M2 are two random m×m invertible matrices, and g is the key for symmetric encryption. S​K is only shared between DO and DU while CS does not know the information.Φ,Θ⟵GenMatrix(D). In order to vectorize the documents and reduce the semantic loss caused by the documents conversion process, DO uses the SBERT model to generate the document vector matrix Ω. Then, DO generates the document topic association matrix (DTA-matrix) Φ and keyword topic association matrix (KTA-matrix) Θ. The detailed steps are given as follows:(1)
DO takes the document setD as the input of the SBERT model, and the SBERT model returns the document vector matrix Ω, where Ωi represents the document vector of the document di.(2)
Before generating the DTA-matrix, DO uses the UMAP to reduce the dimension of document vectors, because the HDBSCAN clustering algorithm is prone to suffer the dimensional curse. At the same time, using the UMAP to reduce dimension can also bring some other benefits. On the one hand, it can reduce the computational complexity, reduce the amount of calculation, and reduce the amount of memory used. On the other hand, in the process of manifold dimension reduction, more local semantic features can be found.(3)
DO uses the document vectors after dimension reductionΩ′1,Ω′2,…,Ω′n as the input of the clustering algorithm HDBSCAN. A soft membership vector is generated for each document during the clustering process, we treat each cluster as a topic and finally DTA-matrix Φ is output. The matrix describes the relevance between documents and topics. Assuming that there are n documents and m topics in D and T, respectively. Φ is a n×m-dimensional matrix. The row vector Φi in Φ is the document topic vector of di and Φij represents the probability that document di belongs to topic tj.(4)
In order to be able to compare the importance of keywords between topics, we propose a model called Topic-Term Frequency-Inverse Topic Frequency. Definition 2. Topic-Term Frequency. The frequency of keywordwi in topic tj is denoted by ttfwi,tj.(9)ttfwi,tj=ni,j∑knk,j,where ni,j is the number of occurrences of keyword wi in topic tj, ∑knk,j is the total number of occurrences of all keywords in topic tj.Definition 2.
Inverse Topic Frequency. Inverse topic frequency ofwi is denoted by itfwi.(10)itfwi=logT1+j:wi∈tj,where j:wi∈tj represents the number of topics containing the keyword wi.Definition 3.
Topic-Term Frequency-Inverse Topic Frequency. The topic-term frequency-inverse topic frequency (TTF-ITF) score betweenwi and tj is denoted by ttf-itfwi,tj. It measures the importance of wi in tj.(11)ttf−itfwi,tj=ttfwi,tj·itfwi.
The higher the TTF-ITF value ofwi in tj is, the higher the importance of wi in tj. According to equation (11), the KTA-matrix is generated. The KTA-matrix Θ describes the relevance between keywords and topics. The row vector Θi in Θ is the keyword topic vector of wi and Θij represents the importance of the keyword wi to the topic tj.
(PD,PW)⟵GenPB(Φ,Θ). DO generates the topic probability vector PD and the keyword probability vector PW from Φ and Θ.(1)
Assuming that each documentdi∈D is equally important, we can further derive the following probability:(12)PD=1n·∑j=1nΦj,whereΦj is the j th row vector in Φ. PD is the topic probability vector, each dimension of PD stores the prior probability of the document d belonging to topic t∈T.(2)
DO generates the keyword probability vectorPW, each dimension of which records the prior belief of each keyword in W appearing in D. The calculation of PW is shown in equation (13).(13)PW=PD·ΘT,
(D˜,Φ˜)⟵EncData(D,Φ, SK). DO encrypts Φ and D into D.˜ and Φ˜. DO first splits the vectors in Φ with the n-bit random vector S. Given a vector V, V is split into two n-dimension vectors V′,V″ following formula (14).(14)V′i=V″i=Vi,Si=0,V′i+V″i=Vi,Si=1.
Then, DO uses the secure matricesM1 and M2 in S​K to encrypt them into the ciphertext V˜,(15)V˜=V˜′,V˜″=V′·M1T,V″·M2T.
When all vectors inΦ have been encrypted, the encrypted index Φ˜ is generated.
Finally, DO generates the encrypted documents setD˜ with the key g in SK.
After the setup module is finished,Φ˜ and D˜ are outsourced to CS, where Φ˜ is used as the secure index for multi-keyword ranked searches. Meanwhile, DO shares SK, Θ, PD, and PW with DU.


### 5.2. Algorithms in Search Module

V˜Q⟵GenTrapdoor(Q,Θ,PD,PW). When starting a ranked search Q=w1,w2,…,wp where wp is the p th keyword in W, DU generates the corresponding query topic vector VQ and uses the security key to encrypt VQ to get the trapdoor TD=V˜Q,k. We describe in detail the generation process of trapdoor as follows:(1)
DU generates anm-dimensional query topic vector from equation (16),(16)VQ=∑wi∈QPD°ΘiQ·PWi,whereVQi represents the probability that the topic intention of Q belongs to the topic ti.(2)
DU dividesVQ into two random vectors VQ′,VQ″ with the n-bit random vector S in S​K. The split rule is shown in formula (17).(17)VQ′i+VQ″i=VQiSi=0,VQ′i=VQ″i=VQiSi=1.(3)
DU encrypts the dividedVQ=VQ′,VQ″ into V˜Q  = \{V˜Q′, V˜Q′′\} using secure matrices M1 and M2 in S​K, as shown in equation (18).(18)V˜Q=V˜Q′,V˜Q′′=VQ′·M1−1,VQ″·M2−1.When the trapdoorT​D​=V˜Q,k​ is generated, it is submitted to CS as a search instruction.R⟵SASearch (Φ˜,TD). CS receives the trapdoor TD and performs the secured ranked search by conducting the secure inner products between V˜Q and the encrypted document topic vectors Φ˜1,Φ˜2,…,Φ˜n. The topic semantic relevance scores between the query and the encrypted documents are calculated by equation (19),(19)ScoreVQ′·M1−1,VQ″·M2−1,Φ′i·M1T,Φ″i·M2T,=VQ′·M1−1·Φ′i·M1TT+VQ″·M2−1·Φ″i·M2TT,=VQ′·Φ′i+VQ″·Φ″i,=VQ·Φi.The encrypted documents having the highestk scores are obtained and returned to DU. After receiving the search result, DU uses the secure key g which is shared with DO to decrypt the encrypted documents to obtain the plaintext ranked search result.


## 5.1. Algorithms in Setup Module

SK⟵GenKey(1ln). DO generates the secured key S​K=S,M1,M2,g, where S is an n-bit random vector, M1 and M2 are two random m×m invertible matrices, and g is the key for symmetric encryption. S​K is only shared between DO and DU while CS does not know the information.Φ,Θ⟵GenMatrix(D). In order to vectorize the documents and reduce the semantic loss caused by the documents conversion process, DO uses the SBERT model to generate the document vector matrix Ω. Then, DO generates the document topic association matrix (DTA-matrix) Φ and keyword topic association matrix (KTA-matrix) Θ. The detailed steps are given as follows:(1)
DO takes the document setD as the input of the SBERT model, and the SBERT model returns the document vector matrix Ω, where Ωi represents the document vector of the document di.(2)
Before generating the DTA-matrix, DO uses the UMAP to reduce the dimension of document vectors, because the HDBSCAN clustering algorithm is prone to suffer the dimensional curse. At the same time, using the UMAP to reduce dimension can also bring some other benefits. On the one hand, it can reduce the computational complexity, reduce the amount of calculation, and reduce the amount of memory used. On the other hand, in the process of manifold dimension reduction, more local semantic features can be found.(3)
DO uses the document vectors after dimension reductionΩ′1,Ω′2,…,Ω′n as the input of the clustering algorithm HDBSCAN. A soft membership vector is generated for each document during the clustering process, we treat each cluster as a topic and finally DTA-matrix Φ is output. The matrix describes the relevance between documents and topics. Assuming that there are n documents and m topics in D and T, respectively. Φ is a n×m-dimensional matrix. The row vector Φi in Φ is the document topic vector of di and Φij represents the probability that document di belongs to topic tj.(4)
In order to be able to compare the importance of keywords between topics, we propose a model called Topic-Term Frequency-Inverse Topic Frequency. Definition 2. Topic-Term Frequency. The frequency of keywordwi in topic tj is denoted by ttfwi,tj.(9)ttfwi,tj=ni,j∑knk,j,where ni,j is the number of occurrences of keyword wi in topic tj, ∑knk,j is the total number of occurrences of all keywords in topic tj.Definition 2.
Inverse Topic Frequency. Inverse topic frequency ofwi is denoted by itfwi.(10)itfwi=logT1+j:wi∈tj,where j:wi∈tj represents the number of topics containing the keyword wi.Definition 3.
Topic-Term Frequency-Inverse Topic Frequency. The topic-term frequency-inverse topic frequency (TTF-ITF) score betweenwi and tj is denoted by ttf-itfwi,tj. It measures the importance of wi in tj.(11)ttf−itfwi,tj=ttfwi,tj·itfwi.
The higher the TTF-ITF value ofwi in tj is, the higher the importance of wi in tj. According to equation (11), the KTA-matrix is generated. The KTA-matrix Θ describes the relevance between keywords and topics. The row vector Θi in Θ is the keyword topic vector of wi and Θij represents the importance of the keyword wi to the topic tj.
(PD,PW)⟵GenPB(Φ,Θ). DO generates the topic probability vector PD and the keyword probability vector PW from Φ and Θ.(1)
Assuming that each documentdi∈D is equally important, we can further derive the following probability:(12)PD=1n·∑j=1nΦj,whereΦj is the j th row vector in Φ. PD is the topic probability vector, each dimension of PD stores the prior probability of the document d belonging to topic t∈T.(2)
DO generates the keyword probability vectorPW, each dimension of which records the prior belief of each keyword in W appearing in D. The calculation of PW is shown in equation (13).(13)PW=PD·ΘT,
(D˜,Φ˜)⟵EncData(D,Φ, SK). DO encrypts Φ and D into D.˜ and Φ˜. DO first splits the vectors in Φ with the n-bit random vector S. Given a vector V, V is split into two n-dimension vectors V′,V″ following formula (14).(14)V′i=V″i=Vi,Si=0,V′i+V″i=Vi,Si=1.
Then, DO uses the secure matricesM1 and M2 in S​K to encrypt them into the ciphertext V˜,(15)V˜=V˜′,V˜″=V′·M1T,V″·M2T.
When all vectors inΦ have been encrypted, the encrypted index Φ˜ is generated.
Finally, DO generates the encrypted documents setD˜ with the key g in SK.
After the setup module is finished,Φ˜ and D˜ are outsourced to CS, where Φ˜ is used as the secure index for multi-keyword ranked searches. Meanwhile, DO shares SK, Θ, PD, and PW with DU.


## 5.2. Algorithms in Search Module

V˜Q⟵GenTrapdoor(Q,Θ,PD,PW). When starting a ranked search Q=w1,w2,…,wp where wp is the p th keyword in W, DU generates the corresponding query topic vector VQ and uses the security key to encrypt VQ to get the trapdoor TD=V˜Q,k. We describe in detail the generation process of trapdoor as follows:(1)
DU generates anm-dimensional query topic vector from equation (16),(16)VQ=∑wi∈QPD°ΘiQ·PWi,whereVQi represents the probability that the topic intention of Q belongs to the topic ti.(2)
DU dividesVQ into two random vectors VQ′,VQ″ with the n-bit random vector S in S​K. The split rule is shown in formula (17).(17)VQ′i+VQ″i=VQiSi=0,VQ′i=VQ″i=VQiSi=1.(3)
DU encrypts the dividedVQ=VQ′,VQ″ into V˜Q  = \{V˜Q′, V˜Q′′\} using secure matrices M1 and M2 in S​K, as shown in equation (18).(18)V˜Q=V˜Q′,V˜Q′′=VQ′·M1−1,VQ″·M2−1.When the trapdoorT​D​=V˜Q,k​ is generated, it is submitted to CS as a search instruction.R⟵SASearch (Φ˜,TD). CS receives the trapdoor TD and performs the secured ranked search by conducting the secure inner products between V˜Q and the encrypted document topic vectors Φ˜1,Φ˜2,…,Φ˜n. The topic semantic relevance scores between the query and the encrypted documents are calculated by equation (19),(19)ScoreVQ′·M1−1,VQ″·M2−1,Φ′i·M1T,Φ″i·M2T,=VQ′·M1−1·Φ′i·M1TT+VQ″·M2−1·Φ″i·M2TT,=VQ′·Φ′i+VQ″·Φ″i,=VQ·Φi.The encrypted documents having the highestk scores are obtained and returned to DU. After receiving the search result, DU uses the secure key g which is shared with DO to decrypt the encrypted documents to obtain the plaintext ranked search result.


## 6. Enhanced Search Scheme

The SASearch algorithm in SBERT-SRSE needs to perform the inner products in turn between the encrypted document topic vectors and the trapdoor, which has a linear time complexity. To improve the efficiency of the ranked searches, we first construct a semantic-related document list, and then use the method in Ref. [20] to construct the index tree TS-tree. We propose a TS-tree-based search algorithm at the same time. The enhanced scheme is denoted as SBERT-ESRSE.


### 6.1. Semantic-Related Document List

To construct the semantic-related document list, we classify each document into a certain topic. The classification is based on document topic vectors, where each dimension in the document topic vector represents the probability that the document is related to the topic. We classify the documents into topics that are most relevant to them. We traverse the topict1,t2,…,tm and add the documents belonging to it to the list. When all topics are traversed, a semantic-related document topic list ℒ=d1,d2,…,dn is generated. Usually in ℒ, the closer the distance between the two documents, the more similar their topic semantics.


### 6.2. TS-Tree-Based Index Construction Algorithm

In order to improve search efficiency, we use a binary tree to replace the original index. DO builds index tree based on semantic-related document listℒ.Definition 4.
A nodeu of TS-tree is defined as a four-element tuple:(20)u=id,pl,pr,dvec,where id is the identifier of the document, pl points to the left child of the node, pr points to the right child of the node, and dvec is the vector stored in the node.
We give a detailed description of the different types of nodes in the TS-tree.ifu is a leaf node, u.pl=u.pr=∅, u.id represents the corresponding document di’ s id i, u.dvec represents di’ s topic vector.ifu is an internal node, u.pl and u.pr correspond to the left and right child nodes of u, respectively. u.id=∅, u.dvec represents the filtering vector of node u, u.dveci=maxu.pl.dveci,u.pr.dveci,i=1,2,…,m.
After using TS-tree as the index, the search efficiency is increased in proportion to the height of the tree in the tree index. The detailed algorithm of TS-tree construction is described in Algorithm1. An example of TS-tree construction in the plaintext state is given in Figure 4.
Algorithm 1: BuildTSTree(ℒ, Φ).
Require: the semantic-related document list ℒ and DTA-matrix Φ;Ensure: the TS-tree I;(1)
Initialize the current nodes listC List = ∅ and the temporary nodes list T List = ∅;(2)
for each di∈ℒdo(3)
Create a leaf nodeu for di, where u.id=i, u.pl = u.pr = ∅, u.dvec = Φi;(4)
Appendu to C List in order;(5)
end for(6)
whileC List>=0do(7)
ifC List>1then(8)
Fetch the first two nodesu1andu2fromC Listand generate a parent nodeuforu1andu2, whereu.id = ∅,u.pl = u1,u.pr = u2, andu.dvecj = maxu1.dvecj,u2.dvecj, for eachj = 1,⋯,m;(9)
AppendutoT List;(10)
else ifC List=1then(11)
Fetch the only one node fromC Listand append it toT List;(12)
else ifC List=0then(13)
Move all the nodes ofT ListtoC Listin order;(14)
end if(15)
end while(16)
return the only node left inC Listwhich the root of the TS-treeI;Figure 4
An example of TS-tree whereℒ = d1,d3,d4,d2,d6,d5 and the number of topics is m = 4. This figure also shows an example of search process, in which query vector VQ = (0, 0.8, 0, 0.5). We set k = 2 with the meaning that two documents will be returned to the DU in this example. According to the TSearch algorithm, the search starts with the root node and reaches the first leaf node u4,1 through the red path. The semantic relevance score between VQ and d1 is Score(VQ, u4,1.dvec) = 0.56, d1.dvec is appended to search result R. After that, the search reaches u4,2 through the blue path, where Score(VQ, u4,2.dvec) = 0.48, d3 is appended to R and the filtering threshold ζ = 0.48. Then, the search reaches u3,2 through the green path and the node u3,2 and its child nodes are filtered because Score(VQ, u3,2.dvec) = 0.1 <ζ. Then, the search reaches u3,3 through the yellow path, where Score(VQ, u3,3.dvec) = 0.53 >ζ, d6 is appended to (R) At this time, R is sorted, then d3 is deleted and ζ is set to 0.53. Finally, the node u 3,4 is filtered because the score Score(VQ, u3,4.dvec) = 0.45 <ζ. CS returns R =  d1,d6 to DU.


### 6.3. TS-Tree-Based Search Algorithm

When CS receives a search request, CS performs the algorithm on the TS-tree to obtain the search result listR with the largest relevance scores. In addition, we need to keep R ranked in descending order and sorted when a new document is added. The relevance score calculation between trapdoor and encrypted document vectors is described in SBERT-SRSE. In the search process, CS uses the filtering threshold to reduce the number of inner product operations. Assuming that the filtering threshold is ζ and the search request is VQ, when the search reaches node u,ifζ< Score(u.dvec, VQ), searching the node u and the child nodes of u.ifζ> Score(u.dvec, VQ), filtering the node u and the child nodes of u.In addition,ζ changes dynamically during searches, when searches reach the leaf node u of TS-tree.Algorithm 2: TSearch (V˜Q, r, ζ, k).
Require:V˜Q is search topic vector, r is root node of a TS-tree, ζ is a filtering threshold and is initialized to 0, and k is the number of requested documents;Ensure: search resultR;(1)
ifr≠∅then(2)
if Score(r.d˜vec,V˜Q)>ζthen(3)
ifris an internal node then(4)
TSearch(V˜Q,r.pl,ζ,k);(5)
TSearch(V˜Q,r.pr,ζ,k);(6)
else(7)
InsertrintoRand then R is sorted in descending order according to the semantic relevance scores between the documents and the query vector.(8)
ifR>kthen(9)
DeleteRk+1;(10)
ζ = Score(Rk.d˜vec,V˜Q);(11
end if(12)
end if(13)
end if(14)
end if(15)
returnR;The details of the search algorithm are described in Algorithm2. An example of searching TS-tree in plaintext state is given in Figure 4.


### 6.4. Algorithms in SBERT-ESRSE

In SBERT-ESRSE, the algorithmBuildTSTree is added and the original algorithms, EncData and SASearch, are improved. These algorithms are introduced as follows:I⟵BuildTSTree(ℒ,Φ). After we obtain the DTA-matrix Φ and the semantic-related document list ℒ, we build the TS-tree as plaintext I on the basis of them; the detailed procedures are shown in Algorithm 1.(D˜,I˜)⟵EncData(D,I, SK). We use TS-tree I as the index to replace the original index Φ and encrypt I with the similar encryption algorithm given as EncData(D,Φ, SK). The encrypted documents D˜ and the encrypted tree index I˜ are outsourced to CS.R⟵SASearch(I˜,T​D). When CS receives a search trapdoor, CS performs a search on the encrypted index I˜ through Algorithm 2. The encrypted TS-tree is used as a search index to improve search efficiency. In the search process, the inner product operation between the trapdoor and the encrypted vectors is the same as SASearch(Φ˜,TD), which has been given in SBERT-SRSE. The search result R is returned to DU. Then, DU decrypts documents with secure key g and gets the plaintext ranked search result.


## 6.1. Semantic-Related Document List

To construct the semantic-related document list, we classify each document into a certain topic. The classification is based on document topic vectors, where each dimension in the document topic vector represents the probability that the document is related to the topic. We classify the documents into topics that are most relevant to them. We traverse the topict1,t2,…,tm and add the documents belonging to it to the list. When all topics are traversed, a semantic-related document topic list ℒ=d1,d2,…,dn is generated. Usually in ℒ, the closer the distance between the two documents, the more similar their topic semantics.


## 6.2. TS-Tree-Based Index Construction Algorithm

In order to improve search efficiency, we use a binary tree to replace the original index. DO builds index tree based on semantic-related document listℒ.Definition 4.
A nodeu of TS-tree is defined as a four-element tuple:(20)u=id,pl,pr,dvec,where id is the identifier of the document, pl points to the left child of the node, pr points to the right child of the node, and dvec is the vector stored in the node.
We give a detailed description of the different types of nodes in the TS-tree.ifu is a leaf node, u.pl=u.pr=∅, u.id represents the corresponding document di’ s id i, u.dvec represents di’ s topic vector.ifu is an internal node, u.pl and u.pr correspond to the left and right child nodes of u, respectively. u.id=∅, u.dvec represents the filtering vector of node u, u.dveci=maxu.pl.dveci,u.pr.dveci,i=1,2,…,m.
After using TS-tree as the index, the search efficiency is increased in proportion to the height of the tree in the tree index. The detailed algorithm of TS-tree construction is described in Algorithm1. An example of TS-tree construction in the plaintext state is given in Figure 4.
Algorithm 1: BuildTSTree(ℒ, Φ).
Require: the semantic-related document list ℒ and DTA-matrix Φ;Ensure: the TS-tree I;(1)
Initialize the current nodes listC List = ∅ and the temporary nodes list T List = ∅;(2)
for each di∈ℒdo(3)
Create a leaf nodeu for di, where u.id=i, u.pl = u.pr = ∅, u.dvec = Φi;(4)
Appendu to C List in order;(5)
end for(6)
whileC List>=0do(7)
ifC List>1then(8)
Fetch the first two nodesu1andu2fromC Listand generate a parent nodeuforu1andu2, whereu.id = ∅,u.pl = u1,u.pr = u2, andu.dvecj = maxu1.dvecj,u2.dvecj, for eachj = 1,⋯,m;(9)
AppendutoT List;(10)
else ifC List=1then(11)
Fetch the only one node fromC Listand append it toT List;(12)
else ifC List=0then(13)
Move all the nodes ofT ListtoC Listin order;(14)
end if(15)
end while(16)
return the only node left inC Listwhich the root of the TS-treeI;Figure 4
An example of TS-tree whereℒ = d1,d3,d4,d2,d6,d5 and the number of topics is m = 4. This figure also shows an example of search process, in which query vector VQ = (0, 0.8, 0, 0.5). We set k = 2 with the meaning that two documents will be returned to the DU in this example. According to the TSearch algorithm, the search starts with the root node and reaches the first leaf node u4,1 through the red path. The semantic relevance score between VQ and d1 is Score(VQ, u4,1.dvec) = 0.56, d1.dvec is appended to search result R. After that, the search reaches u4,2 through the blue path, where Score(VQ, u4,2.dvec) = 0.48, d3 is appended to R and the filtering threshold ζ = 0.48. Then, the search reaches u3,2 through the green path and the node u3,2 and its child nodes are filtered because Score(VQ, u3,2.dvec) = 0.1 <ζ. Then, the search reaches u3,3 through the yellow path, where Score(VQ, u3,3.dvec) = 0.53 >ζ, d6 is appended to (R) At this time, R is sorted, then d3 is deleted and ζ is set to 0.53. Finally, the node u 3,4 is filtered because the score Score(VQ, u3,4.dvec) = 0.45 <ζ. CS returns R =  d1,d6 to DU.


## 6.3. TS-Tree-Based Search Algorithm

When CS receives a search request, CS performs the algorithm on the TS-tree to obtain the search result listR with the largest relevance scores. In addition, we need to keep R ranked in descending order and sorted when a new document is added. The relevance score calculation between trapdoor and encrypted document vectors is described in SBERT-SRSE. In the search process, CS uses the filtering threshold to reduce the number of inner product operations. Assuming that the filtering threshold is ζ and the search request is VQ, when the search reaches node u,ifζ< Score(u.dvec, VQ), searching the node u and the child nodes of u.ifζ> Score(u.dvec, VQ), filtering the node u and the child nodes of u.In addition,ζ changes dynamically during searches, when searches reach the leaf node u of TS-tree.Algorithm 2: TSearch (V˜Q, r, ζ, k).
Require:V˜Q is search topic vector, r is root node of a TS-tree, ζ is a filtering threshold and is initialized to 0, and k is the number of requested documents;Ensure: search resultR;(1)
ifr≠∅then(2)
if Score(r.d˜vec,V˜Q)>ζthen(3)
ifris an internal node then(4)
TSearch(V˜Q,r.pl,ζ,k);(5)
TSearch(V˜Q,r.pr,ζ,k);(6)
else(7)
InsertrintoRand then R is sorted in descending order according to the semantic relevance scores between the documents and the query vector.(8)
ifR>kthen(9)
DeleteRk+1;(10)
ζ = Score(Rk.d˜vec,V˜Q);(11
end if(12)
end if(13)
end if(14)
end if(15)
returnR;The details of the search algorithm are described in Algorithm2. An example of searching TS-tree in plaintext state is given in Figure 4.


## 6.4. Algorithms in SBERT-ESRSE

In SBERT-ESRSE, the algorithmBuildTSTree is added and the original algorithms, EncData and SASearch, are improved. These algorithms are introduced as follows:I⟵BuildTSTree(ℒ,Φ). After we obtain the DTA-matrix Φ and the semantic-related document list ℒ, we build the TS-tree as plaintext I on the basis of them; the detailed procedures are shown in Algorithm 1.(D˜,I˜)⟵EncData(D,I, SK). We use TS-tree I as the index to replace the original index Φ and encrypt I with the similar encryption algorithm given as EncData(D,Φ, SK). The encrypted documents D˜ and the encrypted tree index I˜ are outsourced to CS.R⟵SASearch(I˜,T​D). When CS receives a search trapdoor, CS performs a search on the encrypted index I˜ through Algorithm 2. The encrypted TS-tree is used as a search index to improve search efficiency. In the search process, the inner product operation between the trapdoor and the encrypted vectors is the same as SASearch(Φ˜,TD), which has been given in SBERT-SRSE. The search result R is returned to DU. Then, DU decrypts documents with secure key g and gets the plaintext ranked search result.


## 7. Security Analysis

Before provingℱ-adaptively secure of our schemes, we provide a formal description of the leakage functions for our schemes:Definition 5.
ℱΠ  = {ℱGK, ℱSet, ℱBI, ℱGT, ℱSA}. The leakage functions in ℱΠ corresponds to the secure key generation stage, initial setting stage, index generation stage, and trapdoor generation stage in the schemes of this paper, respectively. Specifically, the leakage are described as follows:LeakSP is the search pattern leakage, which reflects the same results obtained by the same queries.LeakAP is the access pattern leakage, which are the identities of the returned encrypted documents together with the document ranking information.LeakSIP is the size pattern leakage, which are the number of encrypted documents n, the length of an encrypted document vector, and the length of a trapdoor.
The leakage functionsℱGK, ℱSet, ℱBI, and ℱGT correspond to the leakage LeakSIP, and ℱSA corresponds to the leakages LeakSP and LeakAP.Theorem 1.
The proposed schemes, SBERT-SRSE and SBERT-ESRSE, areℱ-adaptively secure with the leakage functions set ℱΠ.Proof.
We adopt a method based on simulation to prove the theorem. In the ideal game,IdealA,SΠλ, the simulator S simulates the steps in SBERT-SRSE and SBERT-ESRSE according to the given leak functions in ℱΠ. If adversary A cannot distinguish between the output of the real game and the ideal game, we can conclude that for A given ℱΠ, the proposed schemes are ℱ-adaptively secure.GameG0. The game represents the real environment RealAΠλ, thus we have(21)PrRealAΠλ=1=PrG0A=1.GameG1. The game represents the simulated environment, thus we have(22)PrIdealA,SΠλ=1=PrG1A=1.
InG1, the simulated RealAΠλ derives from G0. According to the leakages LeakSP, LeakAP, and LeakSIP, the simulator S first generates nm-dimensional random vectors Φ′=Φ′1,Φ′2,…,Φ′n as the encrypted document topic association matrix. Next, S constructs tree-based indexes on Φ′ according to the index construction algorithms in the proposed schemes. For a given query Q, S generates a m-dimensional random vector VQ′ as the trapdoor and then stores the pair (Q, VQ′) for reuse.
We prove the theorem by analyzing the indistinguishability ofG0 and G1. According to the ciphertext retrieval algorithm in the proposed schemes, the key to achieve ciphertext retrieval lies in the generation of encrypted search topic vectors and encrypted document topic vectors that support secure inner product operations, that is, the random invertible matrices M1 and M2 in key S​K are used to generate encryption vectors according to (15) and (18). Therefore, the advantage that A can distinguish G0 and G1 is equivalent to the advantage that A can crack the encryption process shown in formula (23), that is, in the known V′ And V″, by solving formula (23), the advantages of the exact solutions of M1, M2, V′˜, and V˜″ in the corresponding equations are obtained.(23)V′×M1=V′˜,V″×M2=V˜″,.
In the equations corresponding to formula (23), M1 and M2 are m×m-dimensional random invertible matrices, V′ And V″ are m-dimensional random vectors obtained from random vector S, V′˜ And V˜″ are m-dimensional encryption vectors, so the equations have 2m×m+1 unknowns and 2m known numbers. Obviously, in polynomial time, the exact solutions of M1, M2, V′˜, and V˜″ cannot be obtained in these equations. This means that the advantage of being able to distinguish between random numbers and secure inner product operations is negligible, thus(24)PrG0A=1−PrG1A=1≤neglλ.
According to formulas (21), (22), and (24), combined with Definition 1, it can be derived:(25)PrRealAΠλ=1−PrIdealA,SΠλ=1≤neglλ.
According to the security definition of the scheme in this paper (Definition1), based on the leaked function set ℱΠ in Definition 5, the schemes proposed in this paper are ℱ-adaptively secure.


## 8. Performance Analysis

In this section, we evaluate the proposed schemes SBERT-SRSE and SBERT-ESRSE and compare them with the schemes presented in Refs. [20, 40], which are denoted as TFIDF-MRSE and LDA-EMRSE. We implement these schemes by using Python 3.6 in Windows 10 with Intel Core(TM) i5-9300H. The assessment is based on two indicators. One is the semantic precision of search results; the other is the cost of search time. The data set used in the evaluation was 20 newsgroups [49], including 20 different categories of news, including a total of 11315 articles.Default parameters are summarized in Table1, where n,Q, and k are the number of documents, the number of queried keywords, and required documents, respectively.Table 1
Default parameters.
ParametersnQkValues80003100At the same time, in order to make the number of topics trained by the LDA topic model closer to the number of real topics, we set the number of topics to 20.


### 8.1. Semantic Precision Evaluation

In order to reasonably describe the semantic precision of the scheme, we assume that the query keywords come from the same category and the documents in different categories are semantically irrelevant. We evaluate the search precision of SBERT-SRSE, SBERT-ESRSE, LDA-EMRSE, and TFIDF-MRSE using the method adopted by Ref. [50], which is shown as follows:(26)P=TPTP+FP×100%,where TP and FP indicate the numbers of documents in the search result that belong or do not belong to the category of the search intent, respectively.(1)
Semantic Precision versus n. As shown in Figure 5, with the increase of the number of documents n, the semantic precision of SBERT-SRSE and LDA-EMRSE remained stable, while that of TFIDF-MRSE gradually decreased. The reason is that in SBERT-SRSE and LDA-EMRSE, semantic models are used to extract the semantic features of the documents. As the number of documents increases, the topics extracted by the semantic models better reflect the semantic features of the documents, and have no significant impact on the semantic accuracy of the search. At the same time, because the document vectors trained by the SBERT model have more semantic features than those trained by the LDA model, the semantic precision of SBERT-SRSE is higher than that of the semantic precision of LDA-EMRSE.(2)
Semantic Precision versus k. Figure 5(b) shows that the semantic precision of the three schemes gradually decreases as the number of documents required k increases. The reason for this is that as k increases, documents that are less relevant to the search intent are added to the search results, which may result in a slight decrease in the semantic precisions.(3)
Semantic Precision versusQ. Figure 5(c) shows that as the number of queried keywords Q increases, semantic precisions of SBERT-SRSE, LDA-EMRSE, and TFIDF-MRSE are increased gradually, and then tend to be stable. The reason is that in a multi-keyword search, the more keywords that represent the semantic features of the query, the more the returned document reflects the latent semantics of the query. However, when the queried keywords can well represent the semantic features of the query, increasing the number of queried keywords has little impact on the search results. At the same time, the semantic precision of SBERT-SRSE is the highest, LDA-EMRSE is the second, and TFIDF-MRSE is the lowest.Figure 5
Semantic precision versusn, k, and Q.
(a)(b)(c)


### 8.2. Search Time Cost Evaluation

In this section, we evaluate the time cost of the search algorithm in SBERT-SRSE, SBERT-ESRSE, LDA-EMRSE, and TFIDF-MRSE.(1)
Time Cost versus n. Figures 6(a) and 6(b) show that the search time costs of the four schemes increase with the increase of n. Among them, the reason for SBERT-SRSE is that the search process of SBERT-SRSE requires traversing all documents and obtaining the search result. With the increase of n, the number of documents grows, so the search time increases. The reason why the other three schemes increase in time is that they all need to selectively traverse document nodes. The larger the n is, the more document nodes are traversed, which leads to the increase of search time cost.(2)
Time Cost versus k. Figures 7(a) and 7(b) show that as the number of required documents k grows, the search time cost of SBERT-SRSE remains stable, while the other three schemes increases. Since SBERT-SRSE needs to traverse all documents to obtain the search result, no matter how k changes, the search time cost of SBERT-SRSE changes little. The reason for the increase in the search time cost of the other three schemes is that as k grows, more document nodes need to be traversed to find these incremental required documents.(3)
Time Cost versusQ. Figures 8(a) and 8(b) show that with the growth of Q, the search time costs of four schemes all remain stable. This means that the number of queried keywords has little effect on the search time overhead. The reason for this is that no matter how many keywords are queried, in each of the four schemes, they are always transformed into vectors of fixed dimension, respectively.Figure 6
Time cost versusn, (b) is the detail of (a).
(a)(b)Figure 7
Time cost versusk, (b) is the detail of (a).
(a)(b)Figure 8
Time cost versusQ, (b) is the detail of (a).
(a)(b)In Figures6(a), 7(a), and 8(a), the evaluation results all indicate that the search time cost of TFIDF-MRSE is significantly higher than that of the other schemes. This is because the dimension of the vector in TFIDF-MRSE is equivalent to the size of the keyword dictionary, which is much larger than the scale of the other three schemes. Figures 6(b), 7(b), and 8(b) all show that in the other three schemes, SBERT-SRSE has the highest search time cost, LDA-EMRSE is the second, and SBERT-ESRSE is the lowest. The reason is that SBERT-SRSE needs to traverse all the documents in the search process, while SBERT-ESRSE and LDA-EMRSE both use binary-tree-based index to search. Meanwhile, SBERT-ESRSE arranges the documents into leaf nodes according to the results of document clustering, in which the documents of adjacent leaf nodes have a high semantic correlation. So SBERT-ESRSE traverses fewer document nodes than LDA-EMRSE, requiring less search time.


## 8.1. Semantic Precision Evaluation

In order to reasonably describe the semantic precision of the scheme, we assume that the query keywords come from the same category and the documents in different categories are semantically irrelevant. We evaluate the search precision of SBERT-SRSE, SBERT-ESRSE, LDA-EMRSE, and TFIDF-MRSE using the method adopted by Ref. [50], which is shown as follows:(26)P=TPTP+FP×100%,where TP and FP indicate the numbers of documents in the search result that belong or do not belong to the category of the search intent, respectively.(1)
Semantic Precision versus n. As shown in Figure 5, with the increase of the number of documents n, the semantic precision of SBERT-SRSE and LDA-EMRSE remained stable, while that of TFIDF-MRSE gradually decreased. The reason is that in SBERT-SRSE and LDA-EMRSE, semantic models are used to extract the semantic features of the documents. As the number of documents increases, the topics extracted by the semantic models better reflect the semantic features of the documents, and have no significant impact on the semantic accuracy of the search. At the same time, because the document vectors trained by the SBERT model have more semantic features than those trained by the LDA model, the semantic precision of SBERT-SRSE is higher than that of the semantic precision of LDA-EMRSE.(2)
Semantic Precision versus k. Figure 5(b) shows that the semantic precision of the three schemes gradually decreases as the number of documents required k increases. The reason for this is that as k increases, documents that are less relevant to the search intent are added to the search results, which may result in a slight decrease in the semantic precisions.(3)
Semantic Precision versusQ. Figure 5(c) shows that as the number of queried keywords Q increases, semantic precisions of SBERT-SRSE, LDA-EMRSE, and TFIDF-MRSE are increased gradually, and then tend to be stable. The reason is that in a multi-keyword search, the more keywords that represent the semantic features of the query, the more the returned document reflects the latent semantics of the query. However, when the queried keywords can well represent the semantic features of the query, increasing the number of queried keywords has little impact on the search results. At the same time, the semantic precision of SBERT-SRSE is the highest, LDA-EMRSE is the second, and TFIDF-MRSE is the lowest.Figure 5
Semantic precision versusn, k, and Q.
(a)(b)(c)


## 8.2. Search Time Cost Evaluation

In this section, we evaluate the time cost of the search algorithm in SBERT-SRSE, SBERT-ESRSE, LDA-EMRSE, and TFIDF-MRSE.(1)
Time Cost versus n. Figures 6(a) and 6(b) show that the search time costs of the four schemes increase with the increase of n. Among them, the reason for SBERT-SRSE is that the search process of SBERT-SRSE requires traversing all documents and obtaining the search result. With the increase of n, the number of documents grows, so the search time increases. The reason why the other three schemes increase in time is that they all need to selectively traverse document nodes. The larger the n is, the more document nodes are traversed, which leads to the increase of search time cost.(2)
Time Cost versus k. Figures 7(a) and 7(b) show that as the number of required documents k grows, the search time cost of SBERT-SRSE remains stable, while the other three schemes increases. Since SBERT-SRSE needs to traverse all documents to obtain the search result, no matter how k changes, the search time cost of SBERT-SRSE changes little. The reason for the increase in the search time cost of the other three schemes is that as k grows, more document nodes need to be traversed to find these incremental required documents.(3)
Time Cost versusQ. Figures 8(a) and 8(b) show that with the growth of Q, the search time costs of four schemes all remain stable. This means that the number of queried keywords has little effect on the search time overhead. The reason for this is that no matter how many keywords are queried, in each of the four schemes, they are always transformed into vectors of fixed dimension, respectively.Figure 6
Time cost versusn, (b) is the detail of (a).
(a)(b)Figure 7
Time cost versusk, (b) is the detail of (a).
(a)(b)Figure 8
Time cost versusQ, (b) is the detail of (a).
(a)(b)In Figures6(a), 7(a), and 8(a), the evaluation results all indicate that the search time cost of TFIDF-MRSE is significantly higher than that of the other schemes. This is because the dimension of the vector in TFIDF-MRSE is equivalent to the size of the keyword dictionary, which is much larger than the scale of the other three schemes. Figures 6(b), 7(b), and 8(b) all show that in the other three schemes, SBERT-SRSE has the highest search time cost, LDA-EMRSE is the second, and SBERT-ESRSE is the lowest. The reason is that SBERT-SRSE needs to traverse all the documents in the search process, while SBERT-ESRSE and LDA-EMRSE both use binary-tree-based index to search. Meanwhile, SBERT-ESRSE arranges the documents into leaf nodes according to the results of document clustering, in which the documents of adjacent leaf nodes have a high semantic correlation. So SBERT-ESRSE traverses fewer document nodes than LDA-EMRSE, requiring less search time.


## 9. Conclusion

The searchable encryption scheme over cloud data has been a popular and challenging research issue. This paper introduces the SBERT model into searchable encryption, and proposes a semantic-based multi-keyword ranked search scheme for encrypted cloud data. Documents are trained as vectors containing semantic information, and then the documents are represented as vectors with topic relationships through HDBSCAN soft clustering. At the same time, specific keywords in the search are replaced by topic relevance. This solves the problem of semantic ignorance or unclear semantics in traditional searchable encryption schemes. The realization of the tree-based index further improves the search time. The results show that the scheme is an efficient and privacy-protected semantic-based multi-keyword ranked search scheme over encrypted cloud data.



---

*Source: 4478618-2022-04-29.xml*