  Many graph mining and analysis services have been deployed on the cloud,
which can alleviate users from the burden of implementing and maintaining graph
algorithms. However, putting graph analytics on the cloud can invade users'
privacy. To solve this problem, we propose CryptGraph, which runs graph
analytics on encrypted 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. The cloud runs graph analysis on the encrypted
graphs and obtains results which are also in encrypted form that the cloud
cannot decipher. During the process of computing, the encrypted graphs are
never decrypted on the cloud side. The encrypted results are sent back to users
and users perform the decryption to obtain 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 homomorphic encryption, the results analyzed from
the encrypted graphs are guaranteed to be correct. In this paper, we present
how to encrypt a graph using homomorphic 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 graphs, we propose hard
computation outsourcing to seek help from users. Using two graph algorithms as
examples, we show how to apply our methods to perform analytics on encrypted
graphs. Experiments on two datasets demonstrate the correctness and feasibility
of our methods.
