Fine-grained Private Matching: Balancing Social Discovery and Data Privacy in PMSN

TL;DR

This research tackles the "circular dependency" in mobile social networking: the need to share personal data to find compatible people versus the fear of disclosing sensitive info to strangers. The authors present a breakthrough suite of protocols that allow mobile users to find "matches" based on precise interest levels (e.g., how much you like cinema, not just if you like it) using the Paillier cryptosystem. Their method is up to 200x faster than previous state-of-the-art approaches, making real-time private matching feasible on standard mobile devices.

Background: The Limits of Coarse-Grained Matching

Proximity-based Mobile Social Networking (PMSN) relies on direct device-to-device communication (WiFi/Bluetooth). Prior work focused on "all-or-nothing" attributes: Alice and Bob both have the tag "Movies," so they match. However, this ignores nuances. If Alice goes to the cinema twice a week and Bob goes once a month, they might not be as compatible as they seem.

The challenge is that fine-grained data (numeric interest levels) is more sensitive. Disclosing that you have a "Level 10" interest in a specific medical symptom or political view to a stranger nearby is a major privacy risk.

The Core Insight: Mapping Distances to Dot Products

The authors categorize privacy into three levels:

• Level-I: Alice learns the result; Bob learns the metric used.
• Level-II: Alice learns the result; Bob learns nothing.
• Level-III: Alice only learns if the result is below a threshold; Bob learns nothing.

To achieve this efficiently, the paper uses a clever mathematical transformation. Instead of calculating the ${\ell }_1$ distance ($\sum |u_i-v_i|$) directly—which is hard to do under encryption—they convert the numeric values into unary vectors.

For example, if an interest level is 3 (on a scale of 5), the unary vector is $⟨1,1,1,0⟩$. By doing this, the ${\ell }_1$ distance between the original numbers becomes equivalent to the ${\ell }_2^2$ distance between these new vectors. This allows the team to use a Secure Dot-Product protocol as the engine for all matching calculations.

Methodology & Architecture

The protocols rely on the Paillier Cryptosystem, chosen for its additive homomorphic properties. This allows Bob to perform calculations on Alice's encrypted data without ever seeing the raw numbers.

Fig 1: Protocol execution latency showing the significant speed advantage of the proposed methods (Protocols 1-3) over existing RSV and DA schemes.

The "Self-blinding" property is specifically used in Protocol 2 and 3 to ensure Bob can send a result back to Alice that only she can decrypt, while Bob adds a layer of "random noise" (blinding) that ensures he learns nothing about the final similarity score.

Performance: Breaking the Latency Barrier

Previous methods like RSV or DA were theoretically sound but practically dead. Waiting several minutes (200-400 seconds) for a "handshake" in a social setting is unacceptable.

By optimizing the number of expensive modular exponentiations performed online (during the handshake) and moving most of the heavy lifting to an offline pre-computation phase, the authors achieved:

• Online Time: ~1.5 seconds for 200 attributes.
• Communication: Linear growth, manageable over Bluetooth/WiFi.

Table 1: Theoretical overhead breakdown demonstrating fewer expensive 'exp' (exponentiation) operations in the proposed protocols.

Critical Analysis & Takeaways

The brilliance of this work lies in its scalability. By defining a "similarity score" that is additively separable, the authors even extended their work to handle MAX distance (the maximum difference in any single attribute), which is traditionally a non-linear and difficult operation in homomorphic encryption.

Limitations:

• The protocol assumes a "semi-honest" model. A truly malicious user could potentially craft a fake profile to probe the other party's interests (though Level-II and III privacy mitigate this).
• It requires the distribution of Paillier public keys, which implies a basic level of PKI or initial trust.

Conclusion: This paper provides the strongest evidence yet that fine-grained privacy doesn't have to come at the cost of performance. For future PMSN apps, these protocols offer a blueprint for "privacy-by-design" that respects the limited battery and CPU of mobile hardware.