Securely Computing Clustering Coefficient for Outsourced Dynamic Encrypted Graph Data

Social networks are represented by graphs. Clustering coefficient is a measure of how closely knit the actors are. The higher the clustering coefficient of a node, the more is its importance in the network. When small enterprises, with low storage and computational power, want to outsource their data and computation to a third-party cloud, anonymization alone might not help to protect data privacy. Moreover, fear of data leak and misuse by unauthorized parties force the data owner to encrypt data before outsourcing to the cloud. This makes it difficult to perform queries on the data. It is necessary to design a technique that allows queries to be performed on encrypted outsourced graph data without leaking meaningful information.In this paper, we design a novel graph encryption technique that allows calculating clustering coefficient on the outsourced encrypted graph. The encryption also supports edge and neighborhood queries. To the best of our knowledge, these types of queries have not been possible together before efficiently on encrypted graphs. We show that the designed scheme is secure under chosen-query attack. Moreover, we implement a prototype of the scheme and test on real-life data. The implementation results show that the scheme is practical even for a large database.