PROMPT: Balancing Social Rewards and Location Privacy via ε-Coresets

TL;DR

In the era of Waze and Foursquare, we trade our location history for traffic alerts and social status. PROMPT is a novel mobile framework that breaks the paradox of needing to share your identity while maintaining privacy. By utilizing ε-Coreset theory, it allows smartphones to locally calculate how much of a user's trajectory is "leaked" before a report is even sent, ensuring that an attacker can never reconstruct more than a user-defined fraction of their life.

The Motivation: Why Obfuscation and Anonymity Fail

Most existing location privacy solutions rely on two crutches:

1. Anonymity/Claking: Hiding who you are.
2. Obfuscation: Sending fake or noisy data.

However, in modern crowdsourcing, users want their identities known for rewards, and systems require high-fidelity data to be useful. Furthermore, centralized privacy servers are themselves massive honeypots for attackers. The challenge was: how can a resource-constrained smartphone analyze months of GPS traces (hundreds of megabytes) in milliseconds to decide if a new "Check-in" is safe?

Methodology: The Power of Geometric Approximation

The core innovation of PROMPT is the application of ε-Coresets to trajectory data.

1. What is a Coreset?

In computational geometry, a coreset is a small subset of points that approximates the original dataset for a specific query (like distance or density) within an error bound of $(1+ϵ)$. Instead of checking a new report against 100,000 raw GPS points, PROMPT checks it against a "coreset" of a few dozen points that capture the "geometric essence" of the user's mobility.

2. The Privacy Exposure Query

PROMPT defines a specific query that calculates the spatiotemporal correlation between shared reports and the actual underlying trajectories.

• Tracking Protection: If a set of reports provides a "good enough" approximation (an $ϵ$-coreset) of a full trajectory, PROMPT blocks the next report to prevent an attacker from "connecting the dots."
• Sensitive Location Protection: Using Shannon Entropy, the system ensures that sharing a report near your home doesn't make that location's frequency stand out. It forces the frequency of shared reports to be distributed such that an attacker cannot statistically distinguish a "home" from a "gas station."

Figure 1: PROMPT evaluates the perpendicular distance $D$ between shared reports and trajectory segments to determine exposure.

Experiments: Real-World Performance

The authors tested PROMPT on the CrowdAlert (Dublin SmartCity) and Microsoft Geolife datasets.

Scalability on Mobile

One of the most impressive results is the efficiency boost from trajectory compression and coresets. As seen in the figure below, the execution time stays exceptionally low even as the number of stored trajectories grows to 1,000. Figure 2: Execution time remains near 1 second for 1,000 trajectories, proving the feasibility of local processing.

Utility vs. Privacy

While strict privacy usually deletes data, PROMPT is "smart" about what it hides. With a privacy parameter $ϵ=0.6$, the system still allows users to share 83% of their reports, while keeping the percentage of trajectories successfully revealed by an attacker at effectively 0%.

Figure 3: Comparison showing PROMPT (solid lines) successfully keeping exposed trajectories near zero compared to no-protection baselines.

Critical Insights & Conclusion

PROMPT represents a shift from "hiding data" to "managing exposure." By using coresets, the authors solved the "Big Data on Small Device" bottleneck that hindered previous local privacy attempts.

Takeaway: Future crowdsourcing apps should stop asking users to trust a central server. Instead, they should provide the tools (like PROMPT) for the device itself to act as a "Privacy Firewall." While the current model focuses on individual applications, the logic could eventually be extended to a cross-app OS-level privacy manager.

Limitations: The framework currently assumes the attacker uses standard routing engines (like Google Maps) to fill the gaps between reports. If an attacker has sophisticated, personalized mobility models, the ε-Coreset bounds might need to be tightened.