Research On The Shortest Distance Query Technology For Large-Scale Graph Data With Privacy Protectio

As one of the most common data structures in computer science,graphs can represent various networks in reality.The shortest distance query is the most basic class of graph queries,which is widely used in social network analysis,road network navigation,protein analysis and other fields.With the expansion of the real network,the scale of the graph becomes increasingly large.It is increasingly difficult for clients to undertake the task of storing large-scale graphs and performing the shortest distance query.With the help of the emerging cloud technology,outsourcing the large-scale graph to the cloud servers not only save storage resources of the client,but also greatly improve query efficiency.To ensure the privacy and security of the graph,the graph is usually encrypted before outsourcing to the cloud server.However,the encryption operation also brings great challenges to the subsequent shortest distance queries on the graph.It is important to study the shortest distance query technology with privacy-preserving on the large-scale graph.This thesis mainly studies the shortest distance query technology that supports privacy-preserving on the large-scale graph,and proposes two schemes:(1)For the specific query needs of the user in the large-scale road network graph,we propose a scheme that can realize the constrained top-k nearest fuzzy keyword queries with privacy-preserving.This scheme can find the vertices that contain the specified keywords and are close to the specified vertex under a certain cost constraint,even if a typo is made by the user.To support fuzzy keyword query,the fuzzy keyword set is generated by the technology of wildcard for each vertex in the graph.A keyword inverted index is established based on the fuzzy keyword set.At the same time,the scheme adds the information of the cost constraint to the 2-hop cover label index.By utilizing a ciphertext integer comparison protocol based on the tree to calculate the constrained shortest distance between the query vertex and the candidate vertices.The security analysis shows the proposed scheme satisfies CQA2-security and experiments on real datasets show that the scheme is fully functional and efficient.(2)For the incremental updating needs of the large-scale dynamic network graph,we propose a privacy-preserving shortest distance query scheme that supports the dynamic update.The scheme can adapt to the incremental update operation in the real network and update the indexes on the cloud server to ensure the accuracy of subsequent query operations.To update indexes on the cloud server,an auxiliary adjacency index is constructed in addition to a 2-hop cover label index.With the help of the adjacency index,the cloud server can complete the breadth-first traversal based on the secure encrypted graph.The fake vertices with tags added in the adjacency index and the homomorphic Paillier cryptosystem ensure that the cloud server can traverse the vertices correctly on the encrypted graph while preserving the privacy information of the graph.The security analysis shows the proposed scheme satisfies CQA2-security and experiments on real datasets show that the scheme is complete and efficient.