User-Friendly OSN Matching: Bridging Privacy and Social Discovery

TL;DR

In the world of Online Social Networks (OSNs), there is a constant battle between Privacy (hiding your data) and Utility (finding new friends). This paper presents a protocol that allows a user to match their profile against a stranger's—even if that stranger is offline—using a clever mix of Fuzzy Extractors and CAPTCHAs. It effectively prevents the OSN provider from harvesting user data while removing the need for users to exchange passwords manually.

The "Discovery Deadlock" and Motivation

Most users face a catch-22 on platforms like Facebook:

1. Strict Privacy: You hide your profile, but then nobody with similar interests can find you.
2. Open Profiles: You make your data public to find friends, but risk identity theft, stalking, and mass data mining by the platform itself.

Current cryptographic solutions often require "out-of-band" communication (e.g., Alice calling Bob to give him a decryption key). This is impractical for strangers. The author’s insight is to use the profile itself as the key.

Methodology: The Core Mechanism

The protocol relies on three technical pillars to achieve secure, offline matching:

1. Fuzzy Extractors (The Key Generator)

A Fuzzy Extractor $(Gen,Rep)$ allows a user to generate a secret key $r$ from their profile items. If another user has a profile that is "close enough" (within a set difference threshold $t$), they can reconstruct that same key $r$. This removes the need for out-of-band key exchanges.

2. CAPTCHA as a Security Layer

To prevent a malicious OSN from using its massive computing power to brute-force the Fuzzy Extractor or the encrypted profiles, the secret keys are embedded in CAPTCHA images. Since humans can read the CAPTCHA but (standard 2010-era) bots cannot, it ensures that only a real person is attempting a match, preventing mass data harvesting.

3. Homomorphic Encryption

The protocol uses an additively homomorphic scheme (like Paillier). This allows the OSN to compute the difference between Alice’s and Bob’s attributes (i.e., $Enc(a_i-b_i)$) without ever knowing what $a_i$ or $b_i$ actually are.

The Two-Stage Matching Process

Communication happens in a carefully orchestrated sequence involving Alice, the OSN's Matching App (MApp), and Bob’s stored data:

1. Eligibility Check: Alice uses Bob’s public "helper data" and her own profile to try and recreate Bob's secret key $r_b$. If Alice's profile is too different from Bob's, the MApp terminates the protocol.
2. Mutual Interest: If Alice passes Bob’s threshold, she receives a CAPTCHA containing Bob's private key. She then sends her encrypted profile to the MApp. The MApp performs the homomorphic subtraction and returns the results to Alice. Alice decrypts the result to see if Bob meets her criteria.

Experiments & Security Analysis

The paper focuses on a Semi-Trusted Threat Model. The OSN is expected to follow the protocol but will try to recover information automatically if possible.

• Against OSN: The OSN cannot perform "Automated Information Recovery" because it cannot bypass the CAPTCHAs to get the private keys.
• Against Strangers: A stranger (Alice) only learns Bob's details if she already shares enough common interests with him to satisfy his threshold.

Critical Insight & Conclusion

The true value of this work is the realization that social proximity can be its own credential. By using Fuzzy Extractors, the author turns "having common interests" into a cryptographic key.

Limitations

• CAPTCHA Vulnerability: As AI improves (OCR and Vision models), the "protection" offered by CAPTCHAs weakens significantly. Modern iterations would likely require Zero-Knowledge Proofs (ZKP).
• Computation Overhead: Homomorphic encryption and re-randomization at the server level can be computationally expensive for millions of users.

Final Takeaway

This paper serves as a foundational blueprint for decentralized social discovery. It proves that we can find "Kindred Spirits" in the digital void without sacrificing our entire digital identity to the platform provider.