PKcore: Privacy-Preserving Dense Subgraph Discovery in Mobile Social Networks

TL;DR

Finding "cohesive groups" in mobile social networks (MSNs) usually requires sharing your entire friend list—a major privacy nightmare. PKcore is a new distributed protocol that allows users to find a k-core (a group where everyone has at least $k$ friends) without ever revealing their social links to anyone else, not even the person starting the search. By combining Yao's Garbled Circuits and homomorphic encryption, it achieves optimal results with mobile-friendly performance.

Context: The Privacy Paradox in MSNs

Mobile Social Networks (MSNs) like FireChat or Meetup rely on short-range communication (Bluetooth/WiFi) rather than a central server. While this is great for "off-the-grid" communication, it makes finding dense subgraphs (essential for group activities) incredibly difficult. Current SOTA methods for k-core discovery are centralized, meaning they need a "God's eye view" of the network. In an era where 52% of users hide their friend lists, we need a way to calculate group density without exposing the underlying graph topology.

Methodology: The Core of PKcore

The authors solve this by transforming the standard iterative pruning algorithm for k-cores into a secure multi-party computation (MPC) workflow.

1. The Strategy: Pruning Without Peeking

In a standard k-core algorithm, you repeatedly remove any node with a degree less than $k$. In PKcore, this "is my degree $<k$?" check is performed inside a Yao’s Garbled Circuit.

• The Initiator (D) provides $k$.
• The Participant ($p_i$) provides their current degree.
• The Result: Only the encrypted boolean (is degree $\ge k$?) is produced.

2. Hybrid Security Architecture

To update degrees without revealing which specific neighbor was pruned, the protocol uses Additive Homomorphic Encryption. This allows a node to sum up the "survival status" of its neighbors while the values are still encrypted.

Figure 1: The flow of messages between the Initiator and MSN participants, showcasing the interaction between Yao's protocol and homomorphic updates.

Experiments & Results

The authors implemented the arithmetic operations on a Samsung S4 to prove that "academic" cryptography can run on "real-world" hardware.

• Optimal Correctness: The protocol is proven to return the exact same maximum k-core as a centralized algorithm.
• Performance: Even with the overhead of Garbled Circuits, the runtime remains feasible for mobile devices. For a typical network diameter, computation time stays within a range that won't drain a modern smartphone battery instantly.

Figure 2: Runtime computation costs show a manageable linear growth as the number of participants ($m$) increases.

Critical Insight & Conclusion

The brilliance of PKcore lies in its hybridization. Yao’s protocol is powerful but doesn't scale well to many-to-many communication; homomorphic encryption is great for aggregation but expensive for logic. By using Yao’s for the "logic gate" (the comparison with $k$) and homomorphic encryption for the "network aggregation," the authors found a "Goldilocks zone" for mobile privacy.

Limitations: The current model assumes semi-honest participants (they follow the rules but try to learn secrets). In high-stakes environments, a "malicious" user could potentially lie about their degree to manipulate the group formation. Future work moving towards "Verifiable Computation" would be the natural next step for this lineage of MSN research.