Locally differentially private continuous location sharing with randomized response

Abstract

With the growing popularity of fifth-generation-enabled Internet of Things devices with localization capabilities, as well as on-building fifth-generation mobile network, location privacy has been giving rise to more frequent and extensive privacy concerns. To continuously enjoy services of location-based applications, one needs to share his or her location information to the corresponding service providers. However, these continuously shared location information will give rise to significant privacy issues due to the temporal correlation between locations. In order to solve this, we consider applying practical local differential privacy to private continuous location sharing. First, we introduce a novel definition of $(\epsilon ,\delta )$ -local differential privacy to capture the temporal correlations between locations. Second, we present a generalized randomized response mechanism to achieve $(\epsilon ,\delta )$ -local differential privacy for location privacy preservation, which obtains the upper bound of error, and serve it as the basic building block to design a unified private continuous location sharing framework with an untrusted server. Finally, we conduct experiments on the real-world Geolife dataset to evaluate our framework. The results show that generalized randomized response significantly outperforms planar isotropic mechanism in the context of utility.

Introduction

With the development of fifth-generation (5G) wireless communication technology, 5G-enabled Internet of Things (5G IoT) with ubiquitous connection is expected to implement various applications. ¹ Benefited from connections and mobility of 5G IoT devices, location-based applications have been significantly increasing by the growing popularity of 5G IoT devices (e.g. smartphones and self-driving vehicles) with localization capabilities. In order to enjoy relevant services, users have to contribute their locations to the corresponding service providers or third parties. For example, if one wants to access services of mobile edge computing (MEC) which is a crucial part of 5G technology, then he or she needs to share his or her location information to the MEC service provider. However, location information gives rise to significant privacy issues.^2,3 Since location information itself is sensitive and it can also be easily associated with other sensitive information, this will result in user privacy leakage.

In a recent decade, a large body of location privacy preservation mechanisms (LPPMs)^4,5 have been emerged in the setting of location-based service (LBS) or location sharing where a user shares his or her location to an unknown/untrusted server or other party to enjoy some services while guaranteeing location privacy of the user. One solution is cryptography-based LPPM to prevent revealing individual locations. ⁶ However, such method tends to be computationally expensive. Most LPPMs have concentrated on location obfuscation that transforms the real location of individual to a region (e.g. location generalization) ⁷ or a perturbed location (e.g. location perturbation). ⁸ The commonly used location obfuscation methods depend on syntactic privacy models (e.g. k-anonymity); however, they do not provide stringent and provable privacy guarantee. Some of them only take into account perturbing the location at a single timestamp without considering the temporal correlations of a user’s locations. Therefore, the proposed methods are vulnerable to various inference attacks.

Differential privacy ⁹ is a state-of-the-art, stringent and provable privacy notion irrelevant to an adversary’s background knowledge and computing power. There are a large number of works adopting differential privacy to location privacy preservation.^1,10 Most of them, for example, Al-Hussaeni et al., ¹¹ Qardaji et al., ¹² and Fanaeepour and Rubinstein, ¹³ have applied the traditional differential privacy (or centralized differential privacy, CDP) ⁹ on location or trace data for data publishing or aggregation with a trusted server. As privacy matters are raised frequently, local differential privacy (LDP) ¹⁴ has been considered in many application fields due to its more stringent and practical privacy. In LDP model, a user does not trust anybody else and requires that his or her own data be moderately protected before sharing them. In other words, the user’s exact data only allowed to be accessed by himself or herself. From the perspective of model, LDP is more suitable for the setting of private location sharing. Randomized response (RR) is the principal mechanism of LDP and suitable for perturbing classified data (e.g. discrete location data).

Adopting LDP for location privacy preservation is still in its infancy. Recently, few works^15,16 have applied LDP on location data for data aggregation and without considering the temporal correlation between locations. More previous works, for example, Andrés et al. ⁸ and Bordenabe et al., ¹⁷ have adopted LDP model in the setting of private location sharing. Andrés et al. ⁸ proposed a novel privacy notion of geo-indistinguishability for LBSs, which ensures that any two locations in a circle are geographically close. In fact, geo-indistinguishability is a special notion of event-level differential privacy, and the neighborhood is defined with Euclidean distance. It is implemented by planar Laplacian mechanism to inject noise drawn from a two-dimensional Laplace distribution into a real location. Bordenabe et al. ¹⁷ proposed an optimal geo-indistinguishability mechanism to improve the utility by linear programming techniques. However, the notion of geo-indistinguishability is vulnerable to inference attacks if an adversary can learn the correlation between locations over time.

Motivations and contributions

In this article, we study the problem of continuous private location sharing under LDP. As shown in Figure 1, a user who has a set of continuous sensitive locations generated by his or her mobile device shares on-the-fly the locations with an untrusted server to enjoy LBSs, while guaranteeing his or her location privacy at any timestamp. A user’s real locations are only known by himself. The perturbed locations generated by the privacy preservation mechanisms are visible to the untrusted server and adversaries. To this end, we apply LDP to private continuous location sharing under temporal correlations, which cannot be hided from adversaries and hence are assumed to be public. Compared to the existing most similar work by Xiao and Xiong ¹⁸ which proposed a traditional differential privacy–based location privacy preservation framework for continuous location sharing, our main contributions are summarized as follows.

Figure 1.

Continuous private location sharing.

First, we propose a novel definition of $(\epsilon ,\delta )$ -LDP to protect the real location at each timestamp, different from the $\delta$ -location set–based differential privacy definition. ¹⁸ Motivated by the definition of $(\epsilon ,\tau )$ -practical local differential privacy ( $(\epsilon ,\tau )$ -PLDP) ¹⁵ where the “possible set” based on safe region only considers spatial correlation and the real location is obfuscated in other locations within safe region, and by the notion of $\delta$ -location set ¹⁸ based on Markov model that can capture all possible locations under temporal correlation, we consider incorporating $\delta$ -location set into LDP to protect location privacy under the temporal correlation. Accordingly, we propose a novel definition of $(\epsilon ,\delta )$ -LDP to capture the temporal correlations for private continuous location sharing, where the parameter $\delta$ is used to construct the “possible set” of LDP, rather than the “neighborhood databases” of traditional differential privacy that used to determine the sensitivity hull. ¹⁸

Second, we present an efficient generalized randomized response (GRR) to achieve $(\epsilon ,\delta )$ -LDP for location perturbation, and serve it as the basic building block to design a unified continuous private location sharing framework with an untrusted server. In addition, we theoretically analyze privacy and utility guarantees of the mechanism, and the analysis results show that GRR for our location setting can achieve the upper bound of error, rather than the lower bound of error of planar isotropic mechanism (PIM). ¹⁸

Third, we experimentally evaluate the performance of GRR over real-world datasets through the continuous location sharing framework and the results show that GRR provides superior location utility, compared with PIM.

Related work

Location privacy

A large number of works have been conducted on preserving location privacy. In general, location privacy preservation method can be classified into three categories: cryptography, anonymization, and obfuscation. ¹⁹ One of the most widely used definitions of location privacy is the notion of k-anonymity. Gruteser and Grunwald ²⁰ first introduced of k-anonymity into location privacy, and the notion has been widely employed in numerous works to preserve the location privacy. The key idea is how to construct an anonymity set and a user reports an anonymity set consisting of at least k users instead of his real location. Therefore, an adversary cannot distinguish a user from at least k–1 other users. However, the main drawback of location privacy preservation methods based on k-anonymity and its variants (e.g. mix zone) is that it does not always provide stringent and provable privacy preservation. Most of them do not consider the temporal correlation among locations and are vulnerable to multifarious inference attacks.

The other significant solution for preserving location privacy is location obfuscation (e.g. spatial cloaking), which transforms and maps a user’s real location to a region or one or more perturbed location. Andrés et al. ⁸ proposed a novel notion of geo-indistinguishability for location privacy, which protects a location within a small radius and requires the closer any location pairwise are, the more indistinguishable they are. Nevertheless, such location perturbation mechanism may not be rational in the setting of continuous location privacy due to not considering the correlation among locations. To prevent loss of privacy due to the correlation between locations in the trace, Chatzikokolakis et al. ²¹ proposed a predictive differential privacy mechanism to reduce privacy budget consumption rate for trace obfuscation. Similarly, Ma et al. ²² proposed an AGENT mechanism for continuous location privacy preservation by introducing R-tree to achieve the reusability of previously perturbed locations. The two mechanisms satisfy the notion of geo-indistinguishability and make use of the previously reported locations to save privacy budget for obfuscated trace. However, the correlation of the two works considered is only used to reduce the privacy budget for improving the utility, not for preventing inference attacks.

Many works have adopted Markov model for modeling users’ mobility and reasoning their locations or traces. Ardagna et al. ²³ proposed an approach for preserving sensitive location information in continuous LBSs. The approach first modeled the characteristics of a user’s moving preference by Markov chain and then developed a simple obfuscation method based on his characteristics. Shokri et al. ²⁴ presented a quantifying location privacy framework, which provides a Markov model for reconstructing prior knowledge (user mobility) of an adversary to be used in various attacks. In the most similar work ¹⁸ to ours, Xiao et al. proposed a PIM for single-user location sharing under temporal correlations modeled by Markov Chain. Hence, we consider adopting the commonly used Markov model for modeling users’ mobility in our work. In fact, PIM is similar to Laplace mechanism and suitable for perturbing numerical data. Nevertheless, since Markov model is a discrete state model and RR is a perturbation mechanism for categorical (discrete) data, PIM based on noise addition will bring more loss of utility than RR in modeling users’ mobility based on Markov model.

Local differential privacy

Differential privacy is the state-of-the-art, stringent and provable privacy technique. It was initially proposed to protect aggregated statistics in the trusted server setting, which is regarded as centralized differential privacy (CDP). But recent works have been focusing on LDP with stronger privacy preservation, since it requires that a user locally perturbs his data and sends the perturbed data to an untrusted server. In recent years, Google has shown its applicability through RAPPOR, ²⁵ which is a practical LDP solution for protecting users’ settings in the browser. Hereafter, Apple ²⁶ and Microsoft ²⁷ have also applied LDP to iOS10 and Windows 10, respectively. LDP has become the most promising privacy preservation technique.

Different from CDP, which basically uses Laplace mechanism and exponential mechanism, LDP mainly adopts randomized response (W-RR) ²⁸ as the fundamental perturbation mechanism, which is first proposed by Warner in 1965. However, since the W-RR is only suitable for binary variables, Kariouz et al. ²⁹ proposed a staircase mechanism, also known as k-randomized response (K-RR), which can be used for multiple variables $(d>2)$ . In fact, W-RR is a special case of K-RR $(d=2)$ . In order to distinguish from the precious notion, Wang et al. ³⁰ generalized W-RR and K-RR into GRR, where k is greater or equal to 2 $(d\ge 2)$ . In their other work, Wang et al. ³¹ conducted a set of analyses on the LDP mechanisms for frequency estimation problem. This work enables us to select optimal mechanism and corresponding parameters for applications based on LDP, and shows that when possible domain size $d<3e^{\epsilon }+2$ , GRR is optimal for use than other comparative mechanisms.

Most works of LDP, for example, Kairouz et al., ²⁹ Bassily and Smith, ³² and Nguyên et al., ³³ have concentrated on the study of locally differentially private simple data, namely, single numeric or categorical attribute. Recently, some researches have applied LDP for preserving more complex data. Qin et al. ³⁴ have applied LDP on set-valued data which is a set of items (values) for heavy hitter estimation. Wang et al. ³⁵ proposed an optimized LDP mechanism for set-valued data aggregation. Several recent works have adopted LDP to protect location privacy. Chen et al. ¹⁵ first applied LDP to solve the private location (spatial) data aggregation problem. Sei and Ohsuga ¹⁶ proposed a Bayesian-based multiple dummies method against untrusted server, which satisfies LDP. The method can also be used to protect single location privacy. Our contribution is to extend LDP to the setting of continuous location sharing for single user whose locations are temporally correlated. To our best knowledge, we first apply LDP to continuous location sharing. We will achieve higher utility in practice while guaranteeing location privacy of users over time.

Preliminaries and privacy definition

We use normal letters, bold lowercase letters, and bold uppercase letters to denote scalar variables, vectors, and matrices, respectively. The summary of some significant symbol notations is shown in Table 1.

Table 1.

Summary of some significant symbol notations.

Notation	Description
${\mathit{c}}_i$	a cell in a divided map, $i=1,\dots ,m$
$\mathit{s},\mathit{l}$	location in state and map coordinates
${\mathit{s}}^{*},{\mathit{l}}^{*}$	real location in state and map coordinates
$\mathit{z}$	perturbed location in state coordinate
${\mathit{p}}_t^{-},{\mathit{p}}_t^{+}$	prior and posterior probability
$\mathrm{\Delta }\mathbf{S},\left|\mathrm{\Delta }\mathbf{S}\right|$	$\delta$ -location set and its size
$\mathit{M}$	public and personal transition matrix

In order to represent a location for Markov model, we use state coordinate system. Space domain is denoted by $\mathit{C}=\{{\mathit{c}}_1,\dots ,{\mathit{c}}_m\}$ , where ${\mathit{c}}_i$ is denoted by a cell, and these cells are the finest granularity generated by dividing $\mathit{C}$ . ${\mathit{c}}_i$ is an m-dimensional unit vector with the ith element being 1 and others being 0. Each cell can represent a state (location). On the contrary, the geometric space is often seen as a map with latitude and longitude, and then a location l is represented by a two-dimensional vector with two elements l [1] and l [2]. An example for such two coordinate systems is shown in Figure 2. Assuming that a location is in ${\mathit{c}}_9$ , its two coordinates are shown as follows

$$\begin{array}{c}\multicolumn{1}{c}{\mathit{s}={\mathit{c}}_9=\left[\begin{array}{cccccccccccc}0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 0\hfill & 1\hfill & \cdots \hfill & 0\hfill \end{array}\right]}\\ \multicolumn{1}{c}{\mathit{l}=\left[\begin{array}{cc}3\hfill & 2\hfill \end{array}\right]\mathrm{with}\mathit{l}\left[1\right]=3\mathrm{and}\mathit{l}\left[2\right]=2}\end{array}$$

Figure 2.

Coordinate systems.

Noting that they can be interconverted, we skip the interconverted process. Over time, a trajectory can be represented by a bunch of locations, ${\mathit{l}}_1,\dots ,{\mathit{l}}_t$ in map coordinate or ${\mathit{s}}_1,\dots ,{\mathit{s}}_t$ in state coordinate.

Mobility and inference model

In our problem setting, a user’s real locations are only observable by himself, but not by others. The perturbed locations generated by the privacy mechanism are observable to the service provider who might be untrusted. From the perspective of an adversary, the above-mentioned process is a Hidden Markov Model (HMM).

Assume that a vector ${\mathit{p}}_t$ is denoted as the probability distribution of a user’s location at timestamp t. Formally

$${\mathit{p}}_t\left[i\right]=\mathrm{Pr}({\mathit{s}}_t^{*}={\mathit{c}}_i)$$

where ${\mathit{p}}_t[i]$ is the ith element in ${\mathit{p}}_t$ and ${\mathit{c}}_i\in \mathit{C}$ .

Transition probability

$\mathit{M}$ is the state transition probability matrix, where the element $m_{\mathrm{ij}}$ is denoted as the transition probability that a user moves from location ${\mathit{l}}_i$ to location ${\mathit{l}}_j$ . Given probability vector ${\mathit{p}}_{t-1}$ , the probability at timestamp t transforms ${\mathit{p}}_t={\mathit{p}}_{t-1}\mathit{M}$ . We suppose that the transition matrix $\mathit{M}$ is given in our work.

Emission probability

Given a real location ${\mathit{s}}_t^{*}$ , a mechanism generates perturbed location ${\mathit{z}}_t$ , and the probability $\mathrm{Pr}({\mathit{z}}_t|{\mathit{s}}_t^{*}={\mathit{c}}_i)$ is referred to as emission probability in HMM, which is used to establish the relationship between states and observations. It is noting that the probability is decided by the obfuscation mechanism.

Inference and evolution

${\mathit{p}}_t^{-}$ and ${\mathit{p}}_t^{+}$ are denoted by the prior and posterior probability of a user location at timestamp t before and after observing the perturbed z_t respectively. At the current timestamp t, the prior probability can be computed by the posterior probability at previous timestamp t–1 and the state transition matrix of the model, that is ${\mathit{p}}_t^{-}={\mathit{p}}_{t-1}^{+}\mathit{M}$ . According to Bayesian rule, given z_t, the posterior probability can be computed as follows. For each cell ${\mathit{c}}_i$

$${\mathit{p}}_t^{+}\left[i\right]=\mathrm{Pr}({\mathit{s}}_t^{*}={\mathit{c}}_i|{\mathit{z}}_t)=\frac{\mathrm{Pr}({\mathit{z}}_t|{\mathit{s}}_t^{*}={\mathit{c}}_i){\mathit{p}}_t^{-}\left[i\right]}{\sum _j\mathrm{Pr}({\mathit{z}}_t|{\mathit{s}}_t^{*}={\mathit{c}}_j){\mathit{p}}_t^{-}\left[j\right]}$$

(1)

The inference process at each timestamp can be availably derived by forward–backward algorithm in HMM.

Combining the characteristic of LDP model, we consider two different types of M in the light of data source which is used to construct the inference model: one is Public M which is derived with public data and the other is Personal M which is learned from personal data. Nevertheless, different inference models (adversaries) may take different effects on the utility of shared locations. We will also contrast the two inference models in later experiments.

LDP and RR mechanism

The LDP was proposed for the local setting in which there is an untrusted server which is not allowed to access the private data. In general, users only share their information to service provider for enjoying the corresponding services. And yet, users do not trust anyone except themselves and tend to guarantee their privacy at the root that the shared information has been properly sanitized before sharing it themselves. LDP requires that no matter which data value an individual user possesses, the data collector (e.g. an untrusted server) should get almost identical information. Therefore, an adversary with any background knowledge cannot distinguish the individual real value by accessing to the sanitized information. Formally, the definition of LDP is given below.

Definition 1: (Local differential privacy)

A randomized algorithm is $\epsilon$ -LDP, where $\epsilon \ge 0$ , if and only if any pair of values $\mathit{l},\mathit{l}\prime \in \mathcal{L}$ , for all $\mathit{O}\subseteq \mathrm{Range}(A)$

$$\mathrm{Pr}[A\left(\mathit{l}\right)\in \mathit{O}]\le e^{\epsilon }·\mathrm{Pr}[A(\mathit{l}\prime )\in \mathit{O}]$$

where $\mathrm{Range}(A)$ denotes the set of all possible outputs of algorithm $A$ and the probability is over the coin flips of $A$ .

LDP provides stringent privacy preservation in local setting, but its utility is bounded by the privacy domain. If the privacy domain size $\left|\mathcal{L}\right|$ is large, it is difficult in the trade-off between privacy and utility under LDP. A prominent nature of LDP is that a user can take full control of his or her privacy by independently perturbing data to a certain range that meets his or her own privacy preference.

Randomized response

The RR is the fundamental mechanism to achieve LDP. We present the RR by a simple example that is given below. Given a binary attribute, one report a real value with probability $p$ and the flip of unreal value with probability $1-p$ . This satisfies $\ln (p/(1-p))$ -LDP.

Composability

In our problem setting, we need to only release one perturbed location at a timestamp, so the sequential composition property is unavailable. However, for multiple releases at a timestamp, the composition property is applicable. In addition, privacy guarantee for the whole trajectory (e.g. release a set of perturbed locations $\{{\mathit{z}}_1,\dots ,{\mathit{z}}_t\}$ from timestamp 1 to t) is also not considered.

$\delta$ -location set

To capture the temporal correlations between locations, we introduce the concept of $\delta$ -location set to obtain a user’s possible locations at each timestamp. At any timestamp $t$ , a prior probability of the user’s current location is denoted by ${\mathit{p}}_t^{-}[i]=\mathrm{Pr}({\mathit{s}}_t^{*}|{\mathit{z}}_{t-1},\dots ,{\mathit{z}}_1)$ . And we set a parameter $\delta$ to derive the possible locations of the user; $\delta$ -location set $\mathrm{\Delta }{\mathbf{S}}_t$ is a set including minimum number of locations that have prior probability sum no less than $1-\delta$

$$\mathrm{\Delta }{\mathbf{S}}_t=\min \{{\mathit{c}}_i|\sum _{{\mathit{c}}_i}{\mathit{p}}_t^{-}\left[i\right]\ge 1-\delta \}$$

For instance, assuming that a prior probability ${\mathit{p}}_t^{-}=[0.2,0.3,0.1,0.02,0.03,0.35]$ with corresponding to $[{\mathit{c}}_1,{\mathit{c}}_2,{\mathit{c}}_3,{\mathit{c}}_4,{\mathit{c}}_5,{\mathit{c}}_6]$ , if $\delta =0.2$ , then $\mathrm{\Delta }\mathbf{S}=\{{\mathit{c}}_6,{\mathit{c}}_2,{\mathit{c}}_1,{\mathit{c}}_3\}$ ; if $\delta =0.06$ , then $\mathrm{\Delta }\mathbf{S}=\{{\mathit{c}}_6,{\mathit{c}}_2,{\mathit{c}}_1\}$ . Noting that if $\delta =0$ , then $\mathrm{\Delta }\mathbf{S}$ includes all possible locations.

Privacy definition

The nature of $(\epsilon ,\tau )$ -PLDP ¹⁵ is to “hide” a real location in a safe region so that an adversary is unable to distinguish the real location from any other locations in the safe region $\tau$ . This is only applicable for spatial correlation problem, rather than spatial-temporal correlation we consider, since temporal correlation based on a user’s moving patterns in practice is not considered in the construction of safe region. So, it is vulnerable to inference attacks by adversary with background knowledge. In addition, the size of safe region is critical to data utility. Motivated by an a notion of $\delta$ -location set which reflects a set of possible locations the user might frequently appear (by filtering out the locations with small probability), we consider incorporating $\delta$ -location set into LDP and propose a novel definition of LDP for continuous private location sharing setting. We define the LDP based on $\delta$ -location set so that an adversary cannot discriminate the real location from these locations in the $\delta$ -location set.

Definition 2: ( $(\epsilon ,\delta )$ -Local differential privacy)

At any timestamp t, a randomized mechanism $A$ satisfies $({\epsilon }_t,{\delta }_t)$ -differential privacy on $\delta$ -location set $\mathrm{\Delta }{\mathbf{S}}_t$ , if for any output ${\mathit{z}}_t\in \mathrm{Range}(A)$ and any locations ${\mathit{l}}_t,{\mathit{l}}_t^{\prime }\in \mathrm{\Delta }{\mathbf{S}}_t$ , the following holds

$$\mathrm{Pr}(A\left({\mathit{l}}_t\right)={\mathit{z}}_t)\le {\mathrm{e}}^{{\epsilon }_t}·\mathrm{Pr}(A\left({\mathit{l}}_t^{\prime }\right)={\mathit{z}}_t)$$

The above definition makes the real location protected within the ${\delta }_t$ -location set (temporal safe region) at each timestamp. To be specific, the perturbed location ${\mathit{z}}_t$ is LDP at timestamp t for the setting of continuous private location sharing. For other application settings, such as preserving individual trajectory, we will investigate the setting in future work.

Proposed framework

GRR mechanism

The GRR mechanism is a general version of the RR mechanism. In a particular case where the value is binary, that is $d=\left|D\right|=2$ , $A_{\mathrm{GRR}}(v)$ keeps the value unchanged with probability $e^{\epsilon }/(e^{\epsilon }+1)$ and turns it with probability $1/(e^{\epsilon }+1)$ . In the general case where the value is multi-ary, namely, $d=\left|D\right|>2$ , the perturbed mechanism is defined as follows

$$\mathrm{Pr}[A_{\mathrm{GRR}}\left(v\right)=\mathit{z}]=\{\begin{array}{c}\frac{e^{\epsilon }}{e^{\epsilon }+d-1},\mathrm{if}\mathit{z}=v\hfill \\ \multicolumn{1}{c}{\frac{1}{e^{\epsilon }+d-1},\mathrm{if}\mathit{z}\ne v}\end{array}$$

Algorithm 1 shows the pseudocodes of GRR mechanism for location. Given privacy budget $\epsilon$ , a real location ${\mathit{l}}^{*}$ , and location set $\mathrm{\Delta }\mathbf{S}$ , the algorithm returns a perturbed location z that belongs to $\mathrm{\Delta }\mathbf{S}$ . Specifically, the perturbed location is the real location with the probability $e^{\epsilon }/(e^{\epsilon }+\left|\mathbf{\Delta }\mathbf{S}\right|-1)$ ; otherwise, the perturbed location is selected uniformly at random from the set $\{\mathrm{\Delta }\mathbf{S}/{\mathit{l}}^{*}\}$ . In other words, the perturbed location is the dummy location with the probability $1/(e^{\epsilon }+\left|\mathbf{\Delta }\mathbf{S}\right|-1)$ . The following theorem provides the theoretical guarantee of Algorithm 1.

Algorithm 1. Generalized Randomized Response (GRR).
Input: $\epsilon ,{\mathit{l}}^{*},\mathrm{\Delta }\mathbf{S}$ Output: $z$ 1: $b~$ Bern( $e^{\epsilon }/(e^{\epsilon }+\left|\mathrm{\Delta }\mathbf{S}\right|-1)$ );2: if $b=1$ then3:   $\mathit{z}={\mathit{l}}^{*}$ ;4: else5:   $\mathit{z}~$ Uniform $(\{\mathrm{\Delta }\mathbf{S}/{\mathit{l}}^{*}\})$ ;6: end if7: return $\mathit{z}$ ;

Theorem 1

Algorithm 1 satisfies $(\epsilon ,\delta )$ -LDP, where the parameter $\delta$ determines the location set $\mathrm{\Delta }\mathbf{S}$ .

Proof

$\delta$ -location set is a set of locations that a user often visits. Assume that the $\delta$ -location set is denoted by $\mathrm{\Delta }\mathbf{S}$ . For any locations $\mathit{l},\mathit{l}\prime \in \mathrm{\Delta }\mathbf{S}$ and output $\mathit{z}$ , we have

$$\frac{\mathrm{Pr}[A_{\mathrm{GRR}}\left(\mathit{l}\right)=\mathit{z}]}{\mathrm{Pr}[A_{\mathrm{GRR}}(\mathit{l}\prime )=\mathit{z}]}\le \frac{p}{q}=\frac{\frac{e^{\epsilon }}{(e^{\epsilon }+\left|\mathbf{\Delta }\mathbf{S}\right|-1)}}{\frac{1}{(e^{\epsilon }+\left|\mathbf{\Delta }\mathbf{S}\right|-1)}}=e^{\epsilon }$$

This completes the proof.

Continuous private location sharing framework

Location obfuscation algorithm is shown in Algorithm 2. At any timestamp t, we compute the prior probability vector ${\mathit{p}}_t^{-}$ . If the location needs to be shared, we construct a $\delta$ -location set $\mathbf{\Delta }{\mathbf{S}}_t$ . Then, a local differential private mechanism can be adopted to release a perturbed location ${\mathit{z}}_t$ . Meanwhile, the perturbed ${\mathit{z}}_t$ will also be used to update the posterior probability ${\mathit{p}}_t^{+}$ which will be used to compute the prior probability for the next timestamp $t+1$ . Subsequently, at timestamp $t+1$ , the above process is repeated.

Algorithm 2. Location Obfuscation Algorithm.

Input: ${\epsilon }_t,{\delta }_t,\mathit{M},{\mathit{p}}_{t-1}^{+},{\mathit{l}}_t^{*}$ Output: ${\mathit{p}}_t^{+},{\mathit{z}}_t$ 1: ${\mathit{p}}_t^{-}={\mathit{p}}_{t-1}^{+}\mathit{M}$ ;2: if the current location needs to be shared then3:  Computing $\mathrm{\Delta }{\mathbf{S}}_t$ based on ${\mathit{p}}_t^{-}$ ;4:  if ${\mathit{l}}_t^{*}\notin \mathrm{\Delta }{\mathbf{S}}_t$ then5:   Adding ${\mathit{l}}_t^{*}$ to $\mathrm{\Delta }{\mathbf{S}}_t$ ;6:  end if7:   ${\mathit{z}}_t=\mathrm{GRR}({\mathit{l}}_t^{*},\mathrm{\Delta }{\mathbf{S}}_t,{\mathbf{\epsilon }}_t)$ ;8:  Computing posterior probability ${\mathit{p}}_t^{+}$ by formula (1);9:  return ${\mathit{p}}_t^{+},{\mathit{z}}_t$ 10: end if

Since the drawback of $\delta$ -location set is that the real location with small probability may be excluded, this leads to a “drift” phenomenon which may also occur when the Markov model is not accurate enough in practice in virtue of its limited predictability. To solve this problem, the “surrogate” approach with real location is applied in our method, instead of the “surrogate” approach ¹⁸ that the surrogate location is the cell in $\mathrm{\Delta }\mathbf{S}$ with the shortest distance to the real location. This will achieve better utility while still guaranteeing stringent privacy.

Note that the surrogate method does not leak any information of the real location. Because ${\mathit{l}}^{*}$ is always included in $\mathrm{\Delta }\mathbf{S}$ , and then ${\mathit{l}}^{*}$ is protected in $\mathrm{\Delta }\mathbf{S}$ , we formally prove the privacy guarantee in Theorem 2.

Theorem 2

At any timestamp t, Algorithm 2 satisfies $({\epsilon }_t,{\delta }_t)$ -LDP.

Proof

In our method, although a drift happens, the real location is still in $\mathrm{\Delta }{\mathbf{S}}_t$ . According to Theorem 1, ${\mathit{z}}_t$ satisfies ${\epsilon }_t$ -LDP. Therefore, Algorithm 2 is $({\epsilon }_t,{\delta }_t)$ -LDP.

The above algorithm is single private location sharing. Here, we show the framework of continuous private location sharing in Algorithm 3. To enable the framework, we first initialize the initial prior probability ${\mathit{p}}_1^{-}$ and posterior probability ${\mathit{p}}_1^{+}$ . Assume that the ${\mathit{p}}_1^{-}={\mathit{p}}_1^{+}=1$ and the starting location $(t=1)$ is not shared. Then, at each timestamp $(t>1)$ , we run Algorithm 1 to share privately the current location.

Algorithm 3. Continuous Private Location Sharing Framework.
require: $\mathbf{\epsilon },\mathbf{\delta },\mathit{M},{\mathit{l}}^{*}$ ;1: initialize prior and posterior probability ${\mathit{p}}_1^{-}={\mathit{p}}_1^{+}=1$ ;2: for $t=2:T$ 3:   ${\mathit{p}}_t^{+},{\mathit{z}}_t$  = Algorithm 2( ${\epsilon }_t,{\delta }_t,\mathit{M},{\mathit{p}}_{t-1}^{+},{\mathit{l}}_t^{*}$ );4: end for

Noting that the two $({\epsilon }_t,{\mathrm{\delta }}_t)$ privacy parameters are specified by a user, and the user’s location privacy is fully controlled by the user over time, the protection can be enforced at any timestamp. The input parameters $\mathbf{\epsilon },\mathbf{\delta }$ are vectors of these corresponding parameters over the whole timestamps. For simplicity, we assume the parameters ${\epsilon }_t,{\delta }_t$ at each timestamp are same.

Privacy and performance analysis

The privacy analysis is presented in Theorem 2. We will present the utility of GRR.

Theorem 3

The upper bound of error for Algorithm 2 is O(Diam( $\mathrm{\Delta }\mathbf{S}$ )), where Diam( $\mathrm{\Delta }\mathbf{S}$ ) is the diameter of $\mathrm{\Delta }\mathbf{S}$ .

Proof

$\mathrm{\Delta }\mathbf{S}$ is a point set, which is a set of two or more points. If its size is two, the error is the distance between two points; if the size is more than two, the error is the diameter of its convex hull.

Moving model construction and location inference

We discuss the construction (learning) of Markov model. Maximum likelihood estimation and expectation maximization method in HMM can be adopted to obtain the transition matrix. However, depending on the power of adversaries, two typical $\mathit{M}$ can be learned: (1) Public $\mathit{M}$ can be learned from public data and (2) Personal $\mathit{M}$ can be derived with personal data. For simplicity, we consider the maximum likelihood estimation method to estimate the matrix. The public matrix is regarded as public background knowledge, for example, road network. The personal matrix is seen as the personal background knowledge, for example, user’s moving pattern. The knowledge is transparent for an adversary. However, the utility of perturbed locations may vary with different background knowledge of the adversary. We will compare the two models (two different background knowledge) in later experimental evaluations.

Inference methods rest with specific perturbed algorithms. We implement the inference for GRR in the light of the formula (1) and calculate the probability $\mathrm{Pr}({\mathit{z}}_t|{\mathit{s}}_t^{*}={\mathit{c}}_i)$ as follows

$$\mathrm{Pr}({\mathit{z}}_t|{\mathit{s}}_t^{*}={\mathit{c}}_i)=\{\begin{array}{c}\frac{e^{{\epsilon }_i}}{e^{{\epsilon }_i}+\left|\mathrm{\Delta }\mathbf{S}\right|-1},\mathrm{if}{\mathit{z}}_t={\mathit{c}}_i\hfill \\ \multicolumn{1}{c}{\frac{1}{e^{{\epsilon }_i}+\left|\mathrm{\Delta }\mathbf{S}\right|-1},\mathrm{if}{\mathit{z}}_t\ne {\mathit{c}}_i}\end{array}$$

Experimental evaluation

The experimental evaluation is described in this section. All algorithms are implemented in the MATLAB R2018a on a PC with 3.6 GHz Intel Core i3 CPU and 8 GB RAM. We compare the performance of GRR with PIM that is the most relevant to our work.

Experimental setup

Datasets

We use a public real-world Geolife dataset ³⁶ as the experimental dataset. The dataset was gathered from 182 users during the 3 years. It recorded a wide range of users’ mobility behaviors, represented by a batch of records including timestamp, latitude, and longitude. The locations data were updated at relatively high frequency, ranging from 1 to 60 s. We extract all trajectories within roughly third ring of Beijing (116.3017E~116.4577E, 39.848N~39.9680N) to train the Markov model. Note that the area is divided into cells of $0.34\times 0.34\mathrm{k}{\mathrm{m}}^2$ , namely, $50\times 50$ state cells.

Metrics

We evaluate the performance of GRR and PIM in following metrics. On the one hand, since our privacy definition is related to privacy budget $\epsilon$ and $\delta$ -location set $\mathrm{\Delta }\mathbf{S}$ , we evaluate the size of $\mathrm{\Delta }\mathbf{S}$ to learn how $\mathrm{\Delta }\mathbf{S}$ changes. On the other hand, we conduct the utility metric by measuring the distance between the perturbed location and the real location, namely, $d({\mathit{x}}_i-{\tilde{\mathit{x}}}_i)$ which can be independent of specific location-based applications. And by measuring the average distance between locations in real trace and perturbed trace, namely, $\mathrm{dis}(\mathit{X},\tilde{\mathit{X}})=\sum _{i}d({\mathit{x}}_i-{\tilde{\mathit{x}}}_i)/\left|\mathit{X}\right|$ , where $\mathit{X}$ and $\tilde{\mathit{X}}$ are the real trace and perturbed trace, respectively.

Evaluation results

• 1. Performance over time

In order to present the performance of a perturbed mechanism while a user moves over time, including how $\mathrm{\Delta }\mathbf{S}$ changes and how the perturbed location is used, we conduct a batch of experiments to evaluate these performances for a single trajectory with personal matrix learned from a user who has a number of trajectories and public matrix learned from all users. We randomly choose a test trajectory from the user’s trajectories, which consists of 1405 timestamps. The real trace in the form of state and map coordinates is shown in Figure 3.

Figure 3.

Real trace.

We evaluate both GRR and PIM at each timestamp with $\epsilon =1$ and $\delta =0.01$ under the public and personal matrix, respectively. We run each mechanism 10 times, and give the average. Figure 4(a) and (b) as well as Figure 5(a) and (b) show separately the perturbed locations at each timestamp with public and personal matrix. We can perceive that the perturbed locations generated by GRR are closer to the real location, compared with PIM.

Figure 4.

Performance over time under public matrix: (a) PIM perturbed trace, (b) GRR perturbed trace, (c) size of $\mathrm{\Delta }\mathbf{S}$ , and (d) distance.

Figure 5.

Performance over time under personal matrix: (a) PIM perturbed trace, (b) GRR perturbed trace, (c) size of $\mathrm{\Delta }\mathbf{S}$ , and (d) distance.

Size of $\mathrm{\Delta }\mathbf{S}$ over time with public and personal matrix is shown in Figures 4(c) and 5(c), respectively. First, we can figure out the size of $\mathrm{\Delta }\mathbf{S}$ changes dramatically. The reason is that selecting the $\delta$ -location set by the inference mechanism will change not only the probabilities of location in $\mathrm{\Delta }\mathbf{S}$ , but also the probabilities of other locations. However, the size of $\mathrm{\Delta }\mathbf{S}$ is seen as stable, since the change is almost 4 at overall timestamps. Second, we can see that the size of $\mathrm{\Delta }\mathbf{S}$ for PIM and GRR is quite close. This can explain the effect of parameter $\delta$ on size of $\mathrm{\Delta }\mathbf{S}$ for PIM and GRR is almost the same.

Distance over time with public and personal matrix is shown in Figures 4(d) and 5(d), respectively, from which we can figure out that GRR provides better utility than PIM. The distance between perturbed location and real location over time bounds within a few hundred meters.

In order to present the GRR perturbed trace under different parameter $\delta$ , we run a comparative experiment with $\delta =0.01$ and $\delta =0.005$ under the public matrix. The default value is $\epsilon =1$ . In Figure 6, we can see a higher value of $\delta$ will bring better utility. However, the value $\delta$ cannot be as high as possible. The detailed analysis is presented in the following parameter influence.

• 2. Parameters influence

Figure 6.

GRR perturbed trace with public matrix under different parameter $\delta$ : (a) $\delta =0.01$ and (b) $\delta =0.005.$

We further evaluate the overall performance and parameters influence. Each evaluation runs 10 times and the average is given. The performances are shown in Figure 7 (public matrix) and Figure 8 (personal matrix). The default parameters values are $\epsilon =1$ and $\delta =0.01$ , if not given.

1. $\epsilon$ versus size of $\mathrm{\Delta }\mathbf{S}$ and utility. We evaluate the relationship between $\epsilon$ and size of $\mathrm{\Delta }\mathbf{S}$ , as well as average distance by comparing PIM and GRR. Figure 7(a) and (b) as well as Figure 8(a) and (b) show changes in terms of size of $\mathrm{\Delta }\mathbf{S}$ and average distance with $\epsilon$ , respectively. Note that size of $\mathrm{\Delta }\mathbf{S}$ and the distance are average on the overall trace. Figures 7(a) and 8(a) show size of $\mathrm{\Delta }\mathbf{S}$ shrinks as $\epsilon$ grows larger. Since the degree of privacy preservation is inversely proportional to $\epsilon$ , larger $\epsilon$ will further enhance inference result. Figures 7(b) and 8(b) show the distance changes with varying $\epsilon$ . We can figure out that GRR is better than PIM in terms of average distance (utility).

2. $\delta$ versus size of $\mathrm{\Delta }\mathbf{S}$ and utility. We evaluate the relationship between $\delta$ and size of $\mathrm{\Delta }\mathbf{S}$ , as well as average distance by comparing PIM and GRR. Figure 7(c) and (d) as well as Figure 8(c) and (d) show changes in terms of size of $\mathrm{\Delta }\mathbf{S}$ and average distance with $\epsilon$ , respectively. In general, size of $\mathrm{\Delta }\mathbf{S}$ is mainly determined by $\delta$ . We can figure out that PIM and GRR have similar size of $\mathrm{\Delta }\mathbf{S}$ , which indicates the real location is hidden in candidate location sets with approximate size. Figures 7(c) and 8(c) show the size of $\mathrm{\Delta }\mathbf{S}$ reduces with larger $\delta$ , so it is also inversely proportional to $\delta$ . The reason is that more impossible locations are filtered out. However, $\delta$ cannot be too large since the perturbed mechanism hardly protects privacy if size of $\mathrm{\Delta }\mathbf{S}$ is equal to 1. Hence, to guarantee trade-off of privacy and utility, we consider set $\delta =0.01$ so that the size of $\mathrm{\Delta }\mathbf{S}$ for PIM and GRR are larger than 2 and 4, respectively. Figures 7(d) and 8(d) show the distance changes with varying $\delta$ . We can figure out that GRR is better than PIM in terms of average distance (utility).

3. Different Markov model. Comparing Figure 7 on public matrix and Figure 8 on personal matrix, we can perceive the influence of different Markov model. GRR can achieve better utility than PIM in both public and personal model. And it can achieve better utility in personal model than in public model.

Figure 7.

Parameters influence under public matrix: (a) $\epsilon$ versus size, (b) $\epsilon$ versus average distance, (c) $\delta$ versus size, and (d) $\delta$ versus average distance.

Figure 8.

Parameters influence under personal matrix: (a) $\epsilon$ versus size, (b) $\epsilon$ versus average distance, (c) $\delta$ versus size, and (d) $\delta$ versus average distance.

Conclusion and future work

This article investigated locally differentially private continuous location sharing problem. Specifically, we proposed a novel definition $(\epsilon ,\delta )$ -LDP to capture the temporal correlations between locations, and presented a GRR mechanism to achieve the $(\epsilon ,\delta )$ -LDP and obtain the upper bound of error. We served the GRR to design a continuous private location sharing framework and conducted a set of experiments to demonstrate the GRR-based continuous location sharing framework is better than the PIM-based framework in the context of utility.

As future work directions, we will be interested in adopting LDP to general continuous data sharing and continuous location aggregation problems. In addition, we will investigate the influence on the proposed framework in other more advanced mobility model.