Research On Privacy-Preserving Graph Data Processing Techniques In The Cloud

In recent years, the graph-structured data and its applications develop rapidly. The data grows larger and the demands for graph processing become more and more diverse, which makes it hard to be managed and processed at local servers. More and more customers want to outsource their graph-structured data into cloud for flexible management and processing. But graph-structured data usually contains rich and valuable information, and customers lose their control over the data in the cloud. The adversaries and even the cloud providers may attempt to obtain the information illegally. From customers’perspective, their graph-structured data faces serious risks of information leakage. How to enable privacy-preserving operations over customers’ graph-structured data becomes an important problem.Different graph processing techniques have different features and different privacy protection demands. This paper focuses on privacy protection for three important graph processing techniques, and solves the privacy protection problems of substructure similarity query, shortest distance computing and label-constraint query in cloud. The main contributions of this thesis are as follows:(1) To enable privacy-preserving substructure similarity query over the graph data in cloud, we propose a privacy-assured substructure similarity query solution. The proposed solution builds the secure index to represent the major information of the graph data based on privacy homomorphism and obscuration methods. Then the similarity query is carried out on the secure index, which enables privacy-preserving substructure similarity query over the graph-structured data. The analysis and experiments show that the proposed solution can efficiently execute the substructure similarity query and protect the relevant information.(2) To enable edge weight privacy protection during the shortest distance computing in cloud, we propose a privacy-preserving shortest distance computing method based on Paillier homomorphic encryption, which encrypts the edge weight before outsourcing. Following the breadth-first principle, cloud servers could iteratively compute the shortest distance from initial vertex extending to other vertices directly on the encrypted data, getting the shortest distance without privacy breaches. The analysis and experiments show that the method can protect the edge weight information and reduce the customers’local resource demands during the shortest distance computing.(3) To enable privacy-preserving label-constraint reachability query in cloud, we propose a new privacy-preserving label-constraint reachability query solution. The proposed solution builds a two-level secure index to respectively record the reachability information for the reachable vertex-pairs and the labels on their paths based on the cryptographic hash function and secure inner product scheme. Then the label-constraint reachability query can be effectively answered by a two-stage secure query algorithm. The analysis and experiments show the proposed solution can effectively protect the label-constraint reachability information and perform the query efficiently.