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

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

Speakers: Fangyuan Sun

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=F2bg4286mdo

Overview

PACS enables privacy-preserving community search on attributed graphs outsourced to cloud servers. The system allows users to find structurally cohesive communities with the highest attribute relevance scores without revealing the graph data, community attributes, or user queries to the cloud. Built on homomorphic encryption and secure index structures, PACS achieves CQA2 adaptive security (secure against adaptive chosen-query attacks) while completing searches in milliseconds. Applications span social network marketing, citation network analysis, and biological network function module identification.

Background

▶ Watch: Attributed graphs and community search applications (0:00)

Attributed graphs model complex real-world networks by capturing both structural connections and semantic information (node attributes). Community search on these graphs finds groups that are both structurally cohesive (minimum degree constraint) and semantically aligned with query attributes (attributed driving score). Outsourcing these graphs to cloud servers for efficient search raises privacy concerns about exposing sensitive graph data and user query patterns.

Key Findings

▶ Watch: System entities and five-algorithm pipeline (4:00)

• Secure community index protects attribute information using cryptographic constructions
• Secure edge table based on homomorphic encryption protects graph structure
• Search completes within milliseconds on real-world social network datasets
• CQA2 adaptive security proven, protecting against adaptive chosen-query attacks
• Five-algorithm pipeline: key generation, index construction, token generation, privacy-preserving search, result decryption
• Multi-cloud server collaboration for secure comparison protocols
• Honest-but-curious cloud server threat model

Technical Deep Dive

▶ Watch: Key generation and secure index construction algorithms (6:00)

The system involves five entities: key generation center, data owner, cloud servers, and search users. The data owner constructs a secure community index (encrypted attribute vectors per community) and a secure edge table (encrypted adjacency information). Search users generate secure tokens from their queries, which cloud servers use to: (1) filter communities not meeting structural constraints via secure comparison, (2) compute attribute driving scores on encrypted data, (3) retrieve target community edges via homomorphic multiplication without revealing non-target edges.

Demo / Proof of Concept

▶ Watch: Three-step privacy-preserving search with homomorphic multiplication (8:00)

Evaluated on real-world public social network datasets. Index construction, secure search, and result decryption all complete within milliseconds.

Defensive Implications

▶ Watch: Security analysis and millisecond-level performance results (10:00)

PACS enables organizations to outsource graph analytics to cloud providers without exposing sensitive network data -- relevant for social network analysis, organizational network mapping, and biological research where graph structure is sensitive.

Key Takeaways

• Privacy-preserving community search on attributed graphs achievable in milliseconds
• Homomorphic encryption enables computation on encrypted graph data without revealing structure or attributes
• CQA2 adaptive security protects against sophisticated query-based attacks
• Applicable to social networks, citation networks, and biological networks
• Honest-but-curious cloud server assumption; malicious server model not addressed

About the Speaker(s)

Jane (presenting on behalf of Fangyuan Sun) is from IUTD. The research focuses on applied cryptography, searchable encryption, and privacy-preserving graph analytics.