# Privacy-Preserving Ride-Sharing System with Minimum-Detouring Route
## 4 Proposed Approach
### Protocol Details
Based on the non-negligible advantage to distinguish the ciphertext requests encrypted by Paillier cryptosystem, we break the semantic security of Paillier cryptosystem. It is contradictory to the assumption of the theorem. This completes the proof. **Theorem 2**: _If Paillier cryptosystem is semantically secure, pShare has user privacy in the DLU algorithm._

Similar to the proof of Theorem 1, we can prove Theorem 2 that there is no PPT adversary who has a non-negligible advantage to distinguish two outputs of _DLU_ algorithm with drivers from the same zone. **Theorem 3**: _If the garbled circuit \(C_{pp}\) is secure under the semi-honest adversary model, then the PPA algorithm is secure under the semi-honest model._

During the PPA algorithm, we simulate the view of the RS and the CS, respectively. Let \(S_{CS}\) simulate the view of the CS. The RS first blinds the ciphertexts by adding them with a set of randomly generated integers. Then the CS receives the blinded ciphertexts and decrypts them. Since the random integers are big enough, the CS cannot distinguish between two blinded values. That is to say, if \(S_{CS}\) randomly picks an integer from the range \(\left(2^{k-1}+1,2^{k}+2^{l+1}-2\right)\), encrypts it, and sends it to the CS, there is no PPT adversary who can distinguish the blinded plaintext from random integer with non-negligible probability. Then \(C_{pp}\) outputs the path-planning results, which is an \(m\)-bits integer that indicates which path to choose. We use \(S_{RS}\) to simulate the RS's view. For each combination, \(S_{RS}\) randomly chooses a path that meets Equations (11) and (12) and sends the number of the path as the result of _PPA_ algorithm to the RS. There is no PPT adversary who can distinguish the best path, which is a sequence of encrypted location information, from the randomly chosen one. The process of circuit execution is also secure. The security proof of \(C_{pp}\) can be found in [20]. We complete the proof of the theorem. **Theorem 4**: _If the garbled circuit SCOMP is secure under the semi-honest adversary model, then the RCS algorithm is secure under the semi-honest model._

Similar to the proof of Theorem 3, from the view of the CS, the adversary \(\mathcal{A}\) cannot distinguish the blinded plaintext from the random integer. Then \(S_{RS}\) randomly selects a number from all eligible combinations as the result of combination selection. The randomly selected number is also indistinguishable from the real result. **Theorem 5**: _pShare is adaptively semantically secure against semi-honest adversaries._

We first describe a PPT simulator \(\mathcal{S}\) to simulate the whole process of _pShare_ such that any PPT adversary \(\mathcal{A}\) cannot distinguish the results of Real\({}_{\mathcal{AC}}\left(1^{\lambda}\right)\) and \(Ideal_{\mathcal{AS}}\left(1^{\lambda}\right)\) with non-negligible advantages. Given \(\mathcal{L}_{access}=AP_{access}\left(\mathcal{M},d,\mathcal{R}\right)\), \(\mathcal{S}\) randomly generates a set of drivers \(\hat{\mathcal{D}}\), and for each \(\hat{d}\in\hat{\mathcal{D}}\), \(\mathcal{S}\) randomly generates a set of riders around the driver. Then \(\mathcal{S}\) simulates riders to run \(RRS\) algorithm and drivers to run _DLU_ algorithm with \(\mathcal{A}\) acting as the RS, and then running _RFA_, _PPA_, and _RCS_ algorithms. According to Theorems 1 and 2, \(\mathcal{A}\) cannot distinguish \(\hat{d}\in\hat{\mathcal{D}}\) from \(d\in\mathcal{D}\) and \(\hat{r}\in\hat{\mathcal{R}}\) from \(r\in\mathcal{R}\) during \(RRS\) and _DLU_ algorithm execution. Since there is no data transmission in _RFA_, \(\mathcal{A}\) cannot obtain any useful information. According to Theorems 3 and 4, \(\mathcal{A}\) still cannot distinguish \(\hat{d}\in\hat{\mathcal{D}}\) from \(d\in\mathcal{D}\) and \(\hat{r}\in\hat{\mathcal{R}}\) from \(r\in\mathcal{R}\) in _PPA_ and _RCS_ algorithms. In summary, _pShare_ is adaptively \(\mathcal{L}_{access}\)-semantic secure against semi-honest adversaries. We complete the proof.