Encrypted Matchmaking: Securing Geosocial Networks Against Untrusted Servers

TL;DR

In the age of Geosocial Networks (GSNs), finding nearby friends often means sacrificing privacy to service providers. This paper introduces a Privacy-Preserving Matchmaking System that leverages a novel Searchable Encryption (SE) scheme. It allows users to perform proximity-based friend discovery and attribute matching (including range queries like "age > 25") without the central server ever "seeing" the actual location or profile data.

The Motivation: The Privacy-Utility Tradeoff

Most location-based services (LBS) operate on an "open-to-all" policy regarding user data. To find a nearby user with similar interests, you must tell the server exactly where you are and what you like. This creates a massive honeypot for hackers and a goldmine for untrusted service providers.

Existing solutions fall short:

• Obfuscation/Anonymity: Often degrade the quality of service or require a "trusted" middleman.
• Private Information Retrieval (PIR): Mathematically sound but computationally ruinous for mobile devices.
• Existing SE: Often limited to simple keyword matching, failing to handle numerical ranges or flexible friend discovery.

The authors' insight was to treat profiles as vectors and use Matrix-based Encryption to enable comparisons directly in the encrypted domain.

Methodology: Matrix Inversion and Vector Splitting

The core of the system is a specialized Searchable Encryption scheme. Here is the high-level logic:

1. Vectorization: Profiles are converted into numerical vectors $P$. Strings are hashed, and numbers are kept as-is.
2. Encryption (Enc): The data is multiplied by two secret invertible matrices ($M_1,M_2$). A random binary string $S$ acts as a splitting indicator to add noise and prevent statistical attacks.
3. Token Generation (TokenGen): When a user searches, the "Base Station" (a localized trusted entity) helps generate an encrypted trapdoor $t_Q$.
4. Secure Comparison: The server performs a dot product-like operation between the encrypted profile and the trapdoor. The sign of the result determines if the match is successful (Supports $=,>,<$).

Fig 1: The architecture involving multiple authorities and a localized infrastructure (Base Station) to manage authentication.

Experimental Results

The authors evaluated the system using a C++ implementation on a 1.4 GHz machine. They focused on three key metrics: index generation, search time, and update efficiency.

• Scalability: Even with the attribute count increasing to 200, the search time remains within acceptable limits for real-time mobile interactions.
• Computational Offloading: A major highlight is the system's ability to move heavy key updates to the service provider without compromising the underlying secret matrices.

Fig 4 & 5: Performance metrics showing the linear growth of search time and efficient handling of updates.

Critical Insights & Future Outlook

This paper moves beyond the "all-or-nothing" approach to privacy. By using a localized trusted infrastructure (like a Base Station) to handle the heavy lifting of authentication and trapdoor generation, it reduces the burden on the end-user's mobile device.

Limitations: While the matrices provide efficient search, they are susceptible to certain "Known Plaintext Attacks" if the attacker can guess enough profile-trapdoor pairs. Furthermore, the reliance on a "Trusted Base Station" implies that privacy is localized; if the Base Station is compromised, the security of local users is weakened.

Takeaway: This work is a significant step toward Functional Encryption in social media. It proves that we don't need to trust big-tech servers with our data to enjoy the benefits of "finding friends nearby."