Social PaL: Bridging the Privacy Gap in Social Path Discovery

TL;DR

Social PaL is a scalable, decentralized system that lets you find out exactly how many "hops" away you are from someone else on Facebook or LinkedIn without telling the social network—or the other person—who your private friends are. By using a clever trick called ersatz nodes and cryptographic hash chains, it achieves high discovery rates even when most of your friends haven't signed up for the app yet.

The Problem: The "Centralization Tax" on Trust

In the physical world, we use social context to make trust decisions: "I'll lend you my charger because we have three friends in common." Online Social Networks (OSNs) allow us to do this digitally, but at a cost. When you check your "mutual friends" on a centralized platform, the provider learns your location, who you are interested in, and the frequency of your interactions.

Existing privacy-preserving methods (like the Common Friends protocol) were a step forward but had two fatal flaws:

1. The Bootstrapping Wall: If your mutual friend Charlie isn't using the same privacy app as you and Alice, the app simply won't find him.
2. The "Two-Hop" Limit: Most protocols stop at mutual friends (length 2), failing to detect longer chains (length 3 or 4) that still provide significant social proof.

Methodology: Ersatz Nodes and Hash Chains

Social PaL solves these issues through two core innovations:

1. Ersatz Nodes (The Ghost in the Machine)

The authors realized that the server already knows the social graph. When Alice joins Social PaL, the server learns who her friends are. For those friends who aren't Social PaL users, the server creates ersatz nodes. It generates a "fake" capability (token) for them. When Bob (another user) queries his social path, he can match against these ersatz capabilities. This allows Social PaL to "see" social paths that pass through non-members.

2. Hash Chains for Distance Estimation

To calculate distance without revealing the intermediate people, Social PaL uses hash chains. If a capability for a friend is $c$, a "friend-of-a-friend" capability is $h(c)$, and a "friend-of-a-friend-of-a-friend" is $h(h(c))$. By finding which "degree" of hash matches during a Private Set Intersection (PSI), the two parties can determine their distance (e.g., "We are 3 hops apart") without ever learning the identity of the people in the middle.

Figure: The Common Friends architecture which Social PaL extends to support longer paths and ersatz nodes.

Experiments: Real-World OSN Performance

The researchers didn't just theorize; they ran simulations on three different Facebook datasets (MHRW, BFS, and Social Filter) to test "coverage"—the probability of finding a path if one exists.

• 100% Accuracy: With ersatz nodes, length-2 paths are always found.
• High Utility at Low Adoption: Even if only 20% of users join, the system finds over 40% of all paths. At 40% adoption, coverage jumps to 70%.
• Scalability: The server implementation (using PHP/PostgreSQL/Nginx) was shown to handle bursts of requests efficiently, capable of supporting millions of users through a distributed architecture.

Figure: Comparison of discovery coverage with and without ersatz nodes. The purple lines show the dramatic leap in utility when non-system members are accounted for.

Critical Analysis & Applications

The genius of Social PaL lies in its pragmatism. By acknowledging that a central server is needed for "discovery" but shouldn't be trusted with "interaction data," it creates a hybrid trust model that is actually deployable.

Applications:

• SpotShare: An Android app where you can automatically share your mobile data hotspot, but only with people who are within 2 social hops of you.
• nearbyPeople: A "friend radar" that shows social distance to people physically nearby using proximity-based communication (D2D).

Limitations:

While Social PaL prevents the server from seeing who is interacting, the server still maintains a subset of the social graph. Future work involving Homomorphic Encryption or Trusted Execution Environments (TEEs) could potentially hide even this graph data from the server itself.

Conclusion

Social PaL proves that "privacy" and "utility" are not a zero-sum game in social networking. By using ersatz nodes to overcome the bootstrapping hurdle, the authors have provided a blueprint for how decentralized social apps can finally scale to the masses.