# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details
## 6 Evaluation

We compare _pShare_ with schemes [7; 8; 14; 19; 21] under the same threat model and summarize the differences between them in the \[Dir\big{(}r_{j},\mathcal{R}_{i}\big{)} =\check{r}_{i}.EZpath.indexof\big{(}r_{j}.z(s)\big{)}- \tag{10}\]8 Compared to the other privacy-preserving ORH schemes, _pShare_ is able to match the driver with a group of riders andcomputes for the least-detouring path while protecting users' privacy. In this section, we design an experiment to show the utility and efficiency of _pShare_. We present the experimental setup in Section 6.1 and experiment results in Section 6.2. ### Experimental Setup

In this section, we evaluate our experiments on the road network of an about \(50\,\times\,50\) km map of Beijing, which is generated by OpenStreetMap [22]. Since the distribution of riders and drivers is always dynamic, we generate the ride-sharing requests and driver locations using the tool TaxiQueryGenerator [23], whose outputs conform to Beijing's real spatio-temporal distribution. We implement Paillier cryptosystem by an open-source library, jpaillier [24], and Yao's garbled circuits by Faster-GC [25]. During the experiment, we set the modulus of the Paillier cryptosystem to 1024 bits, the bit-length of a blinded value \(k\) to 32 bits, the bit-length of a domain value \(l\) to 16 bits, and the bit-length of a wire label to 80 bits. All our experiments are run on a PC with 8 GB memory and an Intel-8265U CPU of 1.8 GHz. We divide the selected area of the map into grids and set up all the parameters of the _pShare_ ride-sharing system. Then we randomly initialize the locations of the drivers and the riders in the selected area, meanwhile generating the corresponding pick-up time and drop-off time of the riders and the available time of the drivers. Then the pick-up deadline and drop-off deadline are computed as \(t_{s}=t_{cur}+600\) s, \(t_{d}=t_{s}+t_{s\to d}+600\) s.

The default patience time of a rider is 30 min, i.e., the rider will turn to other options for traveling rather than ride-sharing beyond this amount of time. We choose the generated requesting datasets of period 10:00-11:00 and the drivers' datasets of period 10:30-11:00 as the experimental datasets. We first read all rider requesting data, and for each record of driver datasets, we read it sequentially and apply the ride-sharing matching between the driver and riders within the patience time. The result of the ride-sharing matching may be a failure or success. To evaluate the accuracy of _pShare_, we record the matched riders if matching successfully and compare the results to another experiment _pShare-GT_, which takes ground truth to replace the estimated traveling time. Besides, we also measure the overhead of the experiments and record it in the table. ### Experiment Results

**Accuracy:** In the experiments, we use two metrics to evaluate the accuracy of the system, which are Successful Matching Rate (SMR) and Accurate Matching Rate (AMR), respectively. We compute SMR as \(SMR=N_{suc}/N_{tot}\), in which \(N_{suc}\) indicates the number of successful matching and \(N_{tot}\) indicates the total number of matching. We compute AMR as \(AMR=N_{acc}/N_{tot}\); \(N_{acc}\) indicates the number of matches where the results of _pShare_ are the same as the results of _pShare-GT_. We use the metric AMR to evaluate the accuracy of the scheme to find the minimum detouring route. Since there is a trade-off between the matching accuracy and the user privacy, we introduce the Average Number of POI (\(ANP\)) in one zone to represent the privacy level of current zone size, in which POI is point of