CryptGraph: Privacy Preserving Graph Analytics on Encrypted Graph

Many graph mining and analysis services have been de-ployed on the cloud, which can alleviate users from the burden of implementing and maintaining graph algo-rithms. However, putting graph analytics on the cloud can invade users ’ privacy. To solve this problem, we propose CryptGraph, which runs graph analytics on en-crypted graph to preserve the privacy of both users’ graph data and the analytic results. In CryptGraph, users encrypt their graphs before uploading them to the cloud. Cloud runs graph analysis on the encrypted graphs and obtains results which are also in encrypted form that the cloud cannot decipher. The encrypted results are sent back to users and users do the decryption to get the plaintext results. In this process, users ’ graphs and the analytics results are both encrypted and the cloud knows neither of them. Thereby, users ’ privacy can be strongly protected. Meanwhile, with the help of homo-morphic encryption, the results analyzed from the en-crypted graphs are guaranteed to be correct. In this pa-per, we present how to encrypt a graph using homomor-phic encryption and how to query the structure of an encrypted graph by computing polynomials. To solve the problem that certain operations are not executable on encrypted graph, we propose hard computation out-sourcing to seek help from users. Using two graph algo-rithms as examples, we show how to apply our methods to perform analytics on encrypted graphs. Experiments on two datasets demonstrate the correctness and feasi-bility of our methods