Research On Privacy-preserving Subgraph Isomorphic Query Technolog

Benefiting from the cloud computing,graph owners tend to store their data graphs on the cloud server to release the local computation and storage burden.Subgraph isomorphism query is an important graph query operation in graph database.Since the data stored on the cloud server may be leaked due to the attack on the cloud server,the graph data owner must encrypt the data before uploading.In order to implement privacy protected subgraph isomorphic query on the cloud server,scholars have conducted extensive research and proposed some schemes.However,most of these schemes need to use complex calculations such as data mining to build indexes for the database,which brings a high computational burden to the graph data owner.Some schemes need to traverse the entire index to find the data graph that meets the requirements,which makes the query inefficient.And the previous subgraph isomorphic query schemes under privacy protection are mainly designed for static databases,which can not meet the needs of dynamic updating of databases.This thesis mainly studies the subgraph isomorphic query technology under privacy protection,and puts forward two schemes:(1)Aiming at the problems of slow indexing and low query efficiency in the existing privacy protected subgraph isomorphic query schemes,an efficient privacy protected subgraph isomorphic query scheme is proposed.In this scheme,in order to speed up the establishment of the index,the enumeration algorithm is used to extract the trees and cycles in the data graph as the features of the data graph,and the feature vector is established for the data graph through hash mapping.In order to improve the query efficiency of the index,clustering algorithm is used to classify the feature vectors,and then a tree vector index is established for the graph database.Each leaf node in the tree index represents a data graph.In order to support the semantic security of the graph and protect the privacy of the data,the secure inner product computing technology is used to encrypt the index and realize the query.Finally,the security analysis and experiment results of the specific scheme prove that the proposed scheme is safe and efficient.(2)In order to solve the problem that the query index cannot be updated synchronously with the graph database,a privacy protected subgraph isomorphic query scheme is proposed.This scheme is implemented on the basis of the scheme proposed in(1).In this scheme,in order to better support the needs of dynamic updating of graph database,a feature vector list is used to store similar feature vectors.In order to realize the synchronous dynamic updating of the security index and the graph database,three updating algorithms are proposed: adding feature vectors to the secure index,deleting the feature vectors in the secure index and modifying the feature vectors in the secure index.Finally,we prove that our proposed scheme is safe through security analysis and efficient through experiments.