Research On Query Processing Over Encrypted Graph

With the vigorous development of cloud computing,data outsourcing has become a popular trend.Through the cloud outsourcing,abundant resource of software and hardware can be presented to the users according to the requirements.It can save money and improve the utilization efficiency of resource.A graph is widely used,to reduce the cost and save money,large amounts of graph data are outsourced to the cloud server.Graph data usually contain some sensitive information.If the sensitive information is revealed,the user's privacy can be exposed.Due to the cloud server being not fully trusted,encryption is a necessary way of preventing the information leak.Considering the “pay-for-use” billing rule in the cloud,it is particularly uneconomical to download all the graph data and decrypt locally.Therefore,in order to provide the secure and effective query methods,it is of great significance to research query problems over encrypted graph in the cloud.In order to execute neighbor query and get the ranked results on the outsourcing graph,the researches on problem of neighbor query are conducted.In view of the directed weighted graph,a secure ranked neighbor query method PRNQ is proposed.Based on the weights of the graph,the relevance scores of neighbor vertices are calculated by a ranking function,and the relevance scores are used to determine the ranking order of neighbor vertices.The weight about an edge only represents the relationship between two vertices.Through calculating the relevance scores,the dependence between vertices can be obtained,and the ranking order of neighbor vertices can be determined.In order to implement queries in the cloud,an index needs to be built.Neighbor information of graph vertices,including vertex values,direction of the edge and relevance scores,is firstly built,and the neighbor information need to be encrypted.Then neighbor labels of graph vertices are built,and each label corresponds to a vertex.Neighbor information is inserted into the index,and the index is stored on the cloud server.When searching,a query user can send the encrypted query tokens to the cloud server,and the cloud server performs search operation by the index and the query tokens.After the retrieving,the cloud server returns the ranked search results to the query user.We formally analyze the adaptive semantic security of our method.Comparing PRNQ with SENQ by experiments,we find that the comprehensive performance of PRNQ is better than SENQ.In order to make sure that the neighbor query supporting boolean expression query requests can be executed on the outsourcing graph,the researches on problem of boolean neighbor query are conducted.In view of the undirected graph,a secure query method BNQ is proposed.The data owner first encrypts and processes the graph vertices,and then the normalized orthogonal set of graph vertices is built.Next,neighbor vector of each vertex is built.An index is built based on the neighbor vectors,and the index is stored on the cloud server.For ease of calculation,the boolean expression is converted to disjunctive normal form after processing and transformation.The cloud server performs search operations by the index and the disjunctive normal form,and returns the boolean search results to the query user.Formal analysis shows that our method meets adaptive semantic security.Comparing BNQ with SENQ by experiments,we find that the comprehensive performance of BNQ is better than SENQ.In order to make sure that the shortest path query supporting synonym search can be executed on the outsourcing graph,the researches on problem of shortest path query are conducted.In view of the undirected graph,we propose a method called SSPS to perform the shortest path query supporting synonym search over encrypted graph data.Graph data usually contain a lot of properties,and some properties can involve privacy information of users.Therefore,graph data need to be protected.We first convert all the graph vertices into new words through the stemming algorithm to meet the needs of synonym query.We concatenate two arbitrary different new words and encrypt them,and then we get an encrypted token.All the encrypted tokens are used to build an index based on the multiple branch query tree,and the index is stored in the cloud.Each encrypted token is divided into a number of substring,and all the substrings of an encrypted token are used to construct a tree branch from the root node.The contents about shortest paths are stored in the leaf nodes.When searching,a query user can send an encrypted query token to the cloud server.When receiving the encrypted query token,the cloud server divides it into several equal substrings,and perform search in the multiple branch query tree.After the retrieval,the cloud server returns the search results to the query user.Formal analysis shows the adaptive semantic security of our method.The comparative experiments demonstrate the performance and efficiency of SSPS.