# Hail the Closest Driver on Roads: Privacy-Preserving Ride Matching in Online Ride Hailing Services

Authors: Haining Yu; Hongli Zhang; Xiangzhan Yu
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Online ride hailing (ORH) services enable a rider to request a driver to take him wherever he wants through a smartphone app on short notice. To use ORH services, users have to submit their ride information to the ORH service provider to make ride matching, such as pick-up/drop-off location. However, the submission of ride information may lead to the leakages of users’ privacy. In this paper, we focus on the issue of protecting the location information of both riders and drivers during ride matching and propose a privacy-preserving online ride matching scheme, called pRMatch. It enables an ORH service provider to find the closest available driver for an incoming rider over a city-scale road network, while protecting the location privacy of both riders and drivers against the ORH service provider and other unauthorized participants. In pRMatch, we compute the shortest road distance over encrypted data by using road network embedding and partially homomorphic encryption and further efficiently compare encrypted distances by using ciphertext packing and shuffling. The theoretical analysis and experimental results demonstrate that pRMatch is accurate and efficient, yet preserving users’ location privacy.


---

## Body

## 1. Introduction

The widespread adoption of smartphones embedded with GPS, combined with the availability of digital road maps, provides the necessary enabling technologies for online ride hailing (ORH) services, such as Uber (http://www.uber.com), Lyft (http://www.lyft.com), and DiDi Chuxing (http://www.didiglobal.com). As reported in [1], 30% urban American adults had used ORH services, which have already far out-paced the growth of traditional carsharing services of the past. The general feature of ORH services is the ability for a rider to request a driver to take him exactly where he needs to go, via his ORH app. Upon receiving a rider’s request, the ORH service provider makes ride matching between the rider and available drivers and forwards the request to the closest driver.Unfortunately, along with the high convenience of ORH services come some important privacy concerns [2, 3]. To provide better services, ORH services require users to submit ride information to make ride matching, such as riders’ pick-up and drop-off locations. This private information is usually sensitive and can be used to identify an individual or infer his/her daily activity. For example, if a driver Bob accepts a ride request: picking up a rider Alice at a particular location l at time t, it reveals that both Bob and Alice will be at location l at time t. Actually, an ORH service provider is not always fully trusted, it might collect users’ ride information to profile them or infer additional sensitive information from harvested data for purpose of economic benefit. Furthermore, even if an ORH service provider is honest, it may be attacked by other adversaries. Nowadays, risks of data leakage happen more frequently than ever before. The leakages of users’ ride information may pose threats on users’ financial or personal safety. Therefore, it is a major technical challenge to enable ORH services while protecting users’ privacy.Many privacy-enhanced solutions for ORH services are proposed to protect users’ privacy during ride matching. These solutions are based on either nonencryption or encryption. Nonencryption solutions usually employ spatial cloaking [4], geographic masking [5], mix-zone [6], and differential privacy [7] to trade-off between the level of privacy preserving and the quality of ORH service. These solutions are of high-efficiency, but provide limited privacy preservation and suffer from distortion of location information. To improve quality of services, encryption solutions are proposed, which provide strong privacy preservation at the cost of heavy computation and communication cost. These encryption-based solutions integrate well-established cryptographic tools, such as private information retrieval (PIR) [8], secure multiparty computation (SMC) [9], private set intersection (PSI) [10], somewhat homomorphic encryption (SHE) [11], and partially homomorphic encryption (PHE) [12] to accomplish private distance measurements for ride matching. For efficiency, most existing encryption-based solutions use Euclidean distance as the travel cost metric, such as PrivateRide [4], ORide [13], and TRACE [14]. However, Euclidean distance may lead to false hits, because drivers always travel along road network. As evaluated in our experiments, roughly 15% false hits exist when using Euclidean distance to make ride matching. Actually, road distance should be used to evaluate the travel cost between riders and drivers, which can achieve a higher accuracy. As studied in [15, 16], it is a complex problem to compute the shortest road distance under city-scale road networks in the encrypted form. Existing secure shortest road distance approaches are not efficient enough to support online ride matching, which requires heavy cost on shortest road distance computation in real time. It is desired that there exists an encryption-based scheme to efficiently make ride matching for ORH services by using road distance.In this paper, we focus on the issue of the leakage of user’s location privacy during ride matching and propose a privacy-preserving online ride matching scheme, called pRMatch. It enables an ORH service provider to find the closest available driver for an incoming rider over a city-scale road network, while protecting the location privacy of both riders and drivers against the ORH service provider and other unauthorized participants. We summarize the following main contributions:(i)
We propose a privacy-preserving ride matching scheme for ORH services (pRMatch), which enables an ORH service provider to select the closest driver for an incoming rider by using approximate road distance, while preventing users’ location privacy from disclosing to the ORH service provider and other curious participants.(ii)
We propose an efficient shortest road distance computation approach, which computes the shortest road distance over encrypted data by using road network embedding and partially homomorphic encryption.(iii)
We design a secure comparison protocol, which efficiently compares encrypted distances by using ciphertext packing and shuffling.(iv)
We implement pRMatch and perform extensive experiments to validate its accuracy and efficiency. Experimental results demonstrate that pRMatch is secure without hampering the functionality of ORH services.The remainder of this paper is structured as follows: in Section2, we describe the system model and give the problem definition; in Section 3, we list necessary preliminaries; in Section 4, we describe pRMatch scheme in details; in Section 5, we discuss theoretical analysis of pRMatch; in Section 6, we present the evaluation; in Section 7, we review the related literature. Finally, we summarize this paper.


## 2. Models and Problem Definition

### 2.1. System Model

Over a city-scale road network, pRMatch provides strong privacy guarantees to both drivers and riders during ride matching, without sacrificing the usability of the ORH services. As shown in Figure1, pRMatch involves four participants:(i)
SP. The ORH service provider (SP) handles incoming ride hailing requests and matches riders with available drivers, based primarily on their encrypted locations.(ii)
Proxy. The proxy is a third party that offers efficient key management. With the proxy, heavy cryptographic operations can be relieved from users.(iii)
Rider. A rider u is the user who submits his encrypted pick-up location lu to the SP to request a nearby available driver.(iv)
Driver. A driver d is the user who updates his encrypted current location ld to the SP and waits for a new rider to serve.Figure 1
The system model of pRMatch.Here, we assume a ride/driver has a smartphone embedded with GPS to obtain own location at anytime and anywhere, and he also installs and registers to an ORH App offered by the SP.In our system model, we consider single-rider multidriver ride matching, which prefers instant feedback to the users without batch processing requests at a fixed time interval. The batch processing may achieve better system optimization but sacrifice the user experience, e.g., a rider may wait for a while to retrieve the matching result. This single-rider multidriver ride matching is widely practised in user-centered services, such as [4, 13, 14, 17], which do not try to violate user experience to improve the overall system optimization.


### 2.2. Threat Model

The threat model of pRMatch is assumed as follows:(i)
The SP and the proxy arehonest-but-curious, which try to learn additional information from received message and intermediate information during the scheme execution.(ii)
Users (including riders and drivers) are alsohonest-but-curious. That is, riders submit valid request and drivers update correct locations, but they try to harvest other unmatched users’ location information.(iii)
There isno collude among the participants, including the SP and the proxy, the SP and users, the proxy and users. In practice, the SP and the proxy are usually a large service provider (e.g., Uber and Google) which understand the importance of reputation. Active attacks like collusion are easy to detect and will seriously damage their reputation once caught.(iv)
Drivers are independent contractors rather than the SP’s employees; thus, the SP has no authority to access to the location information they hold.(v)
No external adversary can truncate or tamper the communications among the participants.pRMatch focuses on the following representative attacks inspired from [2, 13]:(i)
A1 (SP/Proxy ⟶ D/R, Daily Routines Tracking Attack). The SP or the proxy might attempt to precisely track riders or drivers during their daily routines online or offline.(ii)
A2 (SP/Proxy ⟶ D/R, Large-Scale Inference Attack). The SP or the proxy might attempt to collect rides’ or drivers’ rides deliberately and perform a large-scale inference attack to learn additional users’ privacy, e.g., their home/work addresses, behaviors, and interests.(iii)
A3 (D/R ⟶ R/D, Unauthorized Ride Harvesting Attack). A driver/rider might attempt to harvest additional unauthorized ride information of other unmatched users.


### 2.3. Problem Definition

The problem that we focus on is defined as follows: given a set of driversD that travel along the road network and an incoming rider u, to find the driver with minimum road distance to serve the rider, while preserving the location privacy of both the rider and the drivers. The problem is represented as(1)d∗=argmindk∈DdistRlu,ldk,where lu is the pick-up location, ldk is the current location of driver dk, and distR⋅,⋅ represents the shortest road distance between two locations.Our design goals contain the following three-fold:(i)
Accuracy. pRMatch should provide accurate ride matching results. That is, the matched driver is the closest one to serve the given request with a high probability.(ii)
Efficiency. pRMatch should be efficient to support large-scale ORH services. That is, the computation and communication cost should be low enough to make ride matching over large-scale users.(iii)
Privacy Preservation. In pRMatch, the location privacy of both riders and drivers should be secret to the SP, the proxy, and other users beyond authorization.


## 2.1. System Model

Over a city-scale road network, pRMatch provides strong privacy guarantees to both drivers and riders during ride matching, without sacrificing the usability of the ORH services. As shown in Figure1, pRMatch involves four participants:(i)
SP. The ORH service provider (SP) handles incoming ride hailing requests and matches riders with available drivers, based primarily on their encrypted locations.(ii)
Proxy. The proxy is a third party that offers efficient key management. With the proxy, heavy cryptographic operations can be relieved from users.(iii)
Rider. A rider u is the user who submits his encrypted pick-up location lu to the SP to request a nearby available driver.(iv)
Driver. A driver d is the user who updates his encrypted current location ld to the SP and waits for a new rider to serve.Figure 1
The system model of pRMatch.Here, we assume a ride/driver has a smartphone embedded with GPS to obtain own location at anytime and anywhere, and he also installs and registers to an ORH App offered by the SP.In our system model, we consider single-rider multidriver ride matching, which prefers instant feedback to the users without batch processing requests at a fixed time interval. The batch processing may achieve better system optimization but sacrifice the user experience, e.g., a rider may wait for a while to retrieve the matching result. This single-rider multidriver ride matching is widely practised in user-centered services, such as [4, 13, 14, 17], which do not try to violate user experience to improve the overall system optimization.


## 2.2. Threat Model

The threat model of pRMatch is assumed as follows:(i)
The SP and the proxy arehonest-but-curious, which try to learn additional information from received message and intermediate information during the scheme execution.(ii)
Users (including riders and drivers) are alsohonest-but-curious. That is, riders submit valid request and drivers update correct locations, but they try to harvest other unmatched users’ location information.(iii)
There isno collude among the participants, including the SP and the proxy, the SP and users, the proxy and users. In practice, the SP and the proxy are usually a large service provider (e.g., Uber and Google) which understand the importance of reputation. Active attacks like collusion are easy to detect and will seriously damage their reputation once caught.(iv)
Drivers are independent contractors rather than the SP’s employees; thus, the SP has no authority to access to the location information they hold.(v)
No external adversary can truncate or tamper the communications among the participants.pRMatch focuses on the following representative attacks inspired from [2, 13]:(i)
A1 (SP/Proxy ⟶ D/R, Daily Routines Tracking Attack). The SP or the proxy might attempt to precisely track riders or drivers during their daily routines online or offline.(ii)
A2 (SP/Proxy ⟶ D/R, Large-Scale Inference Attack). The SP or the proxy might attempt to collect rides’ or drivers’ rides deliberately and perform a large-scale inference attack to learn additional users’ privacy, e.g., their home/work addresses, behaviors, and interests.(iii)
A3 (D/R ⟶ R/D, Unauthorized Ride Harvesting Attack). A driver/rider might attempt to harvest additional unauthorized ride information of other unmatched users.


## 2.3. Problem Definition

The problem that we focus on is defined as follows: given a set of driversD that travel along the road network and an incoming rider u, to find the driver with minimum road distance to serve the rider, while preserving the location privacy of both the rider and the drivers. The problem is represented as(1)d∗=argmindk∈DdistRlu,ldk,where lu is the pick-up location, ldk is the current location of driver dk, and distR⋅,⋅ represents the shortest road distance between two locations.Our design goals contain the following three-fold:(i)
Accuracy. pRMatch should provide accurate ride matching results. That is, the matched driver is the closest one to serve the given request with a high probability.(ii)
Efficiency. pRMatch should be efficient to support large-scale ORH services. That is, the computation and communication cost should be low enough to make ride matching over large-scale users.(iii)
Privacy Preservation. In pRMatch, the location privacy of both riders and drivers should be secret to the SP, the proxy, and other users beyond authorization.


## 3. Preliminaries

### 3.1. Paillier Cryptosystem

The Paillier cryptosystem [12] is a widely used PHE that supports additive homomorphic encryption. We brief it to help illustrate and understand our scheme as follows:(i)
Key Generation (pk,sk←KeyGen1λ). Choose two primes p, q and compute N=p×q and λ=l cmp−1,q−1. Then, select a random g∈ℤN2∗ such that gcdLgλmodN2,N=1, where Lx=x−1/N. The public key and private key are pk=N,g and sk=λ, respectively.(ii)
Encryption (c←Em,pk). Let m∈ℤN be a plaintext and r∈ℤN be a random number. The ciphertext is given by c=EmmodN;rmodN=gmrNmodN2.(iii)
Decryption (m←Dc,sk). Given a ciphertext c∈ℤN2, the corresponding plaintext can be derived as(2)m=LcλmodN2LgλmodN2modN.The Paillier cryptosystem has homomorphism properties: for anym1,m2,r1,r2∈ℤN, we have(3)Em1,r1⋅Em2,r2=Em1+m2,r1r2modN2,Em2m1,r1=Em1m2,r1m2modN2.


### 3.2. Road Network Embedding

The road network embedding (RNE) technique [18] is used to convert the road network into a high-dimensional space, where complex shortest road distance computation can be converted to simple computation supported by existing cryptographic primitives.A road network can be modeled as a weighted graphG=V,E,W. Let V be the number of vertices in G (i.e., road intersections) and E be the number of edges in G (i.e., road segments). Define R as a set of Olog2V subsets of V, i.e.,(4)R=V1,1,…,V1,α,…,Vβ,1,…,Vα,β,where α=β=OlogV and Vi,j is a subset composed of 2i random vertices of V. Given a vertex v and a subset Vi,j, the shortest road distance between them is defined as(5)distRv,Vi,j=minv′∈Vi,jdistRv,v′,where R defines a high-dimensional embedding space, where the coordinate of a vertex v∈V is a Olog2V-dimensional vector:(6)cv=distRv,V1,1,…,distRv,V1,α,…,distRv,Vβ,1,…,distRv,Vα,β.The embedded road network ofG is represented as Ω=cvv∈V.For a locationl on the road segment vs,vd∈E, its coordinate can be represented as(7)cl=distRl,V1,1,…,distRl,V1,α,…,distRl,Vβ,1,…,distRl,Vα,β,where distRl,Vi,j=mindistRl,vs+distRvs,Vi,j,distRl,vd+distRvd,Vi,j.Without loss of generality, we assume the dimension of the embedded network isω, s.t., ω≤⌈log2V⌉. Given two locations ls and ld, the shortest distance between them can be approximated through computing the chessboard distance between cls and cld, denoted by(8)distRls,ld≈distCcls,cld=maxVi,j∈RdistRls,Vi,j−distRld,Vi,j=max1≤i≤ωclsi−cldi,where distC⋅,⋅ represents the chessboard distance between two coordinates.


## 3.1. Paillier Cryptosystem

The Paillier cryptosystem [12] is a widely used PHE that supports additive homomorphic encryption. We brief it to help illustrate and understand our scheme as follows:(i)
Key Generation (pk,sk←KeyGen1λ). Choose two primes p, q and compute N=p×q and λ=l cmp−1,q−1. Then, select a random g∈ℤN2∗ such that gcdLgλmodN2,N=1, where Lx=x−1/N. The public key and private key are pk=N,g and sk=λ, respectively.(ii)
Encryption (c←Em,pk). Let m∈ℤN be a plaintext and r∈ℤN be a random number. The ciphertext is given by c=EmmodN;rmodN=gmrNmodN2.(iii)
Decryption (m←Dc,sk). Given a ciphertext c∈ℤN2, the corresponding plaintext can be derived as(2)m=LcλmodN2LgλmodN2modN.The Paillier cryptosystem has homomorphism properties: for anym1,m2,r1,r2∈ℤN, we have(3)Em1,r1⋅Em2,r2=Em1+m2,r1r2modN2,Em2m1,r1=Em1m2,r1m2modN2.


## 3.2. Road Network Embedding

The road network embedding (RNE) technique [18] is used to convert the road network into a high-dimensional space, where complex shortest road distance computation can be converted to simple computation supported by existing cryptographic primitives.A road network can be modeled as a weighted graphG=V,E,W. Let V be the number of vertices in G (i.e., road intersections) and E be the number of edges in G (i.e., road segments). Define R as a set of Olog2V subsets of V, i.e.,(4)R=V1,1,…,V1,α,…,Vβ,1,…,Vα,β,where α=β=OlogV and Vi,j is a subset composed of 2i random vertices of V. Given a vertex v and a subset Vi,j, the shortest road distance between them is defined as(5)distRv,Vi,j=minv′∈Vi,jdistRv,v′,where R defines a high-dimensional embedding space, where the coordinate of a vertex v∈V is a Olog2V-dimensional vector:(6)cv=distRv,V1,1,…,distRv,V1,α,…,distRv,Vβ,1,…,distRv,Vα,β.The embedded road network ofG is represented as Ω=cvv∈V.For a locationl on the road segment vs,vd∈E, its coordinate can be represented as(7)cl=distRl,V1,1,…,distRl,V1,α,…,distRl,Vβ,1,…,distRl,Vα,β,where distRl,Vi,j=mindistRl,vs+distRvs,Vi,j,distRl,vd+distRvd,Vi,j.Without loss of generality, we assume the dimension of the embedded network isω, s.t., ω≤⌈log2V⌉. Given two locations ls and ld, the shortest distance between them can be approximated through computing the chessboard distance between cls and cld, denoted by(8)distRls,ld≈distCcls,cld=maxVi,j∈RdistRls,Vi,j−distRld,Vi,j=max1≤i≤ωclsi−cldi,where distC⋅,⋅ represents the chessboard distance between two coordinates.


## 4. pRMatch Scheme

In this section, we present our pRMatch scheme. We begin with an overview of the scheme and then detail its operations.


### 4.1. Overview

As shown in Figure1, the proxy generates keys and broadcasts the public key to other participants. Drivers periodically report to the SP the geographical zones where they are located. These zones are defined by the SP to prefilter drivers quickly. When a rider wants to hail a driver, he generates the encrypted request and sends it to the SP. Then, the SP prefilters all drivers on the basis of zone information and obtains candidate drivers. All candidate drivers send their encrypted locations to the SP. Upon received above ciphertexts, the SP computes all shortest road distances from the candidate drivers to the rider in encrypted form. The SP and the proxy perform secure comparison protocol to select the driver with the minimum road distance to serve the rider. Finally, the ride matching result is sent to the matched rider and driver.


### 4.2. Ride Prerequisites

Given the road networkG=V,E,W and the dimension ω of the embedded road network, several offline initialization works need to be executed:(i)
The proxy generates a pair of keyspk,sk. The public key pk is open to other participants, and the secret key sk is kept by itself.(ii)
The SP computes the coordinate of each vertex inG to generate the embedded road network Ω=cvv∈V by using RNE technique introduced in Section 3.2, where each coordinate is represented as a ω-dimensional vector. To support drivers prefiltering, the SP partitions the road network G into the set of zones G=zi1≤i≤n. Note that Ω and G are public to all users.(iii)
A driverdk periodically reports to the SP the geographical zone zdk where he is located.


### 4.3. Ride Matching

When a rider hails a driver using the ORH service, the operations performed by the rider, the drivers, the SP, and the proxy are as follows (Figure2):(1)
The rideru first computes the coordinate of his pick-up location lu in the embedded road network Ω according to equation (7), denoted as cu=cu1,…,cuω, and the zone where he is located, denoted as zu. Then, the rider encrypts each element in cu with the public key pk using Paillier cryptosystem, denoted as(9)〚cu〛=Ecu1,…,Ecuω.Finally, the rideru sends his request Ru=〚cu〛,zu to the SP.(2)
Upon receiving the requestRu, the SP selects the candidate drivers D∗ that is located in the zone zu and the adjacent zones of zu. Then, the SP asks the candidate drivers to update their encrypted current locations.(3)
Fordk∈D∗, the driver dk computes the coordinate of his current location ldk in the embedded road network Ω according to equation (7), denoted as cdk=cdk1,⋯,cdkω. Then, the driver encrypts each element in cdk with the public key pk using Paillier cryptosystem, denoted as(10)〚cdk〛=Ecdk1,…,Ecdkω.Finally, the driverdk sends his encrypted current location 〚cdk〛 to the SP.(4)
Upon receiving〚cdk〛dk∈D∗, the SP computes the shortest road distances from all candidate drivers D∗ to the rider u in ciphertext domain. Assume the upper bound of road distance in the road network is a ℓ-bit integer. Given dk∈D∗, the SP computes the shortest road distance between ldk and lu according to equation (8). Concretely, the SP computes the following vector 〚distdk,u〛 over ciphertexts 〚cdk〛 and 〚cu〛 based on homomorphism properties of the Paillier cryptosystem:(11)〚distdk,u〛=Ecdk1−cu1+2ℓ,…,Ecdkω−cuω+2ℓ=Ecdk1E−1cdk1E2ℓ,…,EcdkωE−1cdkωE2ℓ.Note thatE2ℓ is used to ensure all elements in 〚distdk,u〛 are positive. To prevent the proxy from inferring the locations of u and dk, the SP shuffles these encrypted values in 〚distdk,u〛. For every element in the new vector, no one knows its position in the original vector. Consequently, the release of the index of the minimum in a shuffled vector is meaningless and does not reveal any private information. With the random permutation function π, the original vector 〚distdk,u〛 is permuted into the shuffled vector:(12)〚dist˜dk,u〛=〚dist˜1dk,u〛,…,〚dist˜ωdk,u〛=Ecdkπ1E−1cdkπ1E2ℓ,…,EcdkπωE−1cdkπωE2ℓ.It is worth noting that this permutation prevents the proxy from knowing the original position of any element in〚distdk,u〛. To improve the efficiency, the SP uses ciphertext packing technique to pack multiple ciphertexts into one single ciphertext, because the plaintext space of the Paillier cryptosystem is much greater than that of the upper bound of road distance. In the Paillier cryptosystem, the number of slots in a packed ciphertext is p=N/ℓ+1, that is, we can pack p ciphertexts into one single packed ciphertext. The basic idea of ciphertext packing is introduced as follows. Suppose a1,⋯,al are ℓ-bit integers 1≤l≤p, their corresponding ciphertexts are 〚a1〛,⋯,〚al〛. We construct the packed ciphertext by(13)〚a1〛⋯〚al〛=∏i=1l〚ai〛2ℓl−i.We only need one decryption to obtain the packed plaintext(14)a1⋯al=∑i=0lai2ll−i,and then recovera1,⋯,al. Based on above ciphertexts packing, the SP packs all encrypted elements of 〚distdk,u〛 into one single packed ciphertext:(15)〚dist˜dk,u〛=〚dist˜1dk,u〛⋯〚dist˜ωdk,u〛=∏i=1ω〚dist˜idk,u〛2ℓω−i,s.t.,p≥ω. To protect the real identifiers of drivers against the proxy, the SP generates an one-time pseudonym for each driver dk∈D∗, denoted as d˜k=π′dk, and we have(16)D∗˜=d˜k=π′dkdk∈D∗.Finally, the SP sends a set of packed ciphertexts〚dist˜d˜k,u〛d˜k∈D∗˜ to the proxy.(5)
Upon receiving these packed ciphertexts, the proxy decrypts each ciphertext in〚dist˜d˜k,u〛d˜k∈D∗˜ with its secret key sk and then unpacks them to obtain(17)dist˜d˜k,ud˜k∈D∗˜=dist˜1d˜k,u,…,dist˜ωd˜k,ud˜k∈D∗˜.Then, the proxy runs Algorithm1 to obtain the shortest road distances between the candidate drivers D∗˜ and the rider u and then selects the driver with the minimum road distance as the matched driver, denoted as d∗˜. Finally, the proxy sends d∗˜ to the SP.(6)
When receivingd∗˜, the SP can learn the real identifier of d∗˜ is d∗. Then, the match result is sent to the driver d∗ and the rider u.Figure 2
The framework of pRMatch.


## 4.1. Overview

As shown in Figure1, the proxy generates keys and broadcasts the public key to other participants. Drivers periodically report to the SP the geographical zones where they are located. These zones are defined by the SP to prefilter drivers quickly. When a rider wants to hail a driver, he generates the encrypted request and sends it to the SP. Then, the SP prefilters all drivers on the basis of zone information and obtains candidate drivers. All candidate drivers send their encrypted locations to the SP. Upon received above ciphertexts, the SP computes all shortest road distances from the candidate drivers to the rider in encrypted form. The SP and the proxy perform secure comparison protocol to select the driver with the minimum road distance to serve the rider. Finally, the ride matching result is sent to the matched rider and driver.


## 4.2. Ride Prerequisites

Given the road networkG=V,E,W and the dimension ω of the embedded road network, several offline initialization works need to be executed:(i)
The proxy generates a pair of keyspk,sk. The public key pk is open to other participants, and the secret key sk is kept by itself.(ii)
The SP computes the coordinate of each vertex inG to generate the embedded road network Ω=cvv∈V by using RNE technique introduced in Section 3.2, where each coordinate is represented as a ω-dimensional vector. To support drivers prefiltering, the SP partitions the road network G into the set of zones G=zi1≤i≤n. Note that Ω and G are public to all users.(iii)
A driverdk periodically reports to the SP the geographical zone zdk where he is located.


## 4.3. Ride Matching

When a rider hails a driver using the ORH service, the operations performed by the rider, the drivers, the SP, and the proxy are as follows (Figure2):(1)
The rideru first computes the coordinate of his pick-up location lu in the embedded road network Ω according to equation (7), denoted as cu=cu1,…,cuω, and the zone where he is located, denoted as zu. Then, the rider encrypts each element in cu with the public key pk using Paillier cryptosystem, denoted as(9)〚cu〛=Ecu1,…,Ecuω.Finally, the rideru sends his request Ru=〚cu〛,zu to the SP.(2)
Upon receiving the requestRu, the SP selects the candidate drivers D∗ that is located in the zone zu and the adjacent zones of zu. Then, the SP asks the candidate drivers to update their encrypted current locations.(3)
Fordk∈D∗, the driver dk computes the coordinate of his current location ldk in the embedded road network Ω according to equation (7), denoted as cdk=cdk1,⋯,cdkω. Then, the driver encrypts each element in cdk with the public key pk using Paillier cryptosystem, denoted as(10)〚cdk〛=Ecdk1,…,Ecdkω.Finally, the driverdk sends his encrypted current location 〚cdk〛 to the SP.(4)
Upon receiving〚cdk〛dk∈D∗, the SP computes the shortest road distances from all candidate drivers D∗ to the rider u in ciphertext domain. Assume the upper bound of road distance in the road network is a ℓ-bit integer. Given dk∈D∗, the SP computes the shortest road distance between ldk and lu according to equation (8). Concretely, the SP computes the following vector 〚distdk,u〛 over ciphertexts 〚cdk〛 and 〚cu〛 based on homomorphism properties of the Paillier cryptosystem:(11)〚distdk,u〛=Ecdk1−cu1+2ℓ,…,Ecdkω−cuω+2ℓ=Ecdk1E−1cdk1E2ℓ,…,EcdkωE−1cdkωE2ℓ.Note thatE2ℓ is used to ensure all elements in 〚distdk,u〛 are positive. To prevent the proxy from inferring the locations of u and dk, the SP shuffles these encrypted values in 〚distdk,u〛. For every element in the new vector, no one knows its position in the original vector. Consequently, the release of the index of the minimum in a shuffled vector is meaningless and does not reveal any private information. With the random permutation function π, the original vector 〚distdk,u〛 is permuted into the shuffled vector:(12)〚dist˜dk,u〛=〚dist˜1dk,u〛,…,〚dist˜ωdk,u〛=Ecdkπ1E−1cdkπ1E2ℓ,…,EcdkπωE−1cdkπωE2ℓ.It is worth noting that this permutation prevents the proxy from knowing the original position of any element in〚distdk,u〛. To improve the efficiency, the SP uses ciphertext packing technique to pack multiple ciphertexts into one single ciphertext, because the plaintext space of the Paillier cryptosystem is much greater than that of the upper bound of road distance. In the Paillier cryptosystem, the number of slots in a packed ciphertext is p=N/ℓ+1, that is, we can pack p ciphertexts into one single packed ciphertext. The basic idea of ciphertext packing is introduced as follows. Suppose a1,⋯,al are ℓ-bit integers 1≤l≤p, their corresponding ciphertexts are 〚a1〛,⋯,〚al〛. We construct the packed ciphertext by(13)〚a1〛⋯〚al〛=∏i=1l〚ai〛2ℓl−i.We only need one decryption to obtain the packed plaintext(14)a1⋯al=∑i=0lai2ll−i,and then recovera1,⋯,al. Based on above ciphertexts packing, the SP packs all encrypted elements of 〚distdk,u〛 into one single packed ciphertext:(15)〚dist˜dk,u〛=〚dist˜1dk,u〛⋯〚dist˜ωdk,u〛=∏i=1ω〚dist˜idk,u〛2ℓω−i,s.t.,p≥ω. To protect the real identifiers of drivers against the proxy, the SP generates an one-time pseudonym for each driver dk∈D∗, denoted as d˜k=π′dk, and we have(16)D∗˜=d˜k=π′dkdk∈D∗.Finally, the SP sends a set of packed ciphertexts〚dist˜d˜k,u〛d˜k∈D∗˜ to the proxy.(5)
Upon receiving these packed ciphertexts, the proxy decrypts each ciphertext in〚dist˜d˜k,u〛d˜k∈D∗˜ with its secret key sk and then unpacks them to obtain(17)dist˜d˜k,ud˜k∈D∗˜=dist˜1d˜k,u,…,dist˜ωd˜k,ud˜k∈D∗˜.Then, the proxy runs Algorithm1 to obtain the shortest road distances between the candidate drivers D∗˜ and the rider u and then selects the driver with the minimum road distance as the matched driver, denoted as d∗˜. Finally, the proxy sends d∗˜ to the SP.(6)
When receivingd∗˜, the SP can learn the real identifier of d∗˜ is d∗. Then, the match result is sent to the driver d∗ and the rider u.Figure 2
The framework of pRMatch.


## 5. Theoretical Analysis

### 5.1. Complexity Analysis

We analyze the online computation (comp.) cost and communication (comm.) cost for different participants in pRMatch. For the Paillier cryptosystem, we setN and g to 1024 bits and 160 bits, respectively. Under this assumption, one encryption (Enc) needs two 1024-bit exponentiations and one 2048-bit multiplication, and one decryption (Dec) costs essentially one 2048-bit multiplication, and a ciphertext is 2048 bits. Let mul and exp denote one 2048-bit multiplication and one 2048-bit exponentiation, respectively.Algorithm 1: Best driver selection (BDS).
Input: dist˜d˜k,ud˜k∈D∗˜=dist˜1d˜k,u,·,dist˜ωd˜k,ud˜k∈D∗˜.Output: d∗˜.(1)
for1≤k≤D∗˜ do(2)
for1≤i≤ω do(3)
ifdist˜id˜k,u<2ℓ then(4)
dist˜id˜k,u←2ℓ−dist˜id˜k,u;(5)
else(6)
dist˜id˜k,u←dist˜id˜k,u−2ℓ;(7)
end if(8)
ifi=1 or dist<dist˜id˜k,u do(9)
dist←dist˜id˜k,u;(10)
end if(11)
end for(12)
ifk=1 or dist∗>dist do(13)
dist∗←dist;(14)
d∗˜←dk;(15)
end if(16)
end for(17)
returnd∗˜;At the user side, a rider (resp. driver) needs to performωEnc to obtain the encrypted request (resp. current location). Accordingly, ω ciphertexts need to be transferred to the SP. Thus, the comm. cost between the SP and a user is roughly 2048ω bits.At the SP side, the SP performs2ωmul and ωexp to compute one shortest road distance. The total cost of the shortest road distance computation is 2ωD∗mul and ωD∗exp. Besides, the SP packs ωD∗ ciphertexts into ⌈ωD∗/p⌉ packed ciphertexts, where p=⌊1024/ℓ+1⌋. The comp. cost of above packing is ωD∗mul and ωD∗exp. The SP sends ⌈ωD∗/p⌉ packed ciphertexts to the proxy, thus the comm. cost between the SP and the proxy is roughly ⌈2048ωD∗/p⌉ bits.At the proxy side, the proxy primarily performs⌈ωD∗/p⌉Dec to decrypt receiving ciphertexts. Afterwards, it returns one plaintext to the SP.


### 5.2. Security Analysis

The SP cannot harvest any rider’s pick-up locationcu from 〚cu〛, and any driver’s current location cdk from 〚cdk〛, because they are encrypted by the Paillier cryptosystem that has semantic security. The SP only learns the zone information of users and the match result, rather than the exact locations of users.The proxy also cannot learn any rider’s pick-up locationcu and any driver’s current location cdk from dist˜d˜k,ud˜k∈D∗˜, because each location coordinate in the road network embedded space has been shuffled and the real identifiers of drivers have been replaced by pseudonyms. Given dist˜d˜k,u, the proxy infers distd˜k,u with the probability 1/ω!.Next, we present an attack analysis to demonstrate that pRMatch effectively addresses the attacks described in Section2.2.(i)
Against A1. To launch a daily routines tracking attack to a user, the SP/proxy needs to know his exact pick-up/drop-off location and time. In pRMatch, the drop-off event is not reported to the SP/proxy. As aforementioned, the SP cannot learn any rider’s pick-up location or any driver’s current location from the received ciphertext. Moreover, the SP only knows the rough pick-up time and the zone information, which is not enough to track the user. The proxy knows nothing about a ride, because each location coordinate have been shuffled. Above analysis indicates that pRMatch can tackle daily routines tracking attacks.(ii)
Against A2. To launch a large-scale inference attack to a user, the SP/proxy needs to learn his identity and at least his pick-up location and time. We have analyzed that the pick-up location of a rider and the current location of a driver are never exposed to the SP or the proxy. The proxy does not even know the user’s identity, because it is replaced by pseudonyms. Note that the zone size should be well-defined, because unreasonable zone size cannot protect users’ location privacy against known background knowledge attack. For instance, if there is only one semantic location in a zone, then the SP will learn riders in the zone are likely to be picked up at this semantic location. From the above analysis, it is clear that it is difficult for the SP and the proxy to profile riders’ and drivers’ activities.(iii)
Against A3. A driver can learn a rider’s ride information if and only if he is matched to the rider; otherwise, the driver harvests nothing. Likewise, a rider only receives the information of his matched driver. Obviously, unauthorized ride harvesting attacks are hard to be launched.


## 5.1. Complexity Analysis

We analyze the online computation (comp.) cost and communication (comm.) cost for different participants in pRMatch. For the Paillier cryptosystem, we setN and g to 1024 bits and 160 bits, respectively. Under this assumption, one encryption (Enc) needs two 1024-bit exponentiations and one 2048-bit multiplication, and one decryption (Dec) costs essentially one 2048-bit multiplication, and a ciphertext is 2048 bits. Let mul and exp denote one 2048-bit multiplication and one 2048-bit exponentiation, respectively.Algorithm 1: Best driver selection (BDS).
Input: dist˜d˜k,ud˜k∈D∗˜=dist˜1d˜k,u,·,dist˜ωd˜k,ud˜k∈D∗˜.Output: d∗˜.(1)
for1≤k≤D∗˜ do(2)
for1≤i≤ω do(3)
ifdist˜id˜k,u<2ℓ then(4)
dist˜id˜k,u←2ℓ−dist˜id˜k,u;(5)
else(6)
dist˜id˜k,u←dist˜id˜k,u−2ℓ;(7)
end if(8)
ifi=1 or dist<dist˜id˜k,u do(9)
dist←dist˜id˜k,u;(10)
end if(11)
end for(12)
ifk=1 or dist∗>dist do(13)
dist∗←dist;(14)
d∗˜←dk;(15)
end if(16)
end for(17)
returnd∗˜;At the user side, a rider (resp. driver) needs to performωEnc to obtain the encrypted request (resp. current location). Accordingly, ω ciphertexts need to be transferred to the SP. Thus, the comm. cost between the SP and a user is roughly 2048ω bits.At the SP side, the SP performs2ωmul and ωexp to compute one shortest road distance. The total cost of the shortest road distance computation is 2ωD∗mul and ωD∗exp. Besides, the SP packs ωD∗ ciphertexts into ⌈ωD∗/p⌉ packed ciphertexts, where p=⌊1024/ℓ+1⌋. The comp. cost of above packing is ωD∗mul and ωD∗exp. The SP sends ⌈ωD∗/p⌉ packed ciphertexts to the proxy, thus the comm. cost between the SP and the proxy is roughly ⌈2048ωD∗/p⌉ bits.At the proxy side, the proxy primarily performs⌈ωD∗/p⌉Dec to decrypt receiving ciphertexts. Afterwards, it returns one plaintext to the SP.


## 5.2. Security Analysis

The SP cannot harvest any rider’s pick-up locationcu from 〚cu〛, and any driver’s current location cdk from 〚cdk〛, because they are encrypted by the Paillier cryptosystem that has semantic security. The SP only learns the zone information of users and the match result, rather than the exact locations of users.The proxy also cannot learn any rider’s pick-up locationcu and any driver’s current location cdk from dist˜d˜k,ud˜k∈D∗˜, because each location coordinate in the road network embedded space has been shuffled and the real identifiers of drivers have been replaced by pseudonyms. Given dist˜d˜k,u, the proxy infers distd˜k,u with the probability 1/ω!.Next, we present an attack analysis to demonstrate that pRMatch effectively addresses the attacks described in Section2.2.(i)
Against A1. To launch a daily routines tracking attack to a user, the SP/proxy needs to know his exact pick-up/drop-off location and time. In pRMatch, the drop-off event is not reported to the SP/proxy. As aforementioned, the SP cannot learn any rider’s pick-up location or any driver’s current location from the received ciphertext. Moreover, the SP only knows the rough pick-up time and the zone information, which is not enough to track the user. The proxy knows nothing about a ride, because each location coordinate have been shuffled. Above analysis indicates that pRMatch can tackle daily routines tracking attacks.(ii)
Against A2. To launch a large-scale inference attack to a user, the SP/proxy needs to learn his identity and at least his pick-up location and time. We have analyzed that the pick-up location of a rider and the current location of a driver are never exposed to the SP or the proxy. The proxy does not even know the user’s identity, because it is replaced by pseudonyms. Note that the zone size should be well-defined, because unreasonable zone size cannot protect users’ location privacy against known background knowledge attack. For instance, if there is only one semantic location in a zone, then the SP will learn riders in the zone are likely to be picked up at this semantic location. From the above analysis, it is clear that it is difficult for the SP and the proxy to profile riders’ and drivers’ activities.(iii)
Against A3. A driver can learn a rider’s ride information if and only if he is matched to the rider; otherwise, the driver harvests nothing. Likewise, a rider only receives the information of his matched driver. Obviously, unauthorized ride harvesting attacks are hard to be launched.


## 6. Experimental Evaluation

Our experiments are performed on the real road network of California (http://www.cs.utah.edu/lifeifei/SpatialDataset.htm) (Figure 3(a)), which contains 21048 vertices and 21693 edges. We generate riders and drivers on the edges in a random fashion (Figure 3(b)) and set the bit length of the upper bound of road distance to 16, i.e., ℓ=16. We implement a proof-of-concept pRMatch in C++, by relying on the Paillier cryptosystem library (http://acsc.cs.utexas.edu/libpaillier). All our experiments are conducted and executed on a PC running Ubuntu 18.04 LTS, with an Intel i7 processor at 3.4 GHz and 16 GB RAM.Figure 3
Dataset for experiments. (a) The road network of California (b) The user generation over the road network.
(a)(b)pRMatch is compared with the state-of-the-art privacy-preserving schemes ORide [13] and pRide [17] under the same road network. ORide utilizes the Euclidean distance metric for ride matching, and pRide is the first privacy-preserving ride matching scheme using road distance metric. We build ORide on FV scheme [11] inspired from NFLlib (github.com/quarkslab/NFLlib) and FV-NFLlib (github.com/CryptoExperts/FV-NFLlib) and implement pRide on the same Paillier cryptosystem library and Obliv-C [19]. For pRide, the length of a wire in Yao’s garbled circuits [9] is set to 80 bits, and the security parameter for blindness is set to 32 bits to achieve statistical security roughly 2−15.We evaluate the accuracy and the efficiency of pRMatch by varying the dimension of the embedded road network or driver scale, where the dimensionω is the element number of a coordinate in the embedded road network, as defined in equation (8), and driver scale D is the total number of available drivers on road.Accuracy: we use the matching success rate (MSR) to evaluate the accuracy. A matching is successful if the matched driver is the actual driver with the minimum road distance. We defineMSR=Nsuc/Nall, where Nall is the total number of matchings and Nsuc is the number of success matchings.Figure4(a) depicts the MSRs of pRMatch, pRide, and ORide by varying the dimension ω from 4 to 32. We can see the MSRs of pRMatch and pRide raise steadily as the dimension of the embedded road network increases, which is more than 95% if the dimension is higher than 24. That is because higher dimension means higher accuracy of shortest road distance computation. In contrast, Euclidean distance computation in ORide is irrelevant to the dimension, thus the MSR of ORide always stays around 85%. When the dimension is higher than 8, pRMatch and pRide outperform ORide in the terms of accuracy. This is of no surprise because both pRMatch and pRide choose road distance to make ride matching, which is more accurate than Euclidean distance. Figure 4(b) depicts the MSRs of pRMatch, pRide, and ORide by varying the driver scale from 1000 to 4000. As shown in Figure 4(b), the MSRs of pRMatch and pRide are always high under any driver scale. This demonstrates the accuracy of pRMatch is not affected by big-scale drivers. The MSR of ORide gradually rises as the driver scale increases, because larger driver scale indicates there may exist closer drivers located around riders. However, the MSR of ORide is still less than 90%. Above experimental results demonstrate that pRMatch can reach a higher accuracy due to the choice of road distance.Efficiency: we use average online comp. cost and comm. cost for per ride matching to evaluate the efficiency.Figures5(a)–5(d) depict the comp. cost of pRMatch and pRide for per-matching varying the dimension of the embedded road network or driver scale. At the user (including riders and drivers) side, a user needs to encrypt its location coordinate in the embedded road network. As shown in Figure 5(a), the comp. cost of the rider (and the driver) in pRMatch raises with the dimension increases. The reason is that higher dimension requires more encryption operations over a location coordinate. Figure 5(b) shows the comp. cost of the rider (and the driver) stays steady under any driver scale. In addition, pRMatch costs more execution time at the user side, because it cannot pack encrypted coordinate into one single ciphertext. Nevertheless, pRMatch is still practical at the user side for resource-constrained devices. For instance, a user requires roughly 0.1 second to encrypt a 24-dimensional location coordinate. As shown in Figure 5(c) and 5(d), the comp. cost at the server (including the SP and the proxy) side in pRMatch and pRide increases almost linearly as the dimension or the driver scale increases. It is obvious that the comp. cost at the server side in pRMatch is much lower than that in pRide. For instance, pRMatch requires about 1 second for per-matching when the dimension is 24 and the driver scale is 2000, but pRide requires more than 6 seconds. Moreover, we can see that the SP undertakes most comp. cost at the server side, and the proxy always has low comp. cost with big-scale drivers (less than 0.15 second).Figure 4
The accuracy of pRMatch, ORide, and pRide, when the number of zones is 25. (a) The MSR under a different dimension of the embedded road network, whenD=2000. (b) The MSR under a different driver scale, when ω=24.
(a)(b)Figure 5
The efficiency of pRMatch and pRide, when the number of zones is 25. (a) The comp. cost of a user (including the rider and candicate drivers) under different dimension of the embedded road network, whenD=2000. (b) The comp. cost of a user (including the rider and candicate drivers) under a different driver scale, when ω=24. (c) The comp. cost of the servers under a different dimension of the embedded road network, when D=2000. (d) The comp. cost of the servers under a different driver scale, when ω=24. (e) The comm. cost between the SP and a user (including the rider and candicate drivers) under a different dimension of the embedded road network, when D=2000. (f) The comm. cost between the SP and a user (including the rider and candicate drivers) under a different driver scale, when ω=24. (g) The comm. cost between the servers under a different dimension of the embedded road network, when D=2000. (h) The comm. cost of between servers under a different driver scale, when ω=24.
(a)(b)(c)(d)(e)(f)(g)(h)Figures5(e)–5(h) depict the comm. cost of pRMatch and pRide for per-matching by varying the dimension of the embedded network or driver scale. As shown in Figures 5(e) and 5(f), pRMatch requires more comm. cost between the SP and the rider (and the driver) as the dimension increases, while the comm. cost is not affected by the driver scale. We can also see that the comm. cost between the SP and the rider (and the driver) in pRMatch is higher than that in pRide, but it is quite acceptable for resource-constrained devices. As shown in Figures 5(g) and 5(h), pRide requires very heavy comm. cost between the two servers, and it needs even more as the dimension or the driver scale increases. In contrast, the comm. cost between the SP and the proxy in pRMatch slowly grows with the increase of the dimension or driver scale, and it always stays low, about two orders of magnitude less than that in pRide. For instance, pRMatch requires less than 27 kBs comm. cost at the server side when the dimension is 24 and the driver scale is 2000, but pRide requires roughly 24 MBs.Compared with ORide, pRMatch reaches higher accuracy. Compared with pRide, pRMatch achieves higher efficiency at the server side; especially, it brings an order-of-magnitude improvement in comm. cost. pRMatch requires more cost at the user side than pRide, but the cost is quite acceptable for resource-constrained devices.


## 7. Related Work

The rapid adoption of ORH services poses significant challenges for users’ privacy disclosure, as there are a few studies that have emphasized the importance of privacy-preserving solutions in ORH services [2]. PrivateRide [4] is the first system to enhance location privacy for riders in ORH services. It uses spatial cloaking regions to replace their actual locations. But obfuscate locations, instead of the actual locations, affect the accuracy of ride matching; the matched driver may not be the optimal one and has to drive extra distance to pick up the rider; meanwhile, the rider may wait extra time to get the ride. Moreover, PrivateRide only provides limited privacy guarantees for drivers and offers less accountability features. Later, ORide [13] is proposed to address these limitations, which provides stronger privacy and accountability guarantees for both riders and drivers based SHE and anonymous credentials. In addition, ORide applies optimizations for ciphertext packing and transformed processing, hence enabling a notable boost in performance and a reduction in overhead. TRACE [14] supports privacy-preserving spatial query based on random masking technique and point-in-polygon strategy. CoRide [20] is a blockchain-assisted system model for several SPs to establish private collaborative-rides. To achieve efficiency, these schemes utilize the Euclidean distance metric for ride matching, because it is easy to compute over encrypted data. But Euclidean distance may lead to false hits, because drivers always travel along road network. As evaluated in our experiments, it roughly 15% false hits exist when using Euclidean distance to make ride matching. pRide [17] uses PHE and Yao’s garbled circuits to compute road distance for ride matching, but its comp. cost and comm. cost at server side are very heavy. lpRide [21] adopts modified PHE and ciphertext blinding to compute the shortest road distance for ride matching without two noncollusion servers assumption. For both accuracy and efficiency, our pRMatch uses road distance as the travel cost metric to make ride matching over encrypted data without any heavy cost.Also relevant are the works in privacy-enhanced ridesharing services. PrivatePool [22] is a privacy-preserving protocol allowing users to check their feasible ride matches through PSI and SHE. PRIS [23] is a privacy-preserving ride matching scheme for selecting feasible ridesharing partners based on PHE and bilinear pairing. SRide [24] is a privacy-preserving ridesharing matching protocol based on users’ spatial and temporal information, which employs SHE and SMC to compute feasible matches. Most of the previous studies have one limit that hampers their reuse in ORH service. That is, they require drivers offering ridesharing to riders along the route they had already planned to travel. It is impractical for ORH services, where riders can hail a driver to go wherever they want. To tackle this, PSRide [25] is proposed to make privacy-preserving ridesharing matching for ORH systems.There is a vast literature on protecting location privacy against service providers in LBSs; we summarize them into four fundamentally different ways:Location-Based k-Anonymity. It requires that the service provider cannot distinguish the request issuer from k−1 other users such that the probability of identifying him is 1/k. To achieve this, one way is to enlarge the issuer’s location to a cloaking region including k−1 other users by using a hierarchical spatial partitioning [26, 27] or space-filling curves [28]. Another way is to generate k−1 dummies (fake locations) together with the actual request to perform k requests to the service provider [29, 30]. Moreover, location l-diversity [31, 32] is also introduced to enhance k-anonymity. The main drawback of k-anonymity-based solutions is the difficulty of providing provable privacy which guarantees to be independent of background knowledge.Location Obfuscation. It requires blurring or perturbing the location information contained in requests. As reviewed in [33], obfuscation techniques can be divided into three groups. Request enlargement techniques [34, 35] create obfuscation areas for requests to hide users’ locations. Dummy-based techniques [36, 37] generate nonsensitive locations as the dummies without considering other potential users (unlike k-anonymity). Coordinate transformation techniques [38, 39] change the complete coordinate reference system using geometric transformations to confuse adversaries. Generally, obfuscation cannot provide provable privacy guarantees without background knowledge, and may impact the quality of service (QoS) of LBSs. Thus, background knowledge is necessary for location obfuscation, e.g., PPCS [40] generates dummy locations based on entropy while considering semantic location information that might be used by attackers.Differential Privacy. Differential privacy [41] is proposed in statistical databases, which is independent of background knowledge. It can also be used for location privacy in LBSs, such as (D,ϵ)-location privacy [42] and ϵ-geo-indistinguishability [43]. The intuitive idea behind differential privacy is the following: the ratio between the probabilities of obtaining a certain output from two locations relies on their distance, that is, the privacy level increases with their distance. To achieve this, a fake location is probabilistically determined to replace the actual location in requests by running randomization functions. Differential privacy has to make a trade-off between privacy and QoS. Several studies focus on optimal trade-offs [44, 45], but it still has no clear answer.Encryption-Based Solution. Many encryption-based solutions have been discussed above. Besides, cryptographic primitives have been explored in other LBSs, such as location-based kNN search [46, 47] and friend-finder services [48]. Encryption-based solutions strive for stronger, provable privacy guarantees. The essential challenge is to allow for efficient responding to the requests, despite the computational complexity of the cryptographic primitives.


## 8. Conclusion and Future Work

In this paper, we focus on the issue of the preservation of location privacy of both riders and drivers during ride matching in ORH services and proposed a privacy-preserving ride matching scheme, namely, pRMatch. It enables an ORH service provider to find the closest available driver for an incoming rider over a city-scale road network, without leaking users’ location privacy to the ORH service provider and other unauthorized users. In pRMatch, we proposed an efficient shortest road distance computation approach over encrypted data by using road network embedding and PHE and further designed a secure comparison protocol over encrypted data by using ciphertexts packing and shuffling. We also implement pRMatch and perform extensive experiments to validate its accuracy and efficiency. Experimental results demonstrate that pRMatch achieves about 95% accuracy and guarantees efficiency.For future work, we will consider the safety issues during ride execution in privacy-enhanced ORH services. When the urgent safety threat happens, e.g., hijacks, a privacy-preserving scheme cannot break the safety protection.



---

*Source: 4948387-2020-06-12.xml*