Private Discovery of Social Contacts: Bridging Privacy and Trust in Social Clouds

TL;DR

In the era of social clouds, establishing trust between strangers often depends on finding "common ground" or shared friends. However, revealing one's contact list to a stranger is a massive privacy risk. This paper presents a Contact Discovery Scheme (CDS) that allows users to find mutual friends without leaking their non-mutual contacts. It introduces Contact Certification to prevent users from lying about who they know and optimizes the process for mobile performance using Interleaved IHME.

The "Social Wealth" Dilemma

In physical social interactions, we often mention mutual acquaintances to build rapport. In digital "Social Clouds," this becomes a data privacy nightmare. If Alice and Bob want to see if they share a friend, Carol, they usually have to reveal their entire contact lists.

Previous solutions like Private Set Intersection (PSI) had a fatal flaw: Impersonation. An attacker could simply list every celebrity or known figure in their list to see if you are connected to them. Without a mechanism to verify that Alice actually knows Carol, the privacy of the "social graph" is easily dismantled.

Methodology: The Core Architecture

The authors' solution rests on three pillars: Certification, Parallel Key Exchange, and Index-Hiding Encoding.

1. Contact Certification

To prevent users from populating their lists with "fake" contacts, every contact relationship must be certified. If Alice wants to claim Carol as a friend, she must possess a Contact Certificate (an RSA signature) issued by Carol herself. This ensures the "social wealth" is authorized.

2. The RSA-Based Discovery Mechanism

The scheme adapts the Okamoto-Tanaka identity-based key exchange. When Alice and Bob meet:

• They run multiple instances of this key exchange in parallel—one for every contact in their respective circles.
• If they both possess a certificate from the same user (same RSA modulus), their "session keys" will match.
• If the contacts don't match, the blinded RSA elements ensure no information—not even the identity of the contact—is leaked.

3. Efficiency via Interleaved IHME

The complexity of running hundreds of key exchanges is managed by Index-Hiding Message Encoding (IHME). Instead of sending individual messages, Alice bundles her encrypted contact data into a single polynomial. Bob "decodes" this polynomial at specific indices (the hashes of his own contacts).

To make this viable for smartphones (which have limited CPU), the authors introduced Interleaved IHME, splitting messages into smaller chunks ($v$) to speed up finite field arithmetic significantly.

(Note: The protocol flow involves blindings, padding, and polynomial-based IHME encoding/decoding as depicted in Figures 4 and 5 of the paper.)

Experiments: Performance in the Real World

The authors tested the optimized CDS on three tiers of hardware: XEON servers, Netbooks (AMD NEO), and Smartphones (ARMv7 600MHz).

Key Findings:

• Scalability: The protocol is linear ($O(n)$) in communication.
• Latency: Matching 100 contacts on a smartphone takes roughly 7 seconds. While slower than a PC (<1s), it is highly acceptable for an ad-hoc meeting or an initial trust-building phase.
• Bandwidth: 100 contacts require only ~30KB of data exchange, making it suitable for Bluetooth or slow mobile data.

Critical Analysis & Conclusion

Takeaway

This paper successfully moves private social discovery from theoretical "Secure Multi-party Computation" (which was too slow, taking 150s for 128 contacts) into the realm of practical mobile applications. The introduction of Contact Certification is a vital contribution that addresses the adversarial reality of social networks.

Limitations & Future Work

One notable limitation is the List Size Leakage. While the identities of the contacts are hidden, the degree of the polynomial reveals the total number of contacts Alice is checking. Future iterations would need "dummy" contacts to mask the true size of a user's social circle.

Furthermore, the paper opens the door for i-th degree discovery (friends of friends). Finding a "chain of trust" privately remains the "holy grail" for decentralized social PKI systems.

Summary Table