PrigSim: Towards Privacy-Preserving Graph Similarity Search as a Cloud Service

Graphs are widely used to model complex structured data in many applications. With the proliferation of cloud computing, it is popular to store and query graphs in the cloud. Among others, graph similarity search, which aims to retrieve from a graph database graphs similar to a query graph, has received wide attentions and benefited various domains such as cheminformatics, computer vision, and more. Deploying graph similarity search services on the cloud, however, raises critical privacy concerns on the information-rich graphs. In this article, we initiate the first study on privacy-preserving graph similarity search in cloud computing. We design, implement, and evaluate PrigSim, a novel system allowing the cloud to host an outsourced encrypted graph database and support secure graph similarity search, where the graph similarity is measured by the well-known metric called graph edit distance. PrigSim is built from a customized and delicate synergy of insights on graph modelling, lightweight cryptography, and data encoding and padding, providing protections for the confidentiality of data content associated with graphs, as well as hiding the connections among vertices. Extensive experiments demonstrate that the security design of PrigSim is accuracy-preserving, and presents modest performance overheads (with 9 x - 15x higher query latency than the plaintext baseline).

Automated summary

This article presents a study on privacy-preserving graph similarity search in cloud computing. The authors designed and implemented a novel system called PrigSim, which allows for storing and querying encrypted graph databases in the cloud while maintaining secure graph similarity search. Through the use of graph modeling, lightweight cryptography, and data encoding, PrigSim protects the confidentiality of data content associated with graphs and hides connections among vertices. Extensive experiments show that PrigSim's security design is accurate and introduces acceptable performance overheads.