Privacy-Preserving Closest Similar Community Search on Attributed Graphs

Community search on attributed graphs has gained significant attention in recent years for its ability to provide meaningful and personalized results. Given a query community, a similar community search aims to identify the communities that are similar in structural and attributed characteristics to the query community. As real-world networks continue to grow in complexity and size, outsourcing graph data and search tasks to cloud servers not only saves local storage space but also significantly enhances search efficiency. Nonetheless, this inevitably raises concerns about data privacy since cloud servers are not completely trustworthy. In this paper, we research on privacy-preserving similar community search on graphs. We propose a privacy-preserving closest similar community search scheme for attributed graphs that leverages cloud servers to enhance search efficiency while safeguarding the sensitive information in the graph. We consider packaging communities using center vertices to evaluate relationships across communities without accessing details within the communities. To achieve this, we design a centrality score function that integrates attribute contribution and closeness centrality to identify the center vertex of a community. To ensure the security of sensitive information in the attribute graph, we construct three secure indexes for the original graph utilizing diverse cryptographic primitives. By searching secure indexes, cloud servers can answer the closest similar community searches without possessing any sensitive information about the attribute graph. We employ Paillier homomorphic cryptosystem and related protocols to support efficient and secure evaluation of the distance and similarity between two communities on secure indexes. The security analysis confirms that the proposed scheme can be against adaptive chosen-query attacks so as to achieve CQA2-security and experimental results demonstrate the efficiency of the proposed scheme.