Social PaL: Bridging the "Degrees of Separation" Without Sacrificing Privacy

TL;DR

The "Six Degrees of Separation" is a cornerstone of social trust, but finding those links usually requires handing over your entire social graph to Facebook or LinkedIn. Social PaL is a breakthrough system that allows two users to prove how many hops away they are (path length) without revealing their non-mutual friends or their identities to a central server. By introducing Ersatz Nodes, it solves the "ghost town" problem of previous privacy tools, finding 70% of paths even when most people haven't installed the app yet.

The "Centralization Trap" in Trust Discovery

When you're at a conference or using a ride-sharing app, you might trust someone more if you have a mutual friend. Currently, to find this out, you query a central OSN server. This simple query leaks:

1. Interest: You are looking for Person B.
2. Context: Your current location and time of interaction.
3. Social Topology: Your relationship patterns over time.

Prior decentralized works like Common Friends failed because of the Bootstrapping Problem. In those systems, for Alice to see a path to Bob through Charlie, all three had to be users of the privacy system. If Charlie wasn't "in," the link was invisible.

Methodology: The "Ersatz" Breakthrough

Social PaL introduces a brilliant architectural "cheat" called Ersatz Nodes.

1. Handling the Non-Users

When a Social PaL user (Alice) connects her Facebook, the Social PaL server sees her friends. For friends who don't use Social PaL yet (like Charlie), the server creates an Ersatz Node. It generates a "proxy capability" for Charlie and gives it to Alice. Now, if Bob (another user) also knows Charlie, he can see Charlie's ersatz capability through Bob's own connection. Suddenly, the path Alice-Charlie-Bob is visible even though Charlie never signed up.

Figure: How Ersatz nodes (white circles) complete the social graph.

2. Measuring Distance via Hash Chains

To discover paths longer than 2 (friend-of-a-friend-of-a-friend), the authors use a mathematical trick with Hash Chains.

• A user generates a capability $c$.
• They give $h(c)$ to 1st-hop friends.
• They give $h^2(c)$ to 2nd-hop friends. When two users meet, they compare these hashes. If a match is found between Alice's $h^i(c)$ and Bob's $h^j(c)$, they can mathematically deduce the path length $Dist(A,B)$ without seeing the names of the people in the middle.

Figure: The Social PaL Discovery Protocol using Bloom Filter PSI.

Experimental Results: It Actually Works

The researchers tested this against real-world Facebook "Small World" datasets.

• Coverage: Without Ersatz nodes, coverage is abysmal (often < 10%). With them, even at 20% adoption, the system can find over 40% of all possible paths.
• Scalability: The server is designed for the real world. Using Nginx and PHP (with suggested migration to HHVM), a single server can handle roughly 1.4 million users, assuming they refresh their capabilities 4 times a day.

Figure: Server response latency vs. request load.

Critical Insight: Why This Matters

The most impressive part of Social PaL is its Inductive Bias toward real-world deployment. Most academic privacy papers ignore the fact that users won't use a tool if it doesn't work on day one. By leveraging "Ersatz" info from the server, Social PaL provides immediate value.

Limitations & Future Work

• Server Trust: While the server doesn't see interactions, it still learns a subset of the social graph. Future iterations could explore Fully Homomorphic Encryption (FHE) to hide the graph from the Social PaL server itself.
• Tie Strength: A LinkedIn connection isn't the same as a best friend. The authors suggest adding "Tie Strength" in future updates to make trust decisions more nuanced.

Conclusion

Social PaL moves us closer to a world where "Digital Trust" is a decentralized utility. Whether it's safely sharing a Wi-Fi hotspot with a stranger or verifying a Tinder date's social standing, Social PaL shows that we can measure our social distance without losing our privacy in the process.