Research On Reachable Secure Query Technology For Large-Scale Encrypted Graph Dat

Graphs are widely used in many fields,such as biological networks,social networks,and road networks.It can be used to represent the relationship among entities.The social network can be viewed as a graph.In this graph,each user can be regarded as one node and the relationship between two users can be regarded as the edge.The reachability query is an important and common query in the social graph.It refers to querying whether there is a direct path from u to v.K-hop reachability query is a special reachability query,which can answer whether u can reach v within K hops.With the expansion of graph data,it brings heavy computational and storage burden for the data owner.The development of the cloud computing has brought us great convenience.It has brought us nearly unlimited storage space,fast computing,and low cost and a lot of convenience.Therefore,more and more data owners outsource graph data to the cloud server.To protect the structure of the graph,graphs are usually encrypted to send to the cloud server.For the cloud server,querying on encrypted graphs is a huge challenge.It is meaningful to design privacy-preserving reachability query scheme over large-scale graph data.In this thesis,mainly studies privacy-preserving reachability query over large-scale graph data,and proposed schemes are as follows:(1)We propose three schemes to support reachability query over encrypted largescale graphs with result verifiability.These schemes can realize the reachability query over encrypted graphs on the cloud server,and data users can verify whether the query results of the cloud server are correct.In order to protect the structure of the graph,we pad dummy nodes to the index.To protect the privacy of the graph data,we encrypt the padded index.To verify the query results of the cloud server,we propose the first scheme.This scheme generates verification tags for each node in the index.To reduce the communication burden,we proposed the second scheme.This scheme generates one verification tag for each two nodes on the graph.We propose the third scheme based on the second scheme.The third scheme reduces the computation overhead of the data user.The data owner sends the encrypted index and verification tags to the cloud server.The security analysis and the real datasets used in the experiment prove that our scheme is efficient and safe.(2)We propose the scheme to support K-hop reachability query over encrypted larger-scale graphs.To realize privacy-preserving K-hop reachability query,we design the BFST-D index over the plaintext graph,which is composed by the BFST table and the adjacent list D.When two nodes are in one spanning tree,the BFST table can realize the K-hop reachability query.When two nodes are not in one spanning tree,using the adjacent list D helps the K-hop reachability query.We utilize the pseudo-random permutation function,order-revealing encryption and Paillier encryption,to construct the secure index,which can protect the privacy of the graph data and realize the calculation over the encrypted graph data.The security analysis and the real datasets used in the experiment prove that our scheme is efficient and safe.