PLAM: Solving the "Preference Leakage" Dilemma in Mobile Social Networks

TL;DR

Mobile Social Networks (MSNs) are a double-edged sword: they offer "nearest restaurant" convenience but leak your most sensitive preferences (like health concerns) to service providers. PLAM is a new framework that achieves high-level privacy (k-Anonymity and l-Diversity) without needing a risky "trusted middleman." It uses advanced cryptography—Homomorphic Encryption and Verifiable Polynomials—to ensure neither your location nor your specific interests are exposed.

The Problem: The "Diabetes" Inference Attack

Most location-preserving techniques (like spatial k-anonymity) focus on hiding where you are. But authors of PLAM point out a critical gap: Preference Privacy.

Imagine Alice is near a hospital. Even if her exact location is masked, if she consistently queries "diabetes knowledge," the LBS provider can easily infer her medical condition. Existing solutions usually require a "Trusted Anonymizer" server to group users together. However, if this server is hacked, everyone's data is exposed. PLAM asks: Can we achieve this grouping cooperatively among users themselves?

Methodology: Decentralized Aggregation & Verifiable Math

PLAM’s architecture rests on two pillars of modern cryptography:

1. Cooperative Request Aggregation (The Privacy Shield)

Instead of sending a request alone, a user (U1) acts as an initiator. Using BV Homomorphic Encryption (BVHE), a group of nearby users contributes to a "service vector."

• How it works: Users combine their requests in an encrypted state. The initiator can decrypt the total count (ensuring at least $l$ distinct services are requested by $k$ users) but cannot see which user asked for which service.
• Result: The LBS provider receives a batch of $l$ services to perform, making it impossible to link a specific query to a specific pseudo-ID.

2. Verifiable Polynomial Computation (The Integrity Shield)

LBS providers often treat their algorithms as "trade secrets." They won't share the code, but how can Alice know the result isn't faked or lazy? PLAM uses a Witness Technique. The LBS function is treated as a multivariate polynomial $F(x,y)$. When providing an answer, the LBSP also provides a "witness" (a mathematical proof using bilinear pairings). Alice can verify the proof against a public "Merkle Hash Tree" to ensure the math is correct without ever seeing the actual function coefficients.

Experiments: The Latency vs. Privacy Trade-off

The big question for any mobile framework is speed. Since users must wait for others to join a group to satisfy $k$ and $l$ thresholds, delay is inevitable.

The authors conducted extensive simulations across different scenarios (1km² vs 1.5km² areas):

• Velocity Matters: High user mobility (2 m/s) actually helps privacy, as it increases the "encounter rate," allowing groups to form faster.
• Thresholding: The "Sweet Spot" for l-diversity is usually reached within the first 15 minutes of a user stopping to initiate a request.

Critical Insight & Conclusion

PLAM succeeds by shifting the trust from a single server to mathematical protocols. By integrating pseudo-IDs for location un-linkability and BVHE for service aggregation, it addresses the "Honest-but-Curious" threat model effectively.

Limitations: The current framework assumes users won't collude to Deanonymize each other. In a real-world "adversarial" social network, a malicious user could join a group just to spy on the initiator. The authors suggest that future iterations will need to harden the protocol against such internal collusion attacks.

In the era of ubiquitous mobile tracking, PLAM provides a robust blueprint for how we might reclaim our preference privacy without sacrificing the utility of local services.