Towards Privacy-Preserving Travel-Time-First Task Assignment in Spatial Crowdsourcing

TL;DR

Spatial Crowdsourcing (SC) is the backbone of apps like Uber and TaskRabbit. While most privacy-preserving research focuses on travel distance, real-world efficiency depends on travel time. This paper addresses the "Secure Division" bottleneck by introducing a clever LCM-based transformation, allowing platforms to find the fastest worker without ever seeing their location or speed.

Problem & Motivation: The Distance vs. Time Paradox

Imagine two Uber drivers: Alice is 500m away but stuck in gridlock; Bob is 1000m away on an open highway. Traditional "Travel-Distance-First" assignment picks Alice, frustrating the user. "Travel-Time-First" is the logical choice, but it introduces a cryptographic nightmare.

To calculate time ($Time=Distance/Speed$) while keeping both variables secret, you need Secure Division. In the world of Homomorphic Encryption, division is computationally expensive and scales poorly. Previous attempts relied on the product of all speeds, which leads to massive numbers that cause ciphertext overflow, limiting the system to small groups or low speeds.

Methodology: The LCM Shortcut

The authors’ mathematical "Eureka!" moment was realizing they didn't need the exact travel time value; they only needed to compare them.

By finding the Least Common Multiple (LCM) of all worker speeds ($S_{lcm}$), the comparison $\frac{d_i}{s_i}<\frac{d_j}{s_j}$ can be rewritten as: $d_i\cdot \frac{S_{lcm}}{s_i}<d_j\cdot \frac{S_{lcm}}{s_j}$

This transforms division into multiplication, which is natively supported by the Paillier cryptosystem's homomorphic properties.

The Secure LCM Protocol

To compute the LCM without revealing individual speeds, the authors designed a protocol based on:

1. Prime Factorization: Workers factorize their speeds.
2. Aggregation Protocol (AP): Using a set of shared secrets, workers submit "flags" for each prime power factor ($p^k$) they possess.
3. Threshold Summation: The Server identifies the maximum power of each prime across the crowd to construct the global LCM.

Experiments & Results

The framework was tested against a real Gowalla dataset involving 3,036 workers.

1. Breaking the Speed Barrier

Previous SOTA methods (e.g., Liu et al.) fail when the maximum speed ($S_{max}$) exceeds 10 due to numerical overflow. As shown in the performance charts, the proposed LCM method remains stable regardless of the speed range, effectively removing the "speed bottleneck."

2. Efficiency vs. Privacy (DP Comparison)

When compared to Differentially Private (DP) approaches (To et al.), this framework achieved significantly shorter travel distances. Why? Because DP injects noise that degrades assignment accuracy. This protocol uses exact encryption, maintaining 100% utility while providing strong semi-honest security.

Critical Analysis & Conclusion

Takeaway

The core contribution is the shift from "How do we divide securely?" to "How can we avoid division entirely?" This mindset is crucial for deploying privacy-preserving algorithms on mobile devices with limited CPU/Battery.

Limitations

The system assumes a semi-honest model. If a worker or the platform is malicious (actively falsifying data rather than just trying to sneak a peek), the protocol doesn't have a built-in "Truth Discovery" mechanism. Furthermore, the Key Provider (KP) still plays a central role; a fully decentralized version without a TTP (Trusted Third Party) would be the next logical step.

Future Outlook

As ride-sharing and local delivery services increasingly face privacy regulations (like GDPR), move-to-earn or spatial task apps will likely adopt these lightweight LCM-style transformations to satisfy legal requirements without sacrificing user experience.