BCE: Scalable Common-Friend Estimation in DOSNs Without Cryptography

TL;DR

Recommending friends in Distributed Online Social Networks (DOSNs) is a privacy tightrope walk: how do you find mutual connections without exposing your entire friend list? This paper introduces BCE, a framework that uses Bloom Filters and a clever three-party intersection trick to estimate common friends accurately and scalably, all while avoiding the performance tax of heavy cryptography.

Background: The Price of Privacy

In decentralized social networks like Mastodon or Diaspora, there is no central server that knows everyone. To suggest a new friend, the system must calculate the "proximity" between two strangers.

• The Old Way: Exchange raw friend lists (Violates privacy; high bandwidth).
• The "Secure" Way: Use Private Set Intersection (PSI) based on homomorphic encryption (Extremely slow; high CPU usage).

The authors of BCE argue that we can achieve a "good enough" level of privacy using probabilistic data structures and the existing trust of mutual friends.

The BCE Insight: Why Cryptography isn't Always Necessary

The core motivation for BCE is two-fold:

1. Identifier Robustness: P2P networks already use 160-bit SHA-1 hashes for user IDs. Because the search space is ($2^{160}$), dictionary attacks are computationally infeasible.
2. Intersection Delegation: Instead of Alice sending her Bloom Filter to a stranger, Bob, she sends it to a mutual friend, Carol. Carol calculates the intersection and sends only the result back.

Methodology: How It Works

1. Representation via Bloom Filters

Each user maintains a Bloom Filter (BF) representing their friends' identifiers. To handle the dynamic nature of friendships (users adding more friends over time), BCE introduces Variable-Length Bloom Filters. If the false positive rate exceeds a certain threshold ($T$), the filter size ($m$) is adaptively increased.

2. The Intersection Logic

When Alice and Caven are two hops away (connected by a mutual friend, Bob), the process follows these steps:

• Alice and Caven push their Bloom Filters to Bob.
• Bob calculates $IBF=BF(Alice)\cap BF(Caven)$ using a bitwise AND operation.
• Bob sends the resulting $IBF$ back.
• Alice queries the $IBF$ against her own friend list to see who the mutual connections are.

3. Probabilistic Privacy

The paper provides a mathematical proof that the Intersection of Bloom Filters (IBF) is "insensitive" to any single identifier. The probability of one bit changing when a single friend is added is less than 0.2 in most cases, making it nearly impossible for an attacker to deduce specific members of the original set from the intersection.

Experimental Results

The authors tested BCE against real-world social graphs from Facebook and Flickr, comparing it with Proximity Embedding (PE) methods.

• Accuracy: BCE achieves nearly 100% accuracy (lowest NMAE) as the threshold $T$ reaches $10^{-6}$.
• Performance: Unlike matrix factorization (PE), which fails to capture the high-dimensional nature of social links, BCE directly targets the intersection, resulting in orders of magnitude better precision.

Critical Analysis & Conclusion

Takeaway: BCE proves that for high-speed, decentralized applications, probabilistic data structures can replace encryption if the network topology allows for "trusted intermediaries" (mutual friends).

Limitations:

• The "Cold Start" Problem: If Alice and Caven have zero mutual friends, BCE cannot help them find each other, as there is no intermediary to compute the intersection.
• Semi-Honest Model: The system assumes nodes are curious but follow the protocol. If a node (like Bob) was actively malicious and fabricated friend lists, the system would require additional verification layers.

Future Outlook: This approach could be highly relevant for modern Web3 social protocols where user privacy and gas costs (computation) are both at a premium. Integrating differential privacy "noise" into the Bloom Filter bits could further harden it against sophisticated statistical attacks.