# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Description** & _pShare_ & _ORide_[7] & _pRide_[8] & _PSRide_[19] & _PriatePool_ [14] & _PGRide_[21] \\ \hline \begin{tabular}{c} Ride- \\ sharing \\ \end{tabular} & Yes & No & No & Yes & Yes & Yes \\ \hline \begin{tabular}{c} Traveling \\ cost \\ \end{tabular} & \begin{tabular}{c} Road \\ traveling \\ time \\ \end{tabular} & \begin{tabular}{c} Euclidean \\ distance \\ \end{tabular} & \begin{tabular}{c} Road \\ traveling \\ time \\ \end{tabular} & \begin{tabular}{c} Road \\ traveling \\ time \\ \end{tabular} & \begin{tabular}{c} Road \\ traveling \\ distance \\ \end{tabular} & \begin{tabular}{c} Euclidean \\ distance \\ \end{tabular} \\ \hline \
\begin{tabular}{c} Group \\ matching \\ \end{tabular} & Yes & No & No & No & No & Yes \\ \hline
\begin{tabular}{c} Minimum \\ ATT \\ \end{tabular} & Yes & \(\backslash\) & \(\backslash\) & Yes & Yes & No \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison with existing schemes. interest, corresponding to the location points of the riders' probable destinations. Therefore, the users' precise locations are disclosed in the probability of \(1/ANP\). We compute and compare the variants of SMR, AMR, and ANP by varying the zone scale and the number of riders to be searched \(\mathcal{R}_{nearby}\). As shown in Figure 7, SMR has little association with the zone size, but AMR increases remarkably with zone getting smaller, which indicates the accuracy of the zone-based time estimation method is highly relevant to the zone scale. Besides, there is a drastic reduction in APN with smaller zone size, so it is necessary to properly set the zone scale considering protecting users' privacy at an acceptable level. Furthermore, the rider number to be searched has an influence on SMR but has no evident impact on AMR/SMR. **Efficiency:** We take communication and computation cost to evaluate the efficiency of _pShare_ scheme. During the ride-sharing, the computation cost mainly includes the encryption of riders and drivers in the process of Request Submit and Location Submit, the packing/unpacking operations and the garbled circuit execution in the process of ride-sharing matching. As shown in Table 2, for the rider, the communication cost is always 0.51 KB, and the computation cost is 26 ms. For a driver with no onboard rider, the communication cost is 0.13 KB. For a driver with onboard riders, the submitted information should also contain the requests of riders onboard. As for the server (includes both the ride-sharing server and the crypto server), the communication cost and the computation cost are subject to the size of searched riders. The communication cost of the server is mainly from the packed ciphertexts the RS sends to the CS, and the computation cost mainly contains the cost of ciphertexts packing and computation of the RS, the ciphertexts unpacking of the CS, and the execution time of the garbled circuit. From the table, we can see that the total execution time of the server is about 30 s if the number of riders to be searched is 100. The responding time is acceptable for users with an appropriate searching scale. Moreover, we especially evaluate the computation cost of the garbled circuit with different searched riders and the number of available seats. From Figure 8, we can find the execution time of the garbled circuit takes up most of the total computation cost, and the cost rises faster as the size of \(\mathcal{R}_{nearby}\) and \(v\) become bigger. Figure 7: SMR, AMR, and ANP under different zone scales when the number of searched riders is 100 (**left**) and SMR, AMR, and AMR/SMR under different sizes of \(\mathcal{R}_{nearby}\) when the zone scale is \(50\times 50\) (**right**). ## 7 Related Work

### Privacy-Preserving Ride-Matching

Many approaches have been proposed to preserve users' privacy in location-based services. For the cryptographic primitives, there is homomorphic encryption, secure multi-party computation, and private set intersection.