Mnemosyne: Privacy-Preserving Ride Matching With Collusion-Resistant Driver Exclusion

Ride-Hailing Service (RHS) has drawn plenty of attention as it provides transportation convenience for riders and financial incentives for drivers. Despite these benefits, riders risk the exposure of sensitive location data during ride requesting to an untrusted Ride-Hailing Service Provider (RHSP). Our motivation arises from repetitive matching, i.e., the same driver is repetitively assigned to the same rider. Meanwhile, we introduce a driver exclusion function to protect riders' location privacy. Existing work on privacy-preserving RHS overlooks this function. While Secure k Nearest Neighbor (SkNN) facilitates efficient matching, the state-of-the-art neglects a collusion attack. To solve this problem, we formally define repetitive matching and strong location privacy, and propose Mnemosyne: privacy-preserving ride matching with collusion-resistant driver exclusion. We extend the simple integration of equality checking and item exclusion to a dynamic integration. We concatenate each prefix of an acceptable identity range to each location code when generating a ride request, i.e., secure mix index. We process each prefix of the driver identity to generate a ride response, i.e., a mix token. We build an indistinguishable Bloom-filter as an index to query the token. When matching riders with drivers, the colluding parties cannot distinguish identity prefixes from location codes. We build a prototype of Mnemosyne based on servers, smartphones, and a real-world dataset. Experimental results demonstrate that Mnemosyne outperforms existing work regarding strong location privacy and computational costs.