Private Location Sharing for Decentralized Routing services

Motivated by this observation, in this paper we propose a decentralized location sharing protocol where users on the road will periodically compute and announce the traffic counts (e.g., approximate number of vehicles traveling on each road) of the transportation network in a decentralized and privacy-preserving manner. Since only the total number of vehicles on each road is announced, the location of individual users is not discernible by observers, which is contrary to many current location sharing setups where users give their individual location data directly to routing services. With this protocol, user privacy does not rely on a trusted data custodian, and there are no single points of failure.

Furthermore, assuming the roads in the network are sufficiently large, we can prove that the travel time estimates produced by the protocol will be close to the estimates produced by the ground truth with high probability. This result showcases an interesting complementarity between differential privacy and delay functions used in travel time estimation. In low traffic situations, differential privacy constraints lead to poor accuracy for traffic count estimation. However, delay functions are insensitive for small inputs and can thus tolerate the poor accuracy. On the other hand, delay functions are very sensitive in high traffic situations, and differential privacy can provide high accuracy in these settings. Thus when a delay function is composed with a differentially private mechanism, the two compensate for the others’ weaknesses to yield accurate and private travel time estimates. We corroborate this insight using numerical experiments which show that the protocol provides a privacy-preserving routing service with minimal overhead to the travel time of users.

Privacy research in transportation mainly focuses on location privacy, whereby the aim is to prevent untrusted entities from learning geographic locations or location sequences of an individual [1]. A number of privacy-preserving approaches have been proposed for various location-based applications, e.g., trajectory publishing, mobile crowdsensing, traffic control, etc. From a methodological perspective, these approaches are often implemented through spatial cloaking [2], differential privacy[3], and Secure Multi-Party Computation (MPC) [4].

Spatial cloaking-based approaches rely on aggregation to convert users’ exact locations to coarse information. These approaches are often based on k-anonymity [5], where a mobility dataset is divided into equivalence classes based on data attributes (e.g., geological regions, time, etc.) so that each class contains at least k records [6, 7]. These k-anonymity-based approaches can guarantee that every record in the dataset is indistinguishable from at least k-1 other records. However, k-anonymity is generally considered to be a weak privacy guarantee. Furthermore, due to coarse data aggregation, spatial cloaking-based approaches can lead to low data accuracy.

Differential privacy-based approaches provide a sound privacy guarantee by producing randomized responses to queries, whereby two datasets that differ in only one entry produce statistically indistinguishable responses [8]. In other words, differential privacy ensures that an adversary with arbitrary background information (e.g., query responses, other entries) cannot infer individual entries with high confidence. Existing research for location data either probabilistically generates obfuscated locations from a user’s true location [9, 10] or adds noises to the number of users within each equivalent class [11, 12, 13, 14, 15]. However, differential privacy-based approaches can suffer from two drawbacks. First, due to randomization, there is a trade-off between the accuracy of the response and the level of privacy. Second, most existing research requires a trusted data collector to generate random responses, which does not fit our decentralized setting in this paper.

Secure MPC serves as an excellent technique for decentralized settings, whereby several players jointly compute a function over their data while keeping these data private. Existing secure MPC-based research proposes traffic monitoring and control approaches that keep users’ location data confidential, based on secret sharing [16, 17], homomorphic encryption [18, 19], and blockchain [20]. Secure MPC can ensure accuracy since no noises are added to protect location privacy. However, Secure MPC can suffer from high computational overhead due to encryption, and the computation results might leak private information (See Remark 4 for more details).

This paper is organized as follows. In Section 2 we present a model for the transportation system, and specify both the system objective and privacy requirements. We present a decentralized and privacy-preserving routing service protocol in Section 3 along with all of the statistical and cryptographic tools used by the protocol. In Section 4 we prove that if the roads in the transportation network are sufficiently large, then the protocol provides a privacy-preserving routing service whose travel time estimates are provably close to the ground truth. We evaluate our protocol in numerical experiments and present the results in Section 5. We summarize our work and identify important areas for future work in Section 6.

The transportation network is represented as a directed graph $G:=(V,E)$ where edges $E$ represent roads and vertices $V$ represent road intersections. We use $n:=\left|V\right|$ and $m:=\left|E\right|$ to denote the number of vertices and edges in the graph respectively. The concepts of traffic flow, traffic counts, and travel times are essential to this work, so we will describe them here.

At any given time $t$, let $N(t)$ denote the number of users currently traveling in the transportation network. For $1\leq i\leq N(t)$, the state of user $i$ at time $t$, given by $s(t,i)\in\left\{0,1\right\}^{m}$, specifies which road the user is on. The $e^{th}$ entry of the vector $s(t,i)$ is given by:

Note that exactly one entry of $s(t,i)$ is $1$ and all others are $0$. The traffic counts at time $t$, denoted $s(t)\in\mathbb{N}^{m}$, represents the total number of vehicles on each road and is defined as

The number of users traveling on road $e$ at time $t$, denoted by $s_{e}(t)$, is defined as $s_{e}(t)=\sum_{i=1}^{N(t)}s_{e}(t,i)$.

In this work we assume that users can communicate with one another through private channels. Concretely, this means that for any pair of users $i$ and $j$, user $i$ can send a message that can only be deciphered by user $j$. Such a communication channel can be easily established using standard public key cryptography systems.

The goal of the system is to periodically broadcast estimated travel times for all roads in the network for the sake of route recommendation. The accuracy of travel time estimates will be measured by mean absolute percentage error (MAPE) as defined in Definition 6.

With Remark 2 in mind, the system’s goal is to compute and announce the traffic counts of the system every $\Delta t$ minutes. Concretely, for each $k\in\mathbb{N}$, at time $k\Delta t$ the $N(k\Delta t)$ traveling users must compute an approximation to $s(k\Delta t)$ in a distributed and privacy-preserving way where privacy is defined according to Definition 7.

To ensure user privacy, there are two requirements we impose on a desired protocol for the computation of traffic counts: cryptographic security and differential privacy.

As previously mentioned, our goal is to compute a differentially private approximation to $s(k\Delta t)$ for every $k\in\mathbb{N}$. For this we will use the Laplace Mechanism [8] , which produces a differentially private estimate $S(k\Delta t)$ to $s(k\Delta t)$ based on the following rule

where $Z\in\mathbb{R}^{m}$ has independent and identically distributed entries according to the Laplace distribution with mean $0$ and scale parameter $\frac{1}{\epsilon}$ defined below.

We use the Laplace mechanism because it provides a differentially private approximation with the minimum possible mean absolute error [22].

Since we are interested in a decentralized and trustless computation model, the following remark shows that care must be taken in the computation of $S(k\Delta t)$, particularly pertaining to the computation of $Z$, in order for differential privacy to be achieved.

In light of Remark 6, in the next subsection we discuss a cryptographic technique called secret sharing which we will use for a cryptographically secure computation of $S(k\Delta t)$.

In this section we review a cryptographic tool known as secret sharing and discuss how different variants of it can be used to enable cryptographically secure arithmetic operations on private data. We describe how cryptographically secure addition can be performed on private data in Section 3.2.1 using Additive Secret Sharing, and how cryptographically secure multiplication can be performed on private data in Section 3.2.2 using Shamir Secret Sharing.

In this section we show how the differential privacy and secret sharing tools we have discussed can be used to construct a privacy-preserving and decentralized protocol for travel time estimation, which can then be used by a routing service to recommend routes as per Remark 2. The protocol is described in Algorithm 1.

In order to satisfy the privacy requirements as stated in Definition 7, our protocol must be both differentially private and cryptographically secure. Recall from Section 3.1 that we will use the Laplace mechanism to obtain a differentially private estimate $S(k\Delta t)$ to the traffic counts, which is defined below

where $Z$ is an i.i.d. vector of $\mathcal{L}_{\epsilon}$ distributed random variables. We thus need to compute $S(k\Delta t)$ in a decentralized and cryptographically secure way.

In this section we demonstrate how to compute one entry of the vector $S(k\Delta t)$, i.e., $s_{e}(k\Delta t)+Z_{e}$ for an edge $e\in E$. The computation of the entire vector $S(k\Delta t)$ is obtained by parallelizing the computation of all entries.

We begin by choosing a large prime integer $p$. Inverse transform sampling is a method which can transform a uniform random variable into a random variable with a desired distribution. Using this method we can compute $Z_{e}=F^{-1}(U_{e})$ where $U_{e}$ is uniformly distributed over $\left\{0,1,...,p-1\right\}$ and $F^{-1}$ is a scaled version of the cumulative distribution function of $\mathcal{L}_{\epsilon}$. Concretely, $F^{-1}$ is given by

To make the sampling of $Z_{e}$ more computationally efficient, we will approximate $F^{-1}$ with a degree $d$ polynomial $P_{\epsilon,d}$. A larger degree leads to a more accurate approximation of the Laplace distribution but comes at a computational cost.

Thus approximately computing $S_{e}(k\Delta t)$ amounts to computing $s_{e}(k\Delta t)+P_{\epsilon,d}(U_{e})$ where $U_{e}$ is required to be uniformly distributed over $\left\{0,1,...,p-1\right\}$. First, additive shares $\left\{\alpha_{1},...,\alpha_{N(k\Delta t)}\right\}$ for $s_{e}(k\Delta t)$ can be computed using Secure Multi-Party Addition as is done in Example 2. Next, note that if $Y_{1},Y_{2},...,Y_{N(k\Delta t)}$ are independent and uniformly random on $\left\{0,1,...,p-1\right\}$, then $\sum_{i=1}^{N(k\Delta t)}Y_{i}\mod p$ is also uniformly distributed. Therefore user $i$ will draw a random value $U_{e,i}$ so that the value $U_{e}:=\sum_{i=1}^{N(k\Delta t)}U_{e,i}$ will be uniformly distributed. Using Secure Multi-Party Addition, the users can obtain additive shares $\left\{\beta_{1,1},...\beta_{1,N(k\Delta t)}\right\}$ for $U_{e}$. The users will need to compute $P_{\epsilon,d}(U_{e})$. Since $P_{\epsilon,d}$ is a polynomial of degree $d$, the users will need additive shares for $U_{e}^{2},U_{e}^{3},...U_{e}^{d}$ for the computation of $P_{\epsilon,d}(U_{e})$. The users can obtain such shares through Secure Multi-Party Multiplication by multiplying $U_{e}$ with itself using Shamir and Additive Secret Sharing as described in Example 3. Using this method the users obtain additive shares $\left\{\beta_{z,1},...\beta_{z,N(k\Delta t)}\right\}_{z=0}^{d}$ for $\left\{U_{e}^{z}\right\}_{z=0}^{d}$ respectively. Letting $c_{0},...,c_{d}$ be the coefficients of $P_{\epsilon,d}$ so that $P_{\epsilon,d}(u)=\sum_{z=0}^{d}c_{z}u^{z}$, the users can now construct additive shares for $s_{e}(k\Delta t)+P_{\epsilon,d}(U_{e})$ by taking linear combinations of previously computed shares. Explicitly, the shares

are additive shares for $s_{e}(k\Delta t)+P_{\epsilon,d}(U_{e})$ since by construction we have

Algorithm 1 describes the procedure that each user performs to enable the decentralized and privacy-preserving computation of $S(k\Delta t)$.

Recall that $S_{e}(k\Delta t)=s_{e}(k\Delta t)+Z_{e}$ is a differentially private estimate of the traffic count on road $e$ at time $t$. The mean absolute percentage error (MAPE) of $S_{e}(k\Delta t)$ as an estimate for $s_{e}(k\Delta t)$ is given by

From this we can make two conclusions. When there is a lot of traffic on $e$, meaning that $s_{e}(k\Delta t)$ is much larger than $\frac{1}{\epsilon}$, then $\epsilon s_{e}(k\Delta t)$ will be large and hence $S_{e}(k\Delta t)$ will have a small MAPE. However, if $s_{e}(k\Delta t)$ is small, then $S_{e}(k\Delta t)$ will have a large MAPE.

This shows us that the Laplace Mechanism has poor accuracy when reporting small values. In fact, this is true for all differentially private mechanisms since the Laplace Mechanism has the minimum mean absolute error among all differentially private mechanisms [22]. This observation is consistent with Example 1 in that sparse data and small values pose the most difficulty in privacy-preserving efforts.

Fortunately, this bad news does not end our hopes for achieving both accuracy and privacy in travel time estimation. Even if $S_{e}(k\Delta t)$ may not always be a good estimate for $s_{e}(k\Delta t)$, recall that our ultimate objective is travel time estimation, so we are interested in how well $\tau_{e}(S_{e}(k\Delta t))$ approximates $\tau_{e}(s_{e}(k\Delta t))$. Recall Definition 4 for a description of $\tau_{e}$. Next we will show how properties of delay functions can enable accurate travel time estimates even if traffic count estimation is poor.

In this section we show that if a road $e\in E$ is sufficiently large, then the travel time estimates computed from $S_{e}(k\Delta t)$ are close to the travel time estimates computed from the ground truth $s_{e}(k\Delta t)$. Mathematically, this means that $\tau_{e}(S_{e}(k\Delta t))$ is a good estimate for $\tau_{e}(s_{e}(k\Delta t))$.

The key insight behind our result lies in the complementary qualities of differential privacy and volume delay functions. As we saw in Section 4.1, the Laplace mechanism has good accuracy when reporting large values, but poor accuracy for reporting small values. Volume delay functions on the other hand, are very sensitive when the input is large, but very insensitive when the input is small. When composing a volume delay function with a Laplace mechanism, the complementary qualities manifest in two ways. When the traffic $s_{e}(k\Delta t)$ is larger than a road’s capacity, the volume delay function is very sensitive. Fortunately, in this case the high accuracy of the Laplace mechanism ensures that the traffic count is estimated accurately, leading to accurate traffic flow estimation, which leads to accurate travel time estimation. On the other hand, when the traffic is below the road’s capacity, the Laplace mechanism has poor accuracy, however the delay function is very insensitive in this regime and is able to tolerate large estimation error, leading to accurate travel time estimation. Thus the Laplace mechanism and volume delay function cover each others’ weaknesses to enable accurate travel time estimation for any level of traffic.

We formalize this insight through Theorem 1, which, given desired privacy and accuracy levels $\epsilon$ and $\delta$ respectively, provides conditions under which $\tau_{e}(S_{e}(k\Delta t))$ will be close to $\tau_{e}(s_{e}(k\Delta t))$ with high probability. The condition is determined by the road’s $\delta$-critical traffic count, which is defined below.

One natural and immediate question is whether the requirement on the $\delta$-critical traffic count of roads in Theorems 1 are satisfied by real road networks. To answer this question we first discuss parameter choices. To ensure a meaningful privacy guarantee for each timestep, $\epsilon$ should be significantly smaller than $1$. For this reason we focus on applications where $\epsilon=0.2$.

With $\epsilon=0.2$, $\delta=0.1$ and $p=0.1$, the condition in Theorem 1 requires that a road’s $\delta$-critical count be at least $127$ cars. For such roads, the Theorem states that the estimated travel time will be within 10 percent of the ground truth with probability at least 90 percent. To see whether such a requirement is reasonable, we studied a real world transportation network. The $\delta$-critical capacities of all roads in the Sioux Falls transportation network are plotted in Figure 3. The figure shows that more than 80 percent of the roads in the Sioux Falls network have $\delta$-critical counts above 127. Thus the conditions required by Theorem 1 are realistic for most roads.

Care must also be taken in choosing the value of $\Delta t$, i.e. the amount of time between updates to the estimated traffic counts. Specifically, $\Delta t$ should be chosen so that it is similar to the typical travel time of a road in the network. If $\Delta t$ is much smaller than the typical travel time on a road, then sample average approximation can be used to denoise $S(k\Delta t)$ to get a better estimate of $s(k\Delta t)$. While better estimation is usually good, it is also synonymous with less privacy. To illustrate this concept, suppose that for timesteps $1,2,3,...,N$ the ground truth traffic counts for a given road $e$ is constant, meaning that there is a value $s_{e}$ so that $s_{e}(k\Delta t)=s_{e}$ for all $1\leq k\leq N$. Now for each $k$, $S_{e}(k\Delta t)$ is an unbiased estimator for $s_{e}$ with variance $\frac{2}{\epsilon^{2}}$. This variance is necessary to ensure differential privacy. However, note that $\frac{1}{N}\sum_{k^{\prime}=1}^{N}S_{e}(k^{\prime}\Delta t)$ is also an unbiased estimator for $s_{e}$ but now has variance $\frac{2}{N\epsilon^{2}}$. This decrease in variance leads to worse privacy guarantees. For this reason, $\Delta t$ should be chosen similar to the travel time of a road so that $N$ can never get too large.

The properties of the Sioux Falls road network as well as the typical user demands is obtained from the Transportation Network Test Problems (TNTP) dataset. The Sioux Falls road network consists of 24 nodes and 76 edges. Each edge is characterized by a maximum speed, free flow throughput (i.e., vehicles per hour), and length of the segment. Note that we use the terms edge and road interchangeability. Travel times are computed using BPR functions whose parameters are obtained from the aforementioned edge characteristics. Additionally, the dataset also reports the steady state traffic demand between 528 origin-destination (OD) pairs.

We conduct two types of experiments: private routing and non-private routing. In both types of experiments we simulate traffic flow on the network at a time resolution of $10$ seconds. At every time step, we draw new demand from a Poisson distribution, with the mean demand proportional to the steady state demand reported in the dataset. Thus, at each time step, we draw a random number of vehicles with a corresponding origin and destination. For each vehicle, we identify a shortest travel time route between its origin and destination nodes. In the private routing experiment, the shortest path is computed using the most recent travel time estimates produced by our protocol. In the non-private routing experiment, the shortest path is computed using the ground truth travel time which depends on the ground truth traffic counts. In both types of experiments, the simulated movement of the vehicles on the road network is determined by the ground truth traffic counts on that road.

The duration of the simulation is 2 hours, with additional buffer time in the end for vehicles already in transit to complete their trips. For the private routing experiments, the vehicles are assumed to use our protocol to update travel time estimates every $\Delta t=2$ minutes to minimize the number of reports that a vehicle makes from the same road (See Section 4.3). In our experiments, we consider $\epsilon$ values of $0.01$ and $0.1$. We will discuss how our protocol would perform for other values of $\epsilon$ in Section 5.2. We consider three vehicle demand profiles. In the baseline scenario, about 60,120 vehicles are expected to join the road network every hour. We also consider a low demand scenario, where all the OD Poisson parameters are decreased by 50% and a high demand scenario, where all the OD Poisson parameters are increased by 50%. To gain some more insight into the degree of strain this demand induces on the road network, we refer the reader to Table 1. Here, we report the rate of vehicles being added to the network for each scenario as well as the minimum, maximum, and average road utilization during the simulation period. The road utilization is defined as the term $x/c$ from Remark 1. Utilization greater than 1 indicates congestion on a road. The baseline demand profile results in several congested roads – representing a realistic scenario for testing our protocol. Additionally, as expected, increasing the demand rate results in a higher road utilization and more congested roads.

We evaluate the impact of privacy noise on the routes and travel times of vehicles in the network. Table 2 presents several performance measures for $\epsilon=0.01$ under the three demand profiles. Note that the choice of $\epsilon=0.01$ is overly conservative since smaller $\epsilon$ represents a stricter privacy requirement and thus more noise injected into the system. Typical values of $\epsilon$ that are chosen in practice are larger than 0.1 depending on the application. Nevertheless, we consider this relatively stringent privacy requirement to understand the performance limits our protocol.

From Table 2, we first observe that the increase in average travel time for a vehicle is only 8 seconds in the baseline case. This corresponds to a 1.3% increase in travel time. For the low and high demand scenarios, the increase in average travel times are 3.1 sec (0.6%) and 13.2 sec (1.9%) respectively. Vehicles will experience a low additional travel time if the routing decisions for vehicles from our protocol closely resembles what they would have done without any privacy noise. In other words, if the shortest paths on the graph with noisy travel time estimates is the same (or very similar) to the shortest path on a graph with accurate travel time estimates, the vehicles will experience very little additional travel time. Our results confirm that this is indeed the case – the routes chosen by almost 90% of the vehicles are unchanged due to our protocol. Finally, as we compare the three demand scenarios, we observe that higher demand results in greater congestion and subsequently higher travel times. Furthermore, when demand is higher, the choice of an appropriate route for each vehicle is even more critical to minimize. Working with noisy estimates of travel time, during periods of high congestion can thus lead to incorrect routing choices. This is consistent with our observation that the route of 90.9% of the cars are unchanged by our protocol when the demand is low, but only 87% of the routes remain unchanged when the demand is high.

Next, we study the performance of our protocol with a lower privacy setting of $\epsilon=0.1$. Note that we expect that the performance of our protocol converges to the non-private setting as $\epsilon\rightarrow\infty$. Interestingly, our results show that even with $\epsilon=0.1$, the performance of our protocol becomes indistinguishable to the non-private setting. The performance of our protocol for $\epsilon=0.1$ is shown in Table 3. We observe that the increase in travel time is nearly 0 for all the three demand scenarios. In fact, the randomness in the travel time estimates can also result in marginal improvements in travel time in some settings (reflected as a negative increase in travel time). Not surprisingly, the routes chosen by nearly all the cars also is unaffected by our privacy preserving protocol. The results from varying $\epsilon$ are very encouraging – for a reasonable privacy requirement, we are able to get privacy for ‘free’ with no loss in system performance. Although not shown for brevity, our experiments indicated that cars observe no increase in average travel time for all values of $\epsilon>0.1$.

The results from these experiments are significantly better than what is guaranteed by Theorem 1. As we discussed in Section 4.3, Theorem 1 promises that the estimated travel time on each road will be within 10 percent of the ground truth at least 90 percent of the time when $\epsilon=0.2$. Our numerical results in Table 2 show that even when $\epsilon=0.01$ (i.e., $20$ times as noisy as $\epsilon=0.2$), our protocol only introduces an overhead of 8 percent in the baseline case and 13 percent in a high demand case. We believe this is because real world road networks have redundancy. By this we mean that there are many near-optimal paths from an origin to a destination, so it is very likely that at least one of these paths has an accurately estimated travel time. Theorem 1 looks only at the edge level and is thus does not exploit favorable network topologies. On a positive note, Theorem 1 is general in the sense that it can be applied to a network with any topology and any demand structure.