# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 1 Introduction  
With the advent of GPS-embedded mobile devices and digital maps, Online Ride-Hailing (ORH) services have gained much popularity and have seen remarkable development in the past decade. Unlike traditional taxi services, ORH companies such as Uber and Didi provide a platform for riders to request a ride using few operations through their mobile devices, which has had a revolutionary impact on the ride-hailing industry [1]. According to the statistics of Didi Chuxing, they have completed over 10 billion ride-hailing orders [2]. Ride-matching is the primary function of ORH service, and it usually matches the nearest driver for any rider who starts a ride-matching request. To request the ride-matching service, the rider needs to submit his location information to the ORH service provider (i.e., the ORH company) through the ride-hailing application on their smartphone. Then the service provider matches the nearby drivers who update their locations in real time. In order to improve the traffic utilization and the matching success rate, some ORH services also provide an enhanced function, i.e., ride-sharing service, which enables several riders with similar traveling routes to share one driver. Ride-sharing is in the broad category of the sharing economy [3], which is environmentally friendly and beneficial to all participant entities of the service. For riders, it provides a financial and efficient alternative. Moreover, it enables drivers to cut down their traveling costs and improve the revenue with payment from several passengers. Besides, it reduces the emissions of CO\({}_{2}\)[4]. However, despite the convenience the ORH service brings, the privacy concern is also highly raised. For example, the largest Chinese ORH company, Didi Chuxing, was recently demanded to take off all applications from app stores due to a serious violation of data and privacy laws [5]. To request a ride, the rider must submit his ride information, which usually includes some private information on riders such as pick-up and drop-off locations and times. The submitted data can be analyzed for one's mobility patterns or can even be exploited to deduce one's home or working address. The leakage of users' private information invades their rights and sometimes even threatens their security. It is necessary to preserve the privacy of users, whether riders or drivers. To achieve that, many encryption techniques and privacy-enhanced solutions are designed for ride-hailing services [6; 7; 8; 9; 10; 11], which provide private ride-matching schemes but do not support ride-sharing. There are also a few privacy-preserving ride-sharing schemes including SRide [12], PRIS [13], and PrivatePool [14], but they can only enable ride-sharing matches over fixed locations. PSRide is a flexible ride-sharing matching scheme, but it does not support ride-sharing between multiple riders. PSRide supports group ride-sharing matching. However, it cannot find the shortest path to pick up and drop off all riders. Considering the issues stated above, we are motivated to research how to construct a private and practical ride-sharing mechanism, which supports flexible ride-sharing matching over multiple riders and meanwhile finds the shortest path with minimum detouring distance. However, we cannot compute the shortest path over plaintext precise locations of users due to the consideration of efficiency and privacy; thus, a zone-based method is applied to trade off between these factors. By hiding all users' locations in distinct zones, a user's privacy is well protected since enemies cannot distinguish from hundreds of points of interest in one zone. It is noteworthy that the matching is also computed over discretized zones, so the matching results are not necessarily optimal on a non-discretized map. In the following paper, expressions such as \"minimum detouring\" indicate the computing results over the zones.