Precise & Private: Solving the "Next-Door Neighbor" Problem in Mobile Social Matching

TL;DR

Mobile Social Networks (MSNs) allow you to find "missed connections" based on where you've been. However, revealing your location history is a privacy nightmare. This paper proposes a fine-grained matching scheme that uses an overlapping grid system to fix accuracy errors and a weighted matching approach to drastically slash the battery drain on mobile devices.

Background: The Hidden Complexity of Digital Encounters

Most privacy schemes for location matching treat space as a simple chessboard. If two users are in the same "cell" at the same time, they've met.

The Problem: What if you are standing on one side of a line and your friend is 2 meters away on the other side? In a standard grid, the system thinks you've never met. This is the Boundary Problem. Additionally, recording data every 10 minutes leads to tens of thousands of records per year—too much data for a smartphone to encrypt and exchange without killing the battery.

Methodology: The Core Innovations

1. The Overlapping Grid System (Physics Intuition)

Instead of simple squares, the authors use a system where each location is checked against its own cell and the surrounding neighbors.

• Logic: If two users are within distance $2a$ (where $a$ is the triangle side length), they are guaranteed to be flagged as an encounter.
• Architecture: By defining specific rules for cell index neighbors (based on line and column parity), the system creates a "buffer zone" that prevents the "wrongly judged no-encounter" scenario.

Fig 1: The basic idea of overlapping cells to ensure matching precision.

2. Weighted Temporal Compression

The authors observed that humans are creatures of habit. You likely spend 8 hours in an office or 10 hours at home. Instead of treating each 10-minute interval as a new data point to encrypt, the scheme collapses duplicates:

• Old Way: {(9:00, Office), (9:10, Office), (9:20, Office)} $\to$ 3 Encryptions.
• Proposed Way: {(Office, weight: 3)} $\to$ 1 Encryption. This "Fine-grained" approach shrinks the profile size, making the Private Set Intersection (PSI) protocol viable on mobile hardware.

3. Privacy via Commutative Encryption

The protocol uses a three-pass commutative encryption:

1. Alice encrypts her set and sends it to Bob.
2. Bob encrypts Alice's set (while it's still encrypted by her) and sends back his own encrypted set.
3. Alice encrypts Bob's set. Because the encryption is commutative ($E_a(E_b(x))=E_b(E_a(x))$), they can find the intersection without ever seeing the raw coordinates.

Experiments & Results

The authors tested the theory using physical Samsung Nexus S devices. The results were categorized into two main victories:

• Accuracy: The overlapping grid successfully captured "near-misses" that previous SOTA models (like P-match) failed to detect.
• Efficiency: As shown in the performance graphs, as the number of profile items increases, the computation overhead for the proposed scheme stays significantly lower than traditional PSI methods.

Fig 2: Comparison of computation overhead between the proposed scheme and P-match.

Critical Analysis & Conclusion

Takeaway

The genius of this paper isn't just in the cryptography—it's in the spatial-temporal preprocessing. By understanding human behavior (staying in one place) and spatial geometry (overlapping grids), they solved a math problem with a physical intuition.

Limitations

While the protocol is resilient against passive eavesdropping, the authors admit it is vulnerable to Sybil attacks. A malicious user could create dozens of fake identities to "probe" someone's location history through repeated matching requests. Future iterations would likely require an authentication server or a "Matching Quota" to prevent such data mining.

Future Work

The leap from discrete time points to continuous "period matching" opens the door for more complex MSN features, such as "Social Trajectory Matching," where users find friends who share a specific commute or travel path rather than just a single spot.