Fangyuan Sun (Qingdao University), Yaxi Yang (Singapore University of Technology and Design), Jia Yu (Qingdao University), Jianying Zhou (Singapore University of Technology and Design)

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.

View More Papers

The Role of Privacy Guarantees in Voluntary Donation of...

Ruizhe Wang (University of Waterloo), Roberta De Viti (MPI-SWS), Aarushi Dubey (University of Washington), Elissa M. Redmiles (Georgetown University)

Read More

MIMIR: Masked Image Modeling for Mutual Information-based Adversarial Robustness

Xiaoyun xu (Radboud University), Shujian Yu (Vrije Universiteit Amsterdam), Zhuoran Liu (Radboud University), Stjepan Picek (Radboud University)

Read More

QNBAD: Quantum Noise-induced Backdoor Attacks against Zero Noise Extrapolation

Cheng Chu (Indiana University Bloomington), Qian Lou (University of Central Florida), Fan Chen (Indiana University Bloomington), Lei Jiang (Indiana University Bloomington)

Read More