Securing Social Connections: A Fuzzy Interest Matching Protocol for Privacy-First Friend Finding

TL;DR

Researchers have developed a new cryptographic protocol that allows social network users to find friends with similar interests without ever revealing their full profile. By integrating Bloom Filters with Paillier Homomorphic Encryption, the system identifies "fuzzy" matches (overlapping interests) while remaining secure against malicious attackers. For mobile users, an outsourced computation model is provided to offload heavy math to the cloud.

The Social Privacy Dilemma

In the era of Facebook and WeChat, finding "like-minded" individuals is a core feature. However, this usually requires a trade-off: to find a friend who shares your niche hobbies, you must upload those hobbies to a central server or share them with strangers. This exposes users to profiling and privacy breaches.

The technical challenge is a Private Set Intersection (PSI) problem: Alice has set $A$, Bob has set $B$; they want to know $|A\cap B|$ without revealing the elements in $A\setminus B$ or $B\setminus A$. Traditional PSI is often too slow for mobile apps or fails if one party acts maliciously to steal data.

Methodology: The Bloom Filter & Homomorphic Bridge

The authors propose a multi-stage protocol that shifts the heavy lifting away from raw data to a probabilistic data structure.

1. Interest Encoding via Bloom Filters

Interests are hashed into a bit array (Bloom Filter). If Alice likes {reading, movies}, specific bits in her array are flipped to 1.

2. Homomorphic Masking

Alice encrypts her Bloom Filter using Paillier Encryption. Because Paillier is additively homomorphic, the server can perform operations on the ciphertexts that correspond to adding the underlying plaintexts.

3. The Computation Hook

The server takes Alice's encrypted filter and "adds" Bob's filter to it. It then applies a random mask $r$. If both Alice and Bob had a '1' at a specific index (meaning a potential shared interest), the resulting decrypted value for Alice will be 0. If they differed, the mask $r$ turns the result into junk data, hiding the non-matching interests.

Performance & Outsourcing

One major bottleneck in mobile cryptography is modular exponentiation. The Paillier cryptosystem, while secure, is taxing for smartphones.

The paper introduces an Outsourced Computation Scheme. In this model:

• The client generates simple random pairs offline.
• The heavy modular multiplications are sent to a Cloud Provider.
• The Cloud returns a blinded result that the client can easily refine into the final intersection.
• Result: The client's online computation time is reduced to the order of magnitude of simple hash functions (micro-seconds), making it feasible for real-time friend discovery on 2026-era mobile devices.

Critical Insight: Security in the Malicious Model

Unlike "semi-honest" protocols that assume parties follow the rules, this protocol is proven secure in the Malicious Model. Even if a user provides a fake interest set or the server tries to manipulate the bit arrays to probe Alice's data, the zero-knowledge nature of the intersection check ensures that no more information than the final match count is leaked.

Conclusion

This work marks a significant step in making Privacy-Enhancing Technologies (PETs) practical for daily social interactions. By combining the space efficiency of Bloom filters with the mathematical rigor of Paillier encryption, the authors prove that "finding friends" doesn't have to mean "losing privacy." Future improvements may look toward handling variable-sized interest sets to make the "fuzzy" matching even more flexible.