Beyond Simple Handshakes: Achieving Full Anonymity in Mobile Social Profile Matching

TL;DR

In the world of Mobile Social Networks (MSNs), meeting a stranger often involves "Profile Matching"—finding common interests without revealing your whole life. This paper introduces three protocols (eCPM, iCPM, iPPM) that move from simple attribute comparison to fully anonymous message delivery. The standout contribution is the eCPM+ strategy, which uses time-series prediction (ARMA model) to decide exactly when a user should change their pseudonym to avoid being tracked.

Perspective: The Linkability Problem

The fundamental issue in MSNs isn't just encrypting your profile; it's the uniqueness of the result. If you and a neighbor always get a "0.7 similarity score," an observer can link your current location to your past locations simply by watching that score. This paper categorizes this as Conditional Anonymity vs. Full Anonymity. The goal is to ensure that matching results themselves don't become a digital fingerprint.

Methodology: The Core Mechanisms

1. eCPM (Explicit Comparison)

The basic version allows an initiator to see if their attribute (e.g., "Expertise Level") is greater than, equal to, or less than the responder's. It uses Homomorphic Encryption to perform subtraction on ciphertexts.

• Insight: By multiplying the difference by a random factor $\varphi$, the exact difference is hidden, but the sign (positive/negative) remains visible to the initiator.

2. iCPM & iPPM (Implicit Matching)

To achieve Full Anonymity, the initiator shouldn't even know the comparison result explicitly. Instead, they receive a message.

• How it works: The responder prepares pairs of messages. The initiator retrieves one message "obliviously." If $A>B$, they get Message 1; if $A<B$, they get Message 0.
• Result: Neither party learns the attribute values, and the initiator doesn't even "learn" the comparison result—they only receive a functional piece of information (the message).

Figure 1: Comparison between explicit (Scenario 1) and implicit (Scenario 2) matching logic.

eCPM+: Adaptive Privacy via Prediction

While iCPM is mathematically "fully anonymous," it is computationally expensive. The authors propose an optimized version of the explicit protocol called eCPM+.

The core idea is Predictive Pseudonym Change. Using an Autoregressive Moving Average (ARMA) model, a user's device monitors its "Neighborhood Status." If the model predicts that the current pseudonym is about to become too "distinctive" (breaking k-anonymity), it triggers a pseudonym change before the breach occurs.

Figure 2: Tracking neighborhood status over time to predict privacy risks.

Experimental Validation

Using real-world Bluetooth contact traces from a conference (78 users), the authors demonstrated that static pseudonym changes (e.g., every 20 minutes) are inefficient.

• Key Finding: eCPM+ achieves a significantly lower Anonymity Break Period compared to constant-interval strategies.
• Trade-off: It uses slightly more pseudonyms than the "Post-adaptive" approach but provides a much more robust shield against intersection attacks.

Figure 3: Efficiency of pseudonym usage for 5-anonymity across different strategies.

Critical Insight & Conclusion

The transition from what the profile is to how the matching result is consumed is the next frontier of privacy. While homomorphic encryption provides the "how," the ARMA-based prediction provides the "when."

Limitations: The current iPPM protocol still reveals the "predicate structure" (the logic of the query) to the initiator. Future work must focus on Predicate Hiding, ensuring that even the criteria for a match remain a secret. This paper sets a high bar for distributed, privacy-first social interaction.