# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details  
We now describe the construction details of \(p\)_Share_ scheme, which consists of the following five steps:  
1. **Setup. ** In this procedure, the system needs to be initialized. First, the map is partitioned into zones, and the anchor point of each zone needs to be set up as described in III.D; the travel time between any two anchor points is precomputed. Then the CS generates the key pair \((pk,sk)\) and broadcasts \(pk\) to other parties in the system. 2. **Ride Request Submit. ** When a rider needs the ride-sharing service, he will first compute the estimated travel time \(t_{s\to AP(s)}\) and \(t_{d\to AP(d)}\) using the public road network and navigation system in his mobile device, where \(s\) and \(d\) are the locations of his start point and destination point. Then he encrypts them with \(pk\) and obtains \([\! [t_{s\to AP(s)}]\! ]\) and \([\! [t_{d\to AP(d)}]\! ]\), respectively, in which \([\! ]\) represents the ciphertext form. After that, the rider selects the deadline of pick-up time \(t_{s}\) and the deadline of drop-off time \(t_{d}\) and encrypts them. Finally, the rider submits the ride-sharing request \(R=\left(z(s),z(d),[\! [t_{s\to AP(s)}]\!],[\! [t_{d\to AP(d)}]\!],[\![t_{s}]\!],[\! [t_{ d}]\!]\right)\). 3. **Driver Location Update. ** Similarly, the driver needs to submit his current status to finish the matching process. First, he computes \([\! [t_{l\to AP(l)}]\! ]\) with his end device and \(pk\), then submits his status \(D=\left(CAP_{d},OBR_{d},z(l),[\! [t_{l\to AP(l)}]\! ]\right)\), where \(l\) is the driver's current location and \(v\) is the current vehicle load. If \(OBR_{d}>0\), namely that the driver has existing riders, the schedule of driver \(\mathcal{S}_{d}=\left(\{R_{i}\}_{i=1}^{OBR_{d}},\mathcal{P}\right)\) should also be submitted to the RS, which include onboard riders' encrypted requests and the existing path. The definition of path is described in the following paper. 4. **Riders Filtering. ** To mitigate the computation overhead, the RS needs to filter the riders on their coarse locations of start point and destination point (i.e., the corresponding zones) as Algorithm 1. On receiving from a driver's status \(D\), the RS first checks if there are any existing riders. If \(OBR_{d}=0\), the RS searches the surrounding riders of \(z(l)\) within a fixed-size region \(SR\) and outputs the set \(\mathcal{R}_{nearby}\). For each rider \(r\) of \(\mathcal{R}_{nearby}\), the RS obtains the shortest route between \(AP(r_{i}z(s))\) and \(AP(r_{i}z(d))\) from precomputed data. Then the RS gets \(r_{i}.Zpath=\{r_{i}.z(s),\cdots,r_{i}.z(d)\}\), which represents the zones sequence the route passes through. The RS selects \(M\) riders \(\{\!\{r_{i}\}_{i=1}^{M}\!\}\) with the longest length of \(Zpath\) from \(\mathcal{R}_{nearby}\) as the root riders, meanwhile \(M\) corresponding rider sets \(\{\mathcal{R}_{i}\}_{i=1}^{M}\) are constructed. In addition, the RS computes the expanded path for each root rider of \(\{\!\{r_{i}\}_{i=1}^{M}\!\}\). As Figure 2 indicates, \(r.Zpath\) indicates the black area, and \(r.EZpath\) is computed as the grey area and the black area in order to include more potential riders. For the rest of the riders, the RS compares their paths and the directions with the root riders as follows, and riders with similar traveling routes will be added to the corresponding set.