OSN Privacy: Finding Friends Without Revealing Your Soul

TL;DR

In the digital age, making new friends on social media often requires a "privacy sacrifice"—you show me yours, I'll show you mine. This paper, presented at ACM CCS'11, introduces a cryptographic workaround. It allows users to calculate how much they have in common with a stranger (Profile Similarity) using a "chain of friends" and advanced encryption, ensuring that neither the stranger nor the Social Network provider can snoop on your private attributes.

The Privacy Paradox in Social Discovery

When Alice finds Bob on a social platform and thinks they might be compatible, she faces three bad options:

1. Give up: Potential friendship lost.
2. Blind Friend Request: Privacy leaked if Bob turns out to be a "bad actor."
3. Private Message: A deadlock where both parties are too cautious to speak first.

Prior works in Private Set Intersection (PSI) often required both users to be online at the same time to perform the handshake. In the real world, Alice might browse Bob's profile while Bob is asleep. How do we compute similarity when the data owner is offline?

Methodology: Trusting the Chain

The core insight of the authors is to replace a "Trusted Third Party" (which doesn't exist) with two semi-trusted components: the OSN infrastructure and the existing friendship path between Alice and Bob.

1. Polynomial Splitting

Bob's profile attributes are represented as roots of a polynomial $F_b(x)$. To prevent the OSN from seeing his data, Bob splits this polynomial into two parts: $Q_b(x)$ and $R_b(x)$.

• The OSN gets $R_b(x)$.
• Alice eventually gets $Q_b(x)$ through a re-encryption chain. Neither part alone reveals Bob's attributes.

2. Proxy Re-Encryption (PRE)

To handle the offline problem, the protocol uses a chain of friends (e.g., Bob -> Charlie -> Dave -> Alice). Each friend provides a re-encryption key that "transforms" the ciphertext step-by-step until it can be decrypted by Alice's private key.

3. Homomorphic Matching

Once Alice has her share and the OSN has its share, they use Paillier Homomorphic Encryption. This allows Alice to compute the result of the full polynomial $F_b(x)$ at her own attribute points without the OSN seeing her values, and vice versa. If the result is "0", it's a match!

Experimental Insights & Results

The protocol demonstrates that:

• Asynchronous Discovery: For the first time, Alice can check her compatibility with Bob even if Bob hasn't been online for days.
• Security: Under the semi-honest model, the OSN learns nothing. Alice only learns the count of shared interests, not which specific interests they are (unless she performs a brute-force probe).
• Performance: The reliance on ElGamal and Paillier means the OSN does the heavy lifting. While this scales linearly with the number of attributes, it is feasible for standard social profiles (usually 10-50 attributes).

Critical Analysis & Future Directions

The "Honest-but-Curious" Limitation

The paper assumes the OSN and friends are semi-honest. If the OSN colludes with Bob's friends (Charlie or Dave), they could theoretically recover Bob's keys and his private data. In a modern adversarial environment, "Malicious" models are more realistic.

Scalability

As social networks grow, finding a "friendship chain" between any two random users might be computationally expensive for the OSN to index and serve in real-time.

Final Thoughts

This work remains a foundational reference for Privacy-Preserving Social Computing. It cleverly uses the "small world" property of social networks (the chain of friends) not just for social connectivity, but as a cryptographic routing mechanism for trust.