# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details
Besides, some non-encrypted techniques include location perturbation [26], dummy location generation [27], and spatial cloaking [28]. Based on these methods, a few privacy-preserving ride-matching schemes have been proposed. A privacy-enhanced scheme, PrivateRide [6], was proposed by [PERSON] et al., which provides anonymity for users' locations. Later, they extended it to ORide [7], which is based on somewhat homomorphic encryption and enables the matching more efficiently while protecting users' privacy. Besides, [PERSON] et al. proposed a privacy-preserving ride-matching scheme based on road networks [8], which can perform matching more accurately. Considering side-channel attacks, they also presented a private and efficient scheme with Intel SGX enclave, which provides a hardware-enforced Trusted Execution Environment [29]. However, all these schemes are ride-matching schemes, which do not support ride-sharing matching. ### Privacy-Preserving Ride-Sharing

There are also some relevant schemes for ride-sharing. SRide is a privacy-preserving dynamic ride-sharing system, which computes the ride-sharing results based on users' spatiotemporal data. PRIS [13] utilizes PHE [15] to find eligible matching between riders and drivers. [PERSON] et al. proposed a scheme [30] that computes the similarity of riders' trips on ciphertexts to match riders. The FICA scheme [31] ensures data privacy and reliability using edge computation and blockchain techniques. PrivatePool [14] constructs a

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Size of (\(\mathcal{R}_{nearby}\))**} & \multicolumn{4}{c}{_pShare_ Scheme**} \\ \cline{2-7}  & \multicolumn{2}{c}{**Rider**} & \multicolumn{2}{c}{**Driver**} & \multicolumn{2}{c}{**Server**} \\ \cline{2-7}  & **Comm. (KBs)** & **Comp. (ms)** & **Comm. (KBs)** & **Comp. (ms)** & **Comm. (MBs)** & **Comp. (s)** \\ \hline
25 & 0.51 & 26 & 0.13 + 0.52 * \({}



distributed and privacy-enhanced ride-sharing system with PSI [32] protocol and SHE [33] technique. PSRide [19] utilizes PHE [15] and the Garbled Circuit technique to build a privacy-preserving scheme that supports flexible ride-sharing matching. [PERSON] et al. proposed PGRide [21], in which they designed an encrypted aggregate distance computation approach by using SHE and ciphertexts packing technique. Through the approach, the aggregate distances can be computed in encrypted form. However, none of these schemes can support group matching and meanwhile find minimum detouring matching results over road traveling time. ## 8 Conclusions

In this paper, we propose a privacy-preserving ride-sharing scheme _pShare_ for ORH service. _pShare_ supports privacy-preserving ride-sharing between multiple riders, the matching results of which have a minimum ATT. To achieve this, the riders and drivers need to submit their encrypted location information to the ORH server, and the ORH server applies secure computing and compares matching protocols with the crypto server based on the garbled circuit and the data packing technique. They first compute the minimum path for each eligible richer combination, and finally, they compare and select the best combination with minimum ATT. We prove that _pShare_ scheme achieves user privacy and is adaptively semantically secure under the random oracle model. The experimental results have shown that _pShare_ achieves both accuracy and practical efficiency. Conceptualization, [PERSON]; methodology, [PERSON]; software, [PERSON]; validation, Y.L., B.H. and J.L. ; formal analysis, [PERSON]; writing--original draft preparation, [PERSON]; writing--review and editing, J.H. and Y.L. ; visualization, [PERSON]; supervision, M.X. All authors have read and agreed to the published version of the manuscript. This work was supported by the National Nature Science Foundation of China (No.62072466, 61872372, 62102429, 62102422) and the NUDT Research Grant (No. ZK19-38). Not applicable. The data provided in the article is public data. The authors declare no conflict of interest.