PACS: Privacy-Preserving Attribute-Driven Community Search over Attributed Graphs

—In data-driven applications, attribute-driven community search has attracted increasing attention, which aims to help users find high-quality subgraphs that meet specific requirements over attributed graphs. Nevertheless, few works consider data privacy when performing community search. One critical reason is that real-world graphs continue to grow in size, and attribute-driven community search involves computing complex metrics on encrypted graph data, including structural cohesiveness and attribute correlation, which are too time-consuming to be practical. This paper is the first to propose a practical scheme for Privacy-preserving Attribute-driven Community Searches on the cloud, named as PACS. PACS enables servers to efficiently respond to attribute-driven community searches in near-millisecond time, without accessing sensitive information about the attributed graph and search results. To achieve this, we design two structures, a secure community index and a secure edge table, for protecting the privacy of the original attributed graph. The secure community index enables cloud servers to efficiently identify the target community that meets structural cohesiveness and has the highest attribute score. In particular, we employ inner product encryption to evaluate the attribute-driven scores of communities based on encrypted attribute vectors. The secure edge table, constructed by BGN homomorphic encryption, allows cloud servers to securely retrieve the edge information of the target community without knowing its details. We perform a thorough security analysis that demonstrates PACS achieves CQA2-security. Experimental evaluations on real-world social network datasets show that PACS achieves near-millisecond efficiency in processing attribute-driven community searches.