Decentralizing Trust: Privacy-Preserving Path Discovery in Social Networks

TL;DR

In a world where Facebook and LinkedIn have a monopoly on our social graphs, this paper presents a way to reclaim that data. It proposes a protocol where two people can "meet" offline and discover if they share a mutual connection (up to 3 hops away) without disclosing their entire friend list to each other or a central server. It uses Token Flooding and Homomorphic Encryption to ensure that private relationships stay private.

The "Centralization" Trap

Social relationships are arguably our most sensitive data. A centralized social network is a privacy time bomb:

• Involuntary Leaks: Subpoenas or malicious insiders can expose entire graphs.
• Commercial Exploitation: Platforms sell relationship insights to advertisers.
• Connectivity Dependency: You can't verify if someone is "trusted" if you don't have an internet connection to ping the central server.

Existing solutions like "Trust Negotiation" or "Private Set Intersection" (PSI) only work for 1-hop (direct friends). Scaling this to 3-hop paths (the "friend of a friend of a friend" logic) without exposing the entire chain has been a major technical hurdle.

Methodology: The Tokenized Hash Tree

The authors solve this using a two-stage protocol:

1. The Token Flooding Phase (Preparation)

Every user $u$ generates a root seed $z$. They create tokens for their direct friends using $H(z||1)$. These friends then "obfuscate" the tokens further before passing them to their own friends, effectively building a distributed "Hash Tree."

The genius here is deterministic obfuscation. Since the hashing is standardized, the originator can pre-calculate every possible token that would exist at distance $d=2$ or $d=3$ in their ego-network.

2. The Path Discovery Phase (The Handshake)

When two users meet (e.g., Alice and Bob), they run a Private Set Intersection (PSI):

• Alice inputs her list of computed tokens (all the paths she could have).
• Bob inputs his list of received tokens (all the paths he is actually part of).
• If there is a match, Alice finds the "Bridge Contact" (her direct friend leading to Bob) and the distance, without seeing Bob's other friends.

3. Solving the "Structural Leak"

A simple hash tree leaks info: if Alice finds a path to Bob and a path to Charlie through the same token ancestor, she knows Bob and Charlie share a friend. To fix this, the Extended Scheme introduces randomization. Bridge contacts generate a pool of shuffled tokens for their neighbors, decoupling the identity of intermediate nodes from the path itself.

Reality Check: Scalability and Performance

The authors tested the theory on massive datasets from Flickr, Orkut, and YouTube.

• Storage: For most users, "flooding" only consumes about 2 MB of storage—easily handled by a modern smartphone.
• Computation: Heavily skewed. The "hubs" (users with thousands of friends) do more work, but for 90% of the network, the computation is negligible.
• Privacy vs. Utility: The system explicitly respects the "decline of value over distance." It focuses on $d\le 3$, which covers most "trusted" social interactions (recruitment, email whitelisting).

Critical Insight & Future Outlook

This paper is a significant milestone in Decentralized Identity (DID). It proves that you don't need a "Global Social Graph" to provide "Social Proof."

Limitations: The protocol currently assumes users won't lie about their degrees, though "noise" is added to mitigate this. Further research is needed to handle Malicious Actors who might attempt to "shorten" paths by sharing their own tokens with others outside the protocol.

Ultimately, this work lays the groundwork for a future where trust is calculated locally, and privacy is the default, not a feature.