# Privacy-Guarding Optimal Route Finding with Support for Semantic Search on Encrypted Graph in Cloud Computing Scenario

Authors: Bin Wu; Xianyi Chen; Zongda Wu; Zhiqiang Zhao; Zhuolin Mei; Caicai Zhang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The arrival of cloud computing age makes data outsourcing an important and convenient application. More and more individuals and organizations outsource large amounts of graph data to the cloud computing platform (CCP) for the sake of saving cost. As the server on CCP is not completely honest and trustworthy, the outsourcing graph data are usually encrypted before they are sent to CCP. The optimal route finding on graph data is a popular operation which is frequently used in many fields. The optimal route finding with support for semantic search has stronger query capabilities, and a consumer can use similar words of graph vertices as query terms to implement optimal route finding. Due to encrypting the outsourcing graph data before they are sent to CCP, it is not easy for data customers to manipulate and further use the encrypted graph data. In this paper, we present a solution to execute privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario (PORF). We designed a scheme by building secure query index to implement optimal route finding with support for semantic search based on searchable encryption idea and stemmer mechanism. We give formal security analysis for our scheme. We also analyze the efficiency of our scheme through the experimental evaluation.


---

## Body

## 1. Introduction

With the rapid progress of electronic devices and communication technologies, it promotes the advent of the era of cloud computing that has an important impact and value on all walks of life [1, 2]. Cloud computing also speeds up data outsourcing service and makes it an important and convenient application [3, 4]. Graph is a structure that is often used in various fields, such as traffic graph [5], social graph [6], and molecular structure graph [7]. Due to the powerful processing capability of cloud computing and the problem of cost saving, the enormous graph data are usually outsourced to the cloud computing platform (CCP) which is responsible for storing, managing, and processing these data. But the server on CCP is not completely honest and trustworthy, the privacy and security issues of the outsourcing graph data need to be considered and handled. Encrypting the outsourcing graph data is an effective and commonly used method before they are outsourced to CCP [8]. However, it is not easy for data customers to manipulate and further use the encrypted outsourcing graph data. Therefore, it is an extremely meaningful work to implement privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario.The optimal route finding on graph is an operation that is frequently used in many fields, and related applications include shortest path query [9], path planning [10], and minimum spanning tree [11]. The optimal route finding with support for semantic search has stronger query capabilities, and a customer can use similar words of graph vertices as query terms to implement optimal route finding. For instance, in a traffic network graph, the graph vertices represent locations, and the weight on the edge represents the route cost between two locations. The optimal path finding is to query for the path with the least cost between two locations. To realize semantic search, the porter stemmer mechanism commonly used in information retrieval [12] is adopted in this paper. The graph vertex set is transformed into a new set by the stemmer mechanism, and the new set is similar to the original set of vertices in semantics. When performing optimal route finding, the new set serves as the source set of query terms. Our work researches optimal route finding over encrypted graph data, and we also take into account cost savings; it is expensive in cost to download all the graph data from the remote server. In view of this, it is of great significance to implement optimal route finding with support for semantic search on encrypted graph. However, it is not an easy job to carry out the optimal route finding in consideration of the security and privacy issues in the cloud computing scenario.To implement query operations on the remote server in the cloud computing scenario, the idea of searchable encryption is very effective [13–17]. The remote server performs query through encrypted query terms, and the server cannot obtain the privacy information of the query terms and query results. The searchable encryption is a research hotspot in the area of information security, and the research progress in this field has also been advancing. Soon after, some dynamic and extended searchable encryption schemes have emerged [18–22], but the above searchable encryption schemes cannot be used to implement route finding with support for semantic search on encrypted graph. Recently, some researchers have studied and implemented some query schemes on the encrypted graph [23–27]. Chase et al. studied the query problem on the encrypted graph and proposed the structured encryption method [23]. Privacy preserving subgraph query problems were researched in the literatures [24, 25]. Shen et al. studied the problem of cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection [26]. Ciucanu et al. presented a secure framework for graph outsourcing and SPARQL evaluation in the literature [27]. However, these methods cannot address the problem of optimal route finding with support for semantic search on encrypted graph.To solve the problem on CCP, we present a solution to execute privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario (PORF). In the PORF scheme, the server on CCP implements the privacy-guarding optimal route finding with the help of the index we build. Firstly, we use porter stemmer mechanism to transform the graph vertices into a new set to achieve semantic search. Then, based on the new set, we build the chain tables, and each node of which contains optimal route information. Finally, we build a secure index on the basis of all the chain tables, and the index is stored on the server of CCP, and the server executes optimal route finding by the index and the encrypted query terms. The server cannot learn the privacy contents of the query results and query terms. The security analysis and the experimental evaluation show that our proposed PORF scheme is secure and efficient.The contributions of our paper are described below.(1)
We present a scheme to address the problem of optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario(2)
We give the formal security analysis of the scheme to ensure the privacy and security of query results and query terms(3)
We conduct an experimental analysis to demonstrate the efficiency of our schemeThe rest of our paper is organized below. Section2 presents the related work. Section 3 gives the design and analysis process of our PORF scheme. Section 4 analyzes the security of the PORF scheme. Section 5 demonstrates the PORF scheme through experiment and comparison. Finally, section 6 summarizes our paper.


## 2. Related Work

With the rapid development of computer technology and the huge increase of people’s demands [28–31], privacy and security issues have increasingly become an important consideration [32–35]. In the field of data outsourcing security, searchable encryption plays an important role and can realize the query of outsourcing data without disclosing privacy information [36, 37]. Generally speaking, there are two kinds of searchable encryption types: searchable symmetric encryption and searchable asymmetric encryption [16, 17]. Usually, the querying of symmetric encryption is more efficient than that of asymmetrical encryption. Thus, we use symmetric encryption idea in our scheme.Searchable encryption becomes an efficient cryptographic primitive in remote data query which plays an important value in data outsourcing [13–16]. The concept and idea of searchable symmetric encryption was first presented in the literature [13]. Goh came up with the secure index strategy in which the bloom filter was used to address the search question on outsourced data in the literature [14]. Curtmola et al. put forward the conception of nonadaptive searchable symmetric encryption and adaptive searchable symmetric encryption in the literature [16]. Chang et al. adopted pseudorandom functions to solve the problem of privacy preserving keyword searches on remote encrypted data and solved the update problem [17]. Thereafter, some researchers in the field of security proposed a lot of outspread searchable encryption solutions [18–22]. Wang et al. investigate the problem of secure and efficient similarity search over outsourced cloud data and proposed a new symbol-based trietraverse searching mechanism [18]. The questions of the secure and efficient ranked search over encrypted outsourcing data were studied in the literatures [19, 20]. Du et al. presented a dynamic multiclient searchable symmetric encryption scheme supporting Boolean queries which allowed the data owner to authorize multiple users to excute Boolean queries over the encrypted data [21]. Li et al. used the k-nearest neighbor and attribute-based encryption techniques to present a dynamic searchable symmetric encryption scheme and addressed the key sharing problem [22], but all the searchable encryption solutions cannot be used to perform optimal route finding with support for semantic search over encrypted graph data.In recent years, the secure query questions on encrypted graph were studied, and some relative research achievements have been acquired [23–27]. Chase et al. presented the idea of structured encryption and proposed the application of controlled disclosure in the literature [23]. Cao et al. adopted the “filtering-and-verification” principle to study and address the problem of subgraph query on the encrypted graph [24]. Fan et al. proposed a private subgraph query solution for large graphs, and the query subgraph needed to be protected while the data graph did not [25]. Shen et al. proposed a graph encryption scheme to achieve the constrained shortest distance query and presented a tree-based ciphertext comparison protocol [26]. Ciucanu et al. designed and implemented a secure framework to perform the quey with SPARQL evaluation on outsourcing graphs in the literature [27]. However, all the existing solutions of encrytped graph search have not addressed the issue of privacy-guarding optimal route finding with support for semantic search on encrypted graph.In this paper, we come up with a solution on the strength of searchable encryption idea and porter stemmer mechanism to perform optimal route finding with support for semantic search. We first transform graph vertices into new word set and build the chain tables based on the new set. We next build an index which is sent to the server on CCP, and the server excutes optimal route finding through the index and the encrypted query terms. We finally analyze and evaluate our solution both from security and experiment.


## 3. PORF Scheme Construction

### 3.1. Preliminaries

Goldwasser et al. presented the concepts of semantic security and indistinguishability in the literature [38]. A system is semantically secure if whatever an adversary can compute about the plaintext given the ciphertext, he can also compute without the ciphertext [38]. In this paper, we use the set Kge,Enc,Dec containing three polynomial-size algorithms to represent a semantically secure encryption mechanism [39]. Kge is a secret key generating algorithm. Enc and Dec represent the encryption algorithm and decryption algorithm, respectively.To implement semantic search in our PORF scheme, we adopt the porter stemmer mechanism in information retrieval [12], but not limited to only this method can achieve. We use V=v1,⋯,vn to represent the vertices set of outsourcing graph, and the new word set after transformation through porter stemmer mechanism is represented as A=a1,⋯,au, where ∣A∣≤∣V∣. The main notations used in our paper follow in Table 1.Table 1
Summary of notations.
NotationsDenotationsGThe outsourcing graphIThe optimal route finding indexnThe number of vertices of graphGVThe vertices set of graphG, V=v1,⋯,vnmThe number of optimal routes of graphGxΔyThe wordsx and y are concatenated as a wholecThe maximum number of optimal routes about querying vertices in graphGQiThe encrypted query term, where1≤i≤mRQiThe set of optimal route finding results of query termQi,jEnckey·The symmetric encryption algorithmDeckey·The symmetric decryption algorithm


### 3.2. PORF Overview

In the cloud computing scenario, the architecture about outsourcing query illustrated in Figure1 is mainly composed of three entities: the server on CCP, the data owner, and data customers. The server provide data owners and customers with storage, management, and query services. To enable the server to implement optimal route finding on the encrypted outsourcing graph, we construct an index and encrypt the query request and then put them on the server. In this work, our main task is to study and achieve optimal route finding with support for semantic search. With respect to the query control and authentication of data customers, we adopt the thought of preexisting searchable encryption such as broadcast encryption [16].Figure 1
Architecture of optimal route finding on the encrypted graph.Our PORF scheme can perform optimal route finding with support for semantic search over the encrypted graph on CCP, and the following design targets can be achieved.(1)
Privacy-guarding optimal route finding functionality. The customer can achieve privacy-guarding optimal route finding with support for semantic search by means of the server on CCP(2)
Security guarantee. We can give the security guarantee for our scheme through formal analysis, and it prevents the server from getting the privacy of the query results and query terms(3)
Efficiency. We can implement our scheme of optimal route finding with less overheadIn the PORF scheme design, we make use of index and chain table on the part of data structures. Our work considers the undirected graph as the research object, and the processing operation of directed graph is similar. We adopt the chain tables to store the optimal route information. Query vertices need to be processed and encrypted before being sent to the server, and the index is then built to complete privacy-guarding optimal route finding via the server on CCP.To implement the optimal route finding in the cloud computing scenario, we try to deal with it in three steps. Firstly, we build the chain tables, and each node of the chain tables consists of the vertices and optimal route information which need to be encrypted. Secondly, we are going to build a secure index to randomly store all the nodes of the chain tables. Finally, the query vertices of a customer are delivered to the server after security processing, and the server executes optimal route finding with support for semantic search on CCP with the help of the built index. Consistent with the thought of existing symmetric searchable encryption schemes [16, 18, 19], we assume that the server on CCP will adopt the adaptive attack model, and the query customers have the mutual request authentication and query control mechanisms with the data owner [16].


### 3.3. Scheme Design and Implementation

In the PORF scheme, our main work is to build the index and how to implement optimal route finding by means of the index on CCP. The several used algorithms in our scheme are described below.(i)
Genkeys (1ℓ): symmetric secret key generation algorithm. The parameter ℓ is taken as the input, and the symmetric secret key k is used as the output(ii)
Chaintablebuilding (G, K): building the chain tables of graph vertices to store the contents of optimal route. The graph data G and the symmetric secret key set K serve as inputs, and the outputs are the work set A with similar meanings of graph vertices, the set W of compound terms about work set, and the chain table set F(iii)
Indexbuilding (W, F, K, K′): building query index algorithm. The inputs are the set W, chain table set F, and the key sets K and K′, and the output is the query index I(iv)
Querybuilding (wi, K): building query term algorithm. The inputs include the word wi from the set W and the key set K. The encrypted query term set Qi serves as the output(v)
Queryperforming (I, Qi): implementing optimal route finding on CCP. The index I and the query term set Qi serve as the inputs, and the set of optimal route is the outputIn our work, we useℓ to be the security parameter and adopt Kge,Enc,Dec as a secure symmetric encryption scheme in our optimal route finding solution. The building process of our proposed PORF scheme is as follows.


#### 3.3.1. Building Chain Table

To implement the semantic search, we adopt the porter stemmer mechanism to turn graph vertices setV into a new set A=a1,⋯,au, where u≤n. We combine two arbitrary inequable words in the set A to form a new compound term, and new term set is denoted as W = w1,w2,⋯,wm. For every member wi of the set W (0≤i≤m), we build its chain table Fi, and we use elem to represent the node of the chain table. The creation process of chain tables is described in Algorithm 1. The content of each node in the chain table Fi consists of optimal route information, and we write it in terms of the symbol optrvalue. To protect the security of the chain table contents, we need to encrypt the chain table nodes. The two used symmetric key sets in our scheme are represented as K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′. The set of all chain tables that are built related to the set W is denoted as F=F1,F2,⋯Fm.In the algorithmChaintablebuilding, the time complexity of new word conversion via porter stemmer is On, and the time complexity of building set W is On. The time complexity of building every chain table Fi is Omax∣Fi∣,c=Oc (c is the maximum number of optimal routes of compound terms), and the time complexity of building m chain tables is O(m·c). Therefore, the total time complexity of the algorithm Chaintablebuilding is On+O(m·c).Algorithm 1:Chaintablebuilding.
Input: The graph data G, and the symmetric key set K.Output: The chain table set F1: The set of graph vertices isV = v1,v2,⋯,vn, and the symmetric key set is K = k1,k2,⋯,km2:for alli∈1,ndo3:  Each membervi in the set V is turned into a new word after conversion via porter stemmer mechanism, and the new word set is represented as A=a1,⋯,au, where u≤n4:end for5:for alli,j∈1,udo6:  Two arbitrary inequable wordsai and aj in the set A are combined into a new compound term, and all the new terms set is denoted as W = w1,w2,⋯,wm; and ∣wi∣ (1≤i≤m) represents the number of optimal route about the compound term wi7:end for8:for alli∈1,mdo9:for allj∈1,∣wi∣do10:wi,j=Enckioptrvalue;11:Fi→elemj=wi,j;12:end for13:end for14:F=F1,F2,⋯Fm15:returnF.


#### 3.3.2. Building Optimal Route Finding Index

To enable the server to perform optimal route finding in the cloud computing scenario, we propose to implement this by building an index. The process of creating our index is described in Algorithm2. For each chain table Fi (0≤i≤m), the contents of each node contain optimal route information, and the number of nodes (that is, the number of optimal routes about the compound term ∣wi∣) is denoted as ∣Fi∣. For 1≤j≤∣Fi∣, we generate a tag for the term wi by concatenating wi and j, and the tag is represented as wiΔj. Then, all the tags about the term wi are denoted as a set γwi=wiΔ1,⋯,wiΔ∣Fi∣. The matching optimal route informaton of each member in the set γwi is placed in the index. Performing optimal route finding of the term wi is equivalent to seeking for the corresponding members in the index I via all the correlative tags in the set γwi. To prevent the server on CCP from getting information about the number of optimal routes of each member wi, we need to add the extra elements (We call them the disturbingvalues) to pad the index such that the number of optimal routes of each member in the set W is the same; that is, it is the maximum number of optimal routes c in the graph G. If ∣Fi∣<c, we need to add c−∣Fi∣ extra elements.In the algorithmIndexbuilding of generating the index, we need to calculate the storage location of index members and then assign values to each member of the index. The chain table set F contains m chain tables, and each table has at most c nodes. All of the nodes in the chain table set F are stored in the index I. As a result, the time complexity of the algorithm Indexbuilding is O(m·c).Algorithm 2:Indexbuilding.
Input:W,F,K,K′Output: I1: The compound terms set isW = w1,w2,⋯,wm, and the chain table set is F=F1,F2,⋯Fm; The two secret key sets are K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′;2:for allFi∈F (0≤i≤m) do3:for allj∈1,Fido4:loc=Encki′wiΔj;/∗loc is the location of members in the index∗/5:Iloc=Fi→elemloc6:end for7:end for8:for allFi∈F (0≤i≤m) do9:if∣Fi∣<cthen10:for allt∈1,c−∣Fi∣do11:loc=Encki′∣Fi∣+t;12:Iloc=Enckioptrvalue+t;13:end for14:end if15:end for16:returnI.


#### 3.3.3. Performing Optimal Route Finding

After the index is built, we will consider how to execute optimal route finding through the server on CCP. To accomplish this operation, for the elementwi from set W (0≤i≤m), we need to build the query term Qi = ψi1,⋯,ψic. More specifically, the query term is created by the symmetric encryption algorithm Enckey·, that is Qi = ψi1,⋯,ψic = EnckiwiΔ1,⋯,EnckiwiΔc. When a customer is going to execute optimal route finding about the word wi, the query term Qi is delivered to the server on CCP. With the help of the query term and the index, the server completes the operation of optimal route finding in the cloud computing scenario through Algorithm 3.In the algorithmQueryperforming, for the query term Qi (0≤i≤m), if Iψij is not a disturbingvalue (1≤y≤c), we will put Iψij into RQi. Therefore, the time complexity of the algorithm Queryperforming is Oc.Algorithm 3:Queryperforming.
Input:Qi,IOutput:RQi1: Generating the query term of the memberwi from the set W (0≤i≤m), and is denoted as Qi = ψi1,⋯,ψic;2:for allj∈1,cdo3:ifIψij≠disturbingvaluethen4:   putIψij into RQi;5:end if6:end for7:returnRQi;In the paper, we propose a solution to solve the problem of privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario. By the aid of encrypted query terms and a secure index, the server of CCP executes the privacy-guarding optimal route finding and returns the encrypted query results to the query customer. Our scheme satisfies the efficiency and the query security, and the server cannot obtain the privacy information of the query terms and the retrieval results.


## 3.1. Preliminaries

Goldwasser et al. presented the concepts of semantic security and indistinguishability in the literature [38]. A system is semantically secure if whatever an adversary can compute about the plaintext given the ciphertext, he can also compute without the ciphertext [38]. In this paper, we use the set Kge,Enc,Dec containing three polynomial-size algorithms to represent a semantically secure encryption mechanism [39]. Kge is a secret key generating algorithm. Enc and Dec represent the encryption algorithm and decryption algorithm, respectively.To implement semantic search in our PORF scheme, we adopt the porter stemmer mechanism in information retrieval [12], but not limited to only this method can achieve. We use V=v1,⋯,vn to represent the vertices set of outsourcing graph, and the new word set after transformation through porter stemmer mechanism is represented as A=a1,⋯,au, where ∣A∣≤∣V∣. The main notations used in our paper follow in Table 1.Table 1
Summary of notations.
NotationsDenotationsGThe outsourcing graphIThe optimal route finding indexnThe number of vertices of graphGVThe vertices set of graphG, V=v1,⋯,vnmThe number of optimal routes of graphGxΔyThe wordsx and y are concatenated as a wholecThe maximum number of optimal routes about querying vertices in graphGQiThe encrypted query term, where1≤i≤mRQiThe set of optimal route finding results of query termQi,jEnckey·The symmetric encryption algorithmDeckey·The symmetric decryption algorithm


## 3.2. PORF Overview

In the cloud computing scenario, the architecture about outsourcing query illustrated in Figure1 is mainly composed of three entities: the server on CCP, the data owner, and data customers. The server provide data owners and customers with storage, management, and query services. To enable the server to implement optimal route finding on the encrypted outsourcing graph, we construct an index and encrypt the query request and then put them on the server. In this work, our main task is to study and achieve optimal route finding with support for semantic search. With respect to the query control and authentication of data customers, we adopt the thought of preexisting searchable encryption such as broadcast encryption [16].Figure 1
Architecture of optimal route finding on the encrypted graph.Our PORF scheme can perform optimal route finding with support for semantic search over the encrypted graph on CCP, and the following design targets can be achieved.(1)
Privacy-guarding optimal route finding functionality. The customer can achieve privacy-guarding optimal route finding with support for semantic search by means of the server on CCP(2)
Security guarantee. We can give the security guarantee for our scheme through formal analysis, and it prevents the server from getting the privacy of the query results and query terms(3)
Efficiency. We can implement our scheme of optimal route finding with less overheadIn the PORF scheme design, we make use of index and chain table on the part of data structures. Our work considers the undirected graph as the research object, and the processing operation of directed graph is similar. We adopt the chain tables to store the optimal route information. Query vertices need to be processed and encrypted before being sent to the server, and the index is then built to complete privacy-guarding optimal route finding via the server on CCP.To implement the optimal route finding in the cloud computing scenario, we try to deal with it in three steps. Firstly, we build the chain tables, and each node of the chain tables consists of the vertices and optimal route information which need to be encrypted. Secondly, we are going to build a secure index to randomly store all the nodes of the chain tables. Finally, the query vertices of a customer are delivered to the server after security processing, and the server executes optimal route finding with support for semantic search on CCP with the help of the built index. Consistent with the thought of existing symmetric searchable encryption schemes [16, 18, 19], we assume that the server on CCP will adopt the adaptive attack model, and the query customers have the mutual request authentication and query control mechanisms with the data owner [16].


## 3.3. Scheme Design and Implementation

In the PORF scheme, our main work is to build the index and how to implement optimal route finding by means of the index on CCP. The several used algorithms in our scheme are described below.(i)
Genkeys (1ℓ): symmetric secret key generation algorithm. The parameter ℓ is taken as the input, and the symmetric secret key k is used as the output(ii)
Chaintablebuilding (G, K): building the chain tables of graph vertices to store the contents of optimal route. The graph data G and the symmetric secret key set K serve as inputs, and the outputs are the work set A with similar meanings of graph vertices, the set W of compound terms about work set, and the chain table set F(iii)
Indexbuilding (W, F, K, K′): building query index algorithm. The inputs are the set W, chain table set F, and the key sets K and K′, and the output is the query index I(iv)
Querybuilding (wi, K): building query term algorithm. The inputs include the word wi from the set W and the key set K. The encrypted query term set Qi serves as the output(v)
Queryperforming (I, Qi): implementing optimal route finding on CCP. The index I and the query term set Qi serve as the inputs, and the set of optimal route is the outputIn our work, we useℓ to be the security parameter and adopt Kge,Enc,Dec as a secure symmetric encryption scheme in our optimal route finding solution. The building process of our proposed PORF scheme is as follows.


### 3.3.1. Building Chain Table

To implement the semantic search, we adopt the porter stemmer mechanism to turn graph vertices setV into a new set A=a1,⋯,au, where u≤n. We combine two arbitrary inequable words in the set A to form a new compound term, and new term set is denoted as W = w1,w2,⋯,wm. For every member wi of the set W (0≤i≤m), we build its chain table Fi, and we use elem to represent the node of the chain table. The creation process of chain tables is described in Algorithm 1. The content of each node in the chain table Fi consists of optimal route information, and we write it in terms of the symbol optrvalue. To protect the security of the chain table contents, we need to encrypt the chain table nodes. The two used symmetric key sets in our scheme are represented as K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′. The set of all chain tables that are built related to the set W is denoted as F=F1,F2,⋯Fm.In the algorithmChaintablebuilding, the time complexity of new word conversion via porter stemmer is On, and the time complexity of building set W is On. The time complexity of building every chain table Fi is Omax∣Fi∣,c=Oc (c is the maximum number of optimal routes of compound terms), and the time complexity of building m chain tables is O(m·c). Therefore, the total time complexity of the algorithm Chaintablebuilding is On+O(m·c).Algorithm 1:Chaintablebuilding.
Input: The graph data G, and the symmetric key set K.Output: The chain table set F1: The set of graph vertices isV = v1,v2,⋯,vn, and the symmetric key set is K = k1,k2,⋯,km2:for alli∈1,ndo3:  Each membervi in the set V is turned into a new word after conversion via porter stemmer mechanism, and the new word set is represented as A=a1,⋯,au, where u≤n4:end for5:for alli,j∈1,udo6:  Two arbitrary inequable wordsai and aj in the set A are combined into a new compound term, and all the new terms set is denoted as W = w1,w2,⋯,wm; and ∣wi∣ (1≤i≤m) represents the number of optimal route about the compound term wi7:end for8:for alli∈1,mdo9:for allj∈1,∣wi∣do10:wi,j=Enckioptrvalue;11:Fi→elemj=wi,j;12:end for13:end for14:F=F1,F2,⋯Fm15:returnF.


### 3.3.2. Building Optimal Route Finding Index

To enable the server to perform optimal route finding in the cloud computing scenario, we propose to implement this by building an index. The process of creating our index is described in Algorithm2. For each chain table Fi (0≤i≤m), the contents of each node contain optimal route information, and the number of nodes (that is, the number of optimal routes about the compound term ∣wi∣) is denoted as ∣Fi∣. For 1≤j≤∣Fi∣, we generate a tag for the term wi by concatenating wi and j, and the tag is represented as wiΔj. Then, all the tags about the term wi are denoted as a set γwi=wiΔ1,⋯,wiΔ∣Fi∣. The matching optimal route informaton of each member in the set γwi is placed in the index. Performing optimal route finding of the term wi is equivalent to seeking for the corresponding members in the index I via all the correlative tags in the set γwi. To prevent the server on CCP from getting information about the number of optimal routes of each member wi, we need to add the extra elements (We call them the disturbingvalues) to pad the index such that the number of optimal routes of each member in the set W is the same; that is, it is the maximum number of optimal routes c in the graph G. If ∣Fi∣<c, we need to add c−∣Fi∣ extra elements.In the algorithmIndexbuilding of generating the index, we need to calculate the storage location of index members and then assign values to each member of the index. The chain table set F contains m chain tables, and each table has at most c nodes. All of the nodes in the chain table set F are stored in the index I. As a result, the time complexity of the algorithm Indexbuilding is O(m·c).Algorithm 2:Indexbuilding.
Input:W,F,K,K′Output: I1: The compound terms set isW = w1,w2,⋯,wm, and the chain table set is F=F1,F2,⋯Fm; The two secret key sets are K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′;2:for allFi∈F (0≤i≤m) do3:for allj∈1,Fido4:loc=Encki′wiΔj;/∗loc is the location of members in the index∗/5:Iloc=Fi→elemloc6:end for7:end for8:for allFi∈F (0≤i≤m) do9:if∣Fi∣<cthen10:for allt∈1,c−∣Fi∣do11:loc=Encki′∣Fi∣+t;12:Iloc=Enckioptrvalue+t;13:end for14:end if15:end for16:returnI.


### 3.3.3. Performing Optimal Route Finding

After the index is built, we will consider how to execute optimal route finding through the server on CCP. To accomplish this operation, for the elementwi from set W (0≤i≤m), we need to build the query term Qi = ψi1,⋯,ψic. More specifically, the query term is created by the symmetric encryption algorithm Enckey·, that is Qi = ψi1,⋯,ψic = EnckiwiΔ1,⋯,EnckiwiΔc. When a customer is going to execute optimal route finding about the word wi, the query term Qi is delivered to the server on CCP. With the help of the query term and the index, the server completes the operation of optimal route finding in the cloud computing scenario through Algorithm 3.In the algorithmQueryperforming, for the query term Qi (0≤i≤m), if Iψij is not a disturbingvalue (1≤y≤c), we will put Iψij into RQi. Therefore, the time complexity of the algorithm Queryperforming is Oc.Algorithm 3:Queryperforming.
Input:Qi,IOutput:RQi1: Generating the query term of the memberwi from the set W (0≤i≤m), and is denoted as Qi = ψi1,⋯,ψic;2:for allj∈1,cdo3:ifIψij≠disturbingvaluethen4:   putIψij into RQi;5:end if6:end for7:returnRQi;In the paper, we propose a solution to solve the problem of privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario. By the aid of encrypted query terms and a secure index, the server of CCP executes the privacy-guarding optimal route finding and returns the encrypted query results to the query customer. Our scheme satisfies the efficiency and the query security, and the server cannot obtain the privacy information of the query terms and the retrieval results.


## 3.3.1. Building Chain Table

To implement the semantic search, we adopt the porter stemmer mechanism to turn graph vertices setV into a new set A=a1,⋯,au, where u≤n. We combine two arbitrary inequable words in the set A to form a new compound term, and new term set is denoted as W = w1,w2,⋯,wm. For every member wi of the set W (0≤i≤m), we build its chain table Fi, and we use elem to represent the node of the chain table. The creation process of chain tables is described in Algorithm 1. The content of each node in the chain table Fi consists of optimal route information, and we write it in terms of the symbol optrvalue. To protect the security of the chain table contents, we need to encrypt the chain table nodes. The two used symmetric key sets in our scheme are represented as K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′. The set of all chain tables that are built related to the set W is denoted as F=F1,F2,⋯Fm.In the algorithmChaintablebuilding, the time complexity of new word conversion via porter stemmer is On, and the time complexity of building set W is On. The time complexity of building every chain table Fi is Omax∣Fi∣,c=Oc (c is the maximum number of optimal routes of compound terms), and the time complexity of building m chain tables is O(m·c). Therefore, the total time complexity of the algorithm Chaintablebuilding is On+O(m·c).Algorithm 1:Chaintablebuilding.
Input: The graph data G, and the symmetric key set K.Output: The chain table set F1: The set of graph vertices isV = v1,v2,⋯,vn, and the symmetric key set is K = k1,k2,⋯,km2:for alli∈1,ndo3:  Each membervi in the set V is turned into a new word after conversion via porter stemmer mechanism, and the new word set is represented as A=a1,⋯,au, where u≤n4:end for5:for alli,j∈1,udo6:  Two arbitrary inequable wordsai and aj in the set A are combined into a new compound term, and all the new terms set is denoted as W = w1,w2,⋯,wm; and ∣wi∣ (1≤i≤m) represents the number of optimal route about the compound term wi7:end for8:for alli∈1,mdo9:for allj∈1,∣wi∣do10:wi,j=Enckioptrvalue;11:Fi→elemj=wi,j;12:end for13:end for14:F=F1,F2,⋯Fm15:returnF.


## 3.3.2. Building Optimal Route Finding Index

To enable the server to perform optimal route finding in the cloud computing scenario, we propose to implement this by building an index. The process of creating our index is described in Algorithm2. For each chain table Fi (0≤i≤m), the contents of each node contain optimal route information, and the number of nodes (that is, the number of optimal routes about the compound term ∣wi∣) is denoted as ∣Fi∣. For 1≤j≤∣Fi∣, we generate a tag for the term wi by concatenating wi and j, and the tag is represented as wiΔj. Then, all the tags about the term wi are denoted as a set γwi=wiΔ1,⋯,wiΔ∣Fi∣. The matching optimal route informaton of each member in the set γwi is placed in the index. Performing optimal route finding of the term wi is equivalent to seeking for the corresponding members in the index I via all the correlative tags in the set γwi. To prevent the server on CCP from getting information about the number of optimal routes of each member wi, we need to add the extra elements (We call them the disturbingvalues) to pad the index such that the number of optimal routes of each member in the set W is the same; that is, it is the maximum number of optimal routes c in the graph G. If ∣Fi∣<c, we need to add c−∣Fi∣ extra elements.In the algorithmIndexbuilding of generating the index, we need to calculate the storage location of index members and then assign values to each member of the index. The chain table set F contains m chain tables, and each table has at most c nodes. All of the nodes in the chain table set F are stored in the index I. As a result, the time complexity of the algorithm Indexbuilding is O(m·c).Algorithm 2:Indexbuilding.
Input:W,F,K,K′Output: I1: The compound terms set isW = w1,w2,⋯,wm, and the chain table set is F=F1,F2,⋯Fm; The two secret key sets are K = k1,k2,⋯,km and K′ = k1′,k2′,⋯,km′;2:for allFi∈F (0≤i≤m) do3:for allj∈1,Fido4:loc=Encki′wiΔj;/∗loc is the location of members in the index∗/5:Iloc=Fi→elemloc6:end for7:end for8:for allFi∈F (0≤i≤m) do9:if∣Fi∣<cthen10:for allt∈1,c−∣Fi∣do11:loc=Encki′∣Fi∣+t;12:Iloc=Enckioptrvalue+t;13:end for14:end if15:end for16:returnI.


## 3.3.3. Performing Optimal Route Finding

After the index is built, we will consider how to execute optimal route finding through the server on CCP. To accomplish this operation, for the elementwi from set W (0≤i≤m), we need to build the query term Qi = ψi1,⋯,ψic. More specifically, the query term is created by the symmetric encryption algorithm Enckey·, that is Qi = ψi1,⋯,ψic = EnckiwiΔ1,⋯,EnckiwiΔc. When a customer is going to execute optimal route finding about the word wi, the query term Qi is delivered to the server on CCP. With the help of the query term and the index, the server completes the operation of optimal route finding in the cloud computing scenario through Algorithm 3.In the algorithmQueryperforming, for the query term Qi (0≤i≤m), if Iψij is not a disturbingvalue (1≤y≤c), we will put Iψij into RQi. Therefore, the time complexity of the algorithm Queryperforming is Oc.Algorithm 3:Queryperforming.
Input:Qi,IOutput:RQi1: Generating the query term of the memberwi from the set W (0≤i≤m), and is denoted as Qi = ψi1,⋯,ψic;2:for allj∈1,cdo3:ifIψij≠disturbingvaluethen4:   putIψij into RQi;5:end if6:end for7:returnRQi;In the paper, we propose a solution to solve the problem of privacy-guarding optimal route finding with support for semantic search on the encrypted graph in the cloud computing scenario. By the aid of encrypted query terms and a secure index, the server of CCP executes the privacy-guarding optimal route finding and returns the encrypted query results to the query customer. Our scheme satisfies the efficiency and the query security, and the server cannot obtain the privacy information of the query terms and the retrieval results.


## 4. Security Analysis

Now, we analyze the security of the PORF scheme. We first give several concepts used in security analysis of our scheme [10].
(i)
History: the interaction between the server on CCP and a query customer, containing the graph data G and the set of query terms, expressed as Hq=G,Q1,⋯,Qq. The partial history is expressed as Hqt=G,Q1,⋯,Qt, where t≤q(ii)
View: existing the history Hq about the key k, a view is defined as VkHq=EnckG,I,Q1,⋯,Qq. The partial view is VktHq=EnckG,I,Q1,⋯,Qt, where t≤q(iii)
Access Pattern: existing the history Hq about the key k, the access pattern is defined as a tuple RHq=RQ1,⋯,RQq, where RQi1≤i≤q is the result set of optimal route finding matching to the query term Qi(iv)
Search Pattern: existing the history Hq about the key k, the search pattern is defined as a binary symmetric matrix ∏q, such that ∏qi,j=1 if Qi=Qj and ∏qi,j=0, otherwise, for 1≤i,j≤q(v)
Trace: existing the history Hq about the key k, the trace is defined as a tuple TrHq=EnckG,RHq,∏q, where ∣EnckG∣ is the overall size of the outsourcing graph, and RHq and ∏q are the access pattern and the search pattern of the history Hq, respectively. The trace of partial history is defined as TrHqt=∣EnckG∣,RHqt,∏t, where t≤qThe server on CCP will perform optimal route finding through the index and the query term and cannot get the contents of the query results and the query term. In our work, we prove our optimal route finding scheme meets the adaptive semantic security. About the adaptive attack model, the server on CCP can make a choice from the query request on account of the query term and the results about optimal route finding of previous queries [10, 36]. For the consideration of security analysis, we follow the security idea adopted in the previous schemes [10, 36]. According to the security guarantee of our PORF scheme, the server on CCP cannot obtain the additional information apart from the trace, and hence our proposed scheme of optimal route finding is secure. The security theorem of our PORF scheme is stated below.Theorem 1.
Our PORF scheme meets the adaptive semantic security of searchable symmetric encryption idea.Proof.
To prove the security of the PORF scheme, we first describe a polynomial-size simulatorε. For all q∈N, in the case of existing the trace TrHqt of a partial history, the simulator ε can build a view Vqt∗ which is used to simulate the view VktHq of the adversary, and such that Vqt∗ and VktHq cannot be distinguished, where k is a symmetrical key and 0≤t≤q.Fort=0, the simulator ε generates the simulative encrypted outsourcing graph with the same size as the real graph through random strings. In the meantime, the simulator ε constructs the index I∗ through randomly generating strings on the TrHq0 which is also used to simulate the real index I and has the same size as the real index. The index I∗ will be used to simulate the real index in other partial views Vqt∗, where 1≤t≤q. It is very obvious that the simulative encrypted graph is indistinguishable from the real outsourcing graph, and the index I∗ is indistinguishable from the index I. Otherwise, one can distinguish between the outputs of the semantically secure symmetric encryption and the random strings with the same size. Thus, Vq0∗ is indistinguishable from Vk0Hq.For1≤t≤q, the simulator ε can still use the index I∗ that was built before. The search pattern matrix ∏t about t query terms belongs to the trace TrHqt. The simulator ε will generate the query terms Q1∗,⋯,Qt∗ that are contained in the view Vqt∗. In the generation of these query terms, the query terms Q1∗,⋯,Qt−1∗ contained in the view Vqt−1∗ may be reused. Or else, the simulator ε will regenerate these query terms from TrHqt−1.To generateQt∗, the simulator ε first needs to determine whether Hqt−1 contains Qt through checking whether ∏tt,j=1, where 1≤j≤t−1. If Hqt−1 cannot contain Qt, the simulator ε utilizes the information of TrHqt about RQt, i.e, RQt=RwtΔ1,⋯,RwtΔc. The simulator ε selects an address xi at random from the simulative index I∗ for 1≤i≤c, making sure that all addresses are different and generates the query term Qt∗=x1,⋯,xc. The simulator ε will remember the correlation between Qt∗ and wt. Otherwise, if Hqt−1 contains wt, the simulator ε will retrieve the query contents in connection with wt and assigns it to Qt∗. This is to ensure that if Hqt−1 contains repeated query terms, then the query contents that are involved in Vqt∗ are identical.It is very obvious that the query termsQ1∗,⋯,Qt∗ in Vqt∗ are indistinguishable from the query terms Q1,⋯,Qt in VktHq. Otherwise, one could distinguish between the outputs of the semantically secure symmetric encryption and the random strings with the same size. Therefore, for 0≤t≤q, there is no polynomial-size adversary that could distinguish between Vqt∗ and VktHq. Thus, the security theorem of the PORF scheme has been proven.


## 5. Experimental Evaluations

In this section, we will carry out experimental analysis of our scheme on the Enron email network graph [40, 41] and then give the evaluation results. The content of the experiment is completed through using C language program coding over the server on CCP and the local machine. The server on CCP is configured with the Linux operating system of 6 CPU cores with 3.0 GHz and 16 GB of RAM, and the local machine runs on the Windows 10 operating system equipped with Intel Core 4 CPU of 2.6 GHz. In our experimental analysis and evaluation, the index generation, query term generation, and the decryption of query results are performed on the local machine. The operation of optimal route finding is implemented on the server of CCP.To verify the efficiency of our scheme in the experimental analysis, we compare our PORF scheme with the optimal route finding scheme in plaintext, which is referred to as MORF. The MORF scheme is similar with the PORF scheme, and the index is constructed in a similar way. But in the MORF scheme, the data and index are not encrypted. Comparing our PORF scheme with the MORF scheme, it is intended to evaluate the time and memory overhead over encrypted graph. For the outsourcing graph of the same number of vertices, the difference of the number of edges can have a certain effect on the experimental analysis. Therefore, for the outsourcing graph used in our experiment, we adopt five graph data sets chose at random and think about two circumstances to compare and evaluate the performances. One circumstance is that the outsourcing graph includes more edges, and the number of edges in the graph sets is, respectively, 7958, 16934, 35819, 73586, and 119823. The other circumstance includes less edges which contains half of the number or so of the first circumstance. In the experimental evaluation, we use PORF1 and MORF1 to denote the experiments containing much more edges, and PORF2 and MORF2 to denote the experiments containing less edges. The comparative analysis of our experiment about these circumstances can assess overhead issues of optimal route finding and validate the efficiency of our PORF scheme.


### 5.1. Index Building

To perform secure optimal route finding on CCP, we first need to transform the graph vertices to complete the semantic search requirements and generate new word set. The chain tables are then built on top of the new word set to hold the optimal route information, and finally, the index is generated based on all the chain tables through theIndexbuilding algorithm. The experiments evaluated the index building time and index size, respectively. Experimental analysis and evaluation on the experimental graph data are conducted under four conditions, and the experimental result figures of building index are given. The analysis results about the time of index generation are shown in Figure 2, where the abscissa represents the number of vertices in the graph data, and the ordinate shows the time of index generation.Figure 2
Index building time.From Figure2, we can conclude that index building time and the number of vertices are closely related, and the time of index generation increases nearly linearly with the number of vertices under four conditions of PORF1, PORF2, MORF1, and MORF2. Generally, an outsourcing graph with more numbers of edges can have more optimal routes. Therefore, the time of index generation under PORF1 condition is more than that under PORF2 condition, and similarly the time of index generation under MORF1 condition is more than that under MORF2 condition. For the encrypted graph query, we need to encrypt the graph data and build the encrypted index. As a result, the time of index generation is more than that on the plaintext graph. Under PORF condition, we get the security of private data with encryption time cost. After building the encrypted index, the queries on CCP can meet security requirements, and customers’ privacy information cannot be compromised. Therefore, it is an effective way to increase index building time costs appropriately, and the process of encryption is done locally.The experimental analysis of the size about index generation is plotted in Figure3. The abscissa of the figure shows the number of vertices in the graph data, and the ordinate represents the size of index generation. The curves of the size about index generation are changing approximately linearly with the vertex count increases under the four conditions. For outsourcing graphs of the same number of vertices, the more number of edges there are, the larger building size of the index is. Therefore, the index generation size of PORF1 is larger than that of PORF2, and the index generation size of MORF1 is larger than that of MORF2. The proposed PORF scheme can ensure the security of query process with additional storage overhead. The index generation size of PORF is a little larger than that in the plaintext query method, but the difference is not significant.Figure 3
Index building size.


### 5.2. Performing Query

In the process of optimal route finding, the server on CCP makes use of the index and query terms to implement the query task by theQueryperforming algorithm, and the experimental analysis includes query time evaluation and decryption time evaluation. The experimental results about query and decryption are, respectively, shown in Figures 4 and 5, where the horizontal axis represents the number of vertices in the graph data, and the vertical axis represents the time of query or decryption. From Figure 4, we can conclude that the time of performing query changes nearly linearly with the rise of vertex count. The query processes under PORF2 and MORF2 conditions, respectively, take less time than that under PORF1 and MORF1 conditions.Figure 4
Query time.Figure 5
Decryption time.After the query is processed, the server on CCP sends the encrypted retrieval results to the query customer that completes the decryption locally. The results of experimental analysis about decryption are plotted in Figure5. The time of the decryption process in our experiment is related to the decryption mechanism and the size of the query results. We adopt the same decryption mechanism under PORF1 and PORF2 two conditions. The decryption time of PORF1 and PORF2 increases almost linearly with the rise of vertex count. Time consumption of the decryption process under PORF2 condition is less than that under PORF2 condition.In general, the index building of our PORF scheme is completed on local machine, and the time and size of the index are nearly linear to vertex count of the outsourcing graph. The query process is executed by the server on CCP, and the query time also increases with the increasing of vertex count. Meanwhile, the server on CCP does not get the privacy contents about the retrieval results and query terms. Our PORF scheme implements optimal route finding with support for semantic search on the encrypted graph and satisfies the privacy and efficiency of the query process.


## 5.1. Index Building

To perform secure optimal route finding on CCP, we first need to transform the graph vertices to complete the semantic search requirements and generate new word set. The chain tables are then built on top of the new word set to hold the optimal route information, and finally, the index is generated based on all the chain tables through theIndexbuilding algorithm. The experiments evaluated the index building time and index size, respectively. Experimental analysis and evaluation on the experimental graph data are conducted under four conditions, and the experimental result figures of building index are given. The analysis results about the time of index generation are shown in Figure 2, where the abscissa represents the number of vertices in the graph data, and the ordinate shows the time of index generation.Figure 2
Index building time.From Figure2, we can conclude that index building time and the number of vertices are closely related, and the time of index generation increases nearly linearly with the number of vertices under four conditions of PORF1, PORF2, MORF1, and MORF2. Generally, an outsourcing graph with more numbers of edges can have more optimal routes. Therefore, the time of index generation under PORF1 condition is more than that under PORF2 condition, and similarly the time of index generation under MORF1 condition is more than that under MORF2 condition. For the encrypted graph query, we need to encrypt the graph data and build the encrypted index. As a result, the time of index generation is more than that on the plaintext graph. Under PORF condition, we get the security of private data with encryption time cost. After building the encrypted index, the queries on CCP can meet security requirements, and customers’ privacy information cannot be compromised. Therefore, it is an effective way to increase index building time costs appropriately, and the process of encryption is done locally.The experimental analysis of the size about index generation is plotted in Figure3. The abscissa of the figure shows the number of vertices in the graph data, and the ordinate represents the size of index generation. The curves of the size about index generation are changing approximately linearly with the vertex count increases under the four conditions. For outsourcing graphs of the same number of vertices, the more number of edges there are, the larger building size of the index is. Therefore, the index generation size of PORF1 is larger than that of PORF2, and the index generation size of MORF1 is larger than that of MORF2. The proposed PORF scheme can ensure the security of query process with additional storage overhead. The index generation size of PORF is a little larger than that in the plaintext query method, but the difference is not significant.Figure 3
Index building size.


## 5.2. Performing Query

In the process of optimal route finding, the server on CCP makes use of the index and query terms to implement the query task by theQueryperforming algorithm, and the experimental analysis includes query time evaluation and decryption time evaluation. The experimental results about query and decryption are, respectively, shown in Figures 4 and 5, where the horizontal axis represents the number of vertices in the graph data, and the vertical axis represents the time of query or decryption. From Figure 4, we can conclude that the time of performing query changes nearly linearly with the rise of vertex count. The query processes under PORF2 and MORF2 conditions, respectively, take less time than that under PORF1 and MORF1 conditions.Figure 4
Query time.Figure 5
Decryption time.After the query is processed, the server on CCP sends the encrypted retrieval results to the query customer that completes the decryption locally. The results of experimental analysis about decryption are plotted in Figure5. The time of the decryption process in our experiment is related to the decryption mechanism and the size of the query results. We adopt the same decryption mechanism under PORF1 and PORF2 two conditions. The decryption time of PORF1 and PORF2 increases almost linearly with the rise of vertex count. Time consumption of the decryption process under PORF2 condition is less than that under PORF2 condition.In general, the index building of our PORF scheme is completed on local machine, and the time and size of the index are nearly linear to vertex count of the outsourcing graph. The query process is executed by the server on CCP, and the query time also increases with the increasing of vertex count. Meanwhile, the server on CCP does not get the privacy contents about the retrieval results and query terms. Our PORF scheme implements optimal route finding with support for semantic search on the encrypted graph and satisfies the privacy and efficiency of the query process.


## 6. Conclusion

In this paper, we propose a novel solution to address the problem of optimal route finding with support for semantic search, in which we adopt searchable encryption idea and porter stemmer mechanism. We first convert all graph vertices into a new word set by porter stemmer mechanism to satisfy semantic search. Then, we build the chain tables based on the new word set to place optimal route information and build an index based on the chain tables which is used to execute optimal route finding. Secondly, we prove the security of our scheme through formal analysis. Finally, we give experimental analysis and evaluation, and the results show that our scheme has good performance.For our future work, we intend to build dynamic optimal route finding scheme to meet the needs of dynamic graphs. In addition, our other research direction is to combine encryption graph query with secret key management and update to meet a wider range of query requirements.



---

*Source: 6617959-2021-03-17.xml*