G2G: Breaking the Privacy Barrier in Group-to-Group Mobile Social Matching

TL;DR

Social networking in physical proximity is changing how we interact, but revealing personal interests to a group of strangers is a major privacy risk. G2G and G2G+ are new protocols that allow two groups of mobile users to calculate how well their interests align without revealing individual attributes. By using efficient permutation functions instead of complex encryption, they achieve high security with milliseconds of latency.

Background: The Limits of User-to-User Matching

Most existing Proximity-based Mobile Social Networks (PMSNs) focus on "1-on-1" matching. However, in the real world, social discovery often happens at the group level (e.g., a group of hikers finding another group in the same park). Current solutions either sacrifice privacy by using a central server or are too slow for mobile devices because they rely on heavy cryptography.

The Core Insight: Permutation as Privacy

The authors argue that we don't need "heavy" encryption to hide data. Instead, they treat group attributes as a matrix $P_{nimesd}$. By applying a series of random permutations ($\pi$), the data is shuffled such that:

1. The identity of which user owns which attribute is hidden.
2. In G2G+, the specific values of attributes are further masked by shuffling the attribute order itself.

Protocol Architecture

The system operates in two main phases:

• Pre-processing: Groups internally shuffle their attribute matrices using inverse permutations stored by trusted "gatekeeper" members.
• Matching: Groups exchange partial data and compute a Weighted Manhattan Distance. This metric provides a "fine-grained" score of similarity rather than a simple "yes/no" binary match.

Methodology: From G2G to G2G+

The paper defines two levels of privacy:

• Level-I (G2G): You know the match result, but you don't know who in the other group specifically triggered the match.
• Level-II (G2G+): A "black-box" approach. Members only learn the total group matching degree, and individual attribute levels are completely obscured by additional permutation layers.

One of the most clever architectural choices is the resilience to "Single Point of Failure." By distributing inverse permutation keys across multiple members ($M_1$ and $M_m$), the protocol can still function even if some members go offline during the calculation.

Performance and Results

The efficiency of G2G is its strongest selling point. Because it uses matrix multiplication and basic arithmetic for distance calculation, the overhead is minimal.

• Scalability: As the number of attributes ($d$) increases, the runtime grows linearly.
• Latency: Even with 100 attributes and 20 users, the matching process is virtually instantaneous for the end-user.

Fig: The impact of attribute count (d) on runtime shows high efficiency for real-time mobile use.

Critical Insight & Conclusion

G2G proves that in the trade-off between Security, Efficiency, and Accuracy, we can achieve a "sweet spot" by moving away from traditional encryption. By leveraging the social structure of the group itself (assuming at least two "honest" members), the protocol creates a self-shielding data exchange.

Takeaway: Future mobile social applications should look toward these "lightweight cryptographic" approaches to enable privacy-preserving features without killing battery life or user experience.