# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details
: _Let \(p\)Share = (\(RRS\), \(DLU\), \(RFA\), \(PPA\), RCS) be our privacy-preserving ride-sharing scheme, representing the process of Ride Request Submit, Driver Location Update, Request Filtering Algorithm, Path-Planning Algorithm, and Rider Combination Selection, respectively. We consider the following experiments with probabilistic polynomial time (PPT) adversary \(\mathcal{A}\), a challenger \(\mathcal{C}\), a simulator \(\mathcal{S}\), and the leakage function \(\mathcal{L}_{access}\)._

\(\mathrm{Real}_{\mathcal{A},\mathcal{C}}\big{(}1^{\lambda}\big{)}\): Firstly, \(\mathcal{C}\) runs the initialization to set the system parameters. Then \(\mathcal{A}\) outputs a set of ride requests \(\mathcal{R}\). For each r\({}_{i}\in\mathcal{R}\), \(\mathcal{C}\) and \(\mathcal{A}\) execute a simulation of \(RRS\), with \(\mathcal{C}\) acting as the rider and \(\mathcal{A}\) acting as the RS. Then \(\mathcal{A}\) generates a polynomial number of adaptively chosen drivers \(\mathcal{D}\). For each driver \(d_{j}\in\mathcal{D}\), \(\mathcal{C}\) and \(\mathcal{A}\) execute a simulation of \(DLU\), in which \(\mathcal{C}\) and \(\mathcal{A}\) play the role of the driver and the RS, respectively. Afterward, \(\mathcal{A}\) acts the \(RS\) and runs \(RFA\), \(PPA\), and \(RCS\), and finally outputs \(\gamma\) as the result of the experiments. \(\mathit{Ideal}_{\mathcal{A},\mathcal{S}}\big{(}1^{\lambda}\big{)}\): Firstly, \(\mathcal{S}\) generates system parameters in the process initialization. Then \(\mathcal{A}\) outputs a set of riders \(\mathcal{R}\) for each r\({}_{i}\in\mathcal{R}\), and \(\mathcal{A}\) executes a simulation of \(RRS\), with \(\mathcal{S}\) acting as the rider and \(\mathcal{A}\) acting as the RS. Then \(\mathcal{A}\) generates a polynomial number of adaptively chosen drivers \(\mathcal{D}\). For each driver \(d_{j}\), \(\mathcal{S}\) is given the leakage function \(\mathcal{L}_{access}=AP_{access}(\mathcal{M},d,\mathcal{R})\) and executes a simulation of \(DLU\) with \(\mathcal{A}\), in which \(\mathcal{C}\) and \(\mathcal{A}\) plays the role of the driver and the RS, respectively. Afterward, \(\mathcal{A}\) acts the RS and runs \(RFA\), \(PPA\), and \(RCS\), and outputs \(\gamma^{\prime}\) as the result of the experiment. We define the advantage of \(\mathcal{A}\) and in the experiment as \(Adv(\lambda)=|Pr(\gamma=\gamma^{\prime})-1/2|\). Then we say \(p\)_Share_ is adaptively \(L_{access}\)-semantic secure if for all PPT adversaries \(\mathcal{A}\), there exists a PPT simulator s.t. \(Adv(\lambda)\) is negligible. According to the above definitions, we analyze the user privacy of \(p\)_Share_ as follows:

**Theorem 1**. : _If Paillier cryptosystem is semantically secure, \(p\)Share has rider privacy in \(RRS\) algorithm._

Proof. : Supposing \(p\)_Share_ cannot satisfy user privacy in \(RRS\) and there is a PPT adversary who has a non-negligible advantage to distinguish the outputs of the \(\mathrm{Real}_{\mathcal{A},\mathcal{C}}\big{(}1^{\lambda}\big{)}\) from the outputs of the \(\mathit{Ideal}_{\mathcal{A},\mathcal{S}}\big{(}1^{\lambda}\big{)}\). We use \(\mathcal{A}\) to break user privacy in \(RRS\) algorithm. First, we generate the public key \(pk\) and randomly generate two plaintext ride-sharing requests

\[Dir\big{(}r_{j},\mathcal{R}_{i}\big{)} =\check{r}_{i}.EZpath.indexof\big{(}r_{j}.z(s)\big{)}- \tag{10}\]5

and

\[Dir\big{(}r_{j},\mathcal{R}_{i}\big{)} =\check{r}_{i}.EZpath.indexof\big{(}r_{j}.z(s)\big{)}- \tag{10}\]6

in which \(z(s_{1})=z(s_{2})\), \(z(d_{1})=z(d_{2})\). Then we send the requests to the challenger, and the challenger randomly chooses \(b\in\{0,1\}\) and returns

\[Dir\big{(}r_{j},\mathcal{R}_{i}\big{)} =\check{r}_{i}.EZpath.indexof\big{(}r_{j}.z(s)\big{)}- \tag{10}\]7

with the RRS algorithm. We send \(R_{b}\) to the adversary \(\mathcal{A}\), who gives his guess \(b^{\prime}\). So the advantage for \(\mathcal{A}\) to distinguish two requests is \(Adv(\lambda)=|Pr(b=b^{\prime})-1/2|\), which is also non-negligible.