B-Mobishare: Securing Your Social Graph and Location with Bloom Filters

TL;DR

B-Mobishare is a refined privacy framework for mobile social networks that prevents service providers from "connecting the dots" between your location and your friends. By replacing raw data transmission with a Bloom Filter-based verification protocol, it achieves high security against social network de-anonymization with significantly lower computational costs than traditional encryption methods.

Context: The Privacy-Utility Tradeoff in mOSNs

Mobile Online Social Networks (mOSNs) thrive on location sharing—finding friends nearby or "checking in." However, this convenience creates a goldmine for adversaries. Even if you use a pseudonym (fake ID), the frequency and pattern of your queries can reveal your identity and your entire social circle. Previous works like Mobishare introduced dummy locations to hide the user, but they failed to protect the Social Graph itself from curious server providers.

The Problem: The "Honest-but-Curious" LBS

In a typical architecture, there's a Social Network Server (SNS) and a Location Based Server (LBS). Even if they don't openly collude:

• LBS Insights: The LBS sees location updates and queries. Over time, it can link fake IDs to real-world movements.
• Social Relation Leakage: When the SNS sends a friend list to the LBS to find who is nearby, the LBS learns exactly who you are friends with. This allows for de-anonymization attacks that bridge the gap between "fake ID" and "real person."

Methodology: The Bloom Filter Shield

The core innovation of B-Mobishare is the introduction of a Bloom Filter as a cryptographic filter between the SNS and LBS.

1. System Architecture

The system involves four entities: the User, the Cellular Tower (CT - trusted), the SNS (manages identities), and the LBS (manages locations).

2. The Verification Protocol

When a user queries for nearby friends:

• Step 1: The SNS generates a "fake friend-list" (using the real-fake IDs of the user's friends).
• Step 2: Instead of sending this list, the SNS maps these IDs into a Bloom Filter ($B{F}_f$).
• Step 3: The LBS receives the Bloom Filter and checks its internal location database. It only returns location data for entities that "pass" the filter test.
• Step 4: Because Bloom Filters are one-way (you can check membership but cannot easily extract the members), the LBS cannot learn the full friend list.

Experiments & Results: Efficiency vs. Security

The researchers analyzed the security against location and social relationship threats.

Security Analysis

• SOTA Comparison: Unlike [12] which used the Paillier Cryptosystem, B-Mobishare avoids the massive overhead of homomorphic encryption.
• False Positives: Bloom Filters have a known "False Positive" rate. However, the authors show that with a bit-array $m$ of $10^5$, the error rate $p$ is nearly negligible, and any remaining errors are filtered out by the SNS before reaching the user.

Performance Table

The following table outlines the symbols and parameters used to maintain this efficiency:

Critical Insight & Conclusion

The genius of B-Mobishare lies in its procedural shift. By moving the filtering logic to a probabilistic data structure, it effectively creates a "zero-knowledge-lite" environment.

Takeaway: In the world of mobile security, "Good Enough" privacy with high performance often beats "Perfect" privacy that drains a smartphone's battery in minutes. B-Mobishare strikes this balance by acknowledging that while we can't stop servers from seeing data, we can stop them from seeing relationships.

Limitations: The model assumes the SNS and LBS do not collude. If these two entities merge or share databases, the Bloom Filter protection is bypassed, highlighting a lingering challenge in centralized mOSN architectures.