# Prophet: A Context-Aware Location Privacy-Preserving Scheme in Location Sharing Service

Authors: Jiaxing Qu; Guoyin Zhang; Zhou Fang
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

Location sharing service has become an indispensable part in mobile social networks. However, location sharing may introduce a new class of privacy threats ranging from localizing an individual to profiling and identifying him based on the places he shared. Although users may avoid releasing geocontent in sensitive locations, it does not necessarily prevent the adversary from inferring users’ privacy through space-temporal correlations and historical information. In this paper, we design a Prophet framework, which provides an effective security scheme for users sharing their location information. First, we define fingerprint identification based on Markov chain and state classification to describe the users’ behavior patterns. Then, we propose a novel location anonymization mechanism, which adopts aε-indistinguishability strategy to protect user’s sensitive location information published. Finally, experimental results are given to illustrate good performance and effectiveness of the proposed scheme.


---

## Body

## 1. Introduction

With the growing popularity of mobile devices (such as smartphones), millions of applications (or apps for short) with location-based services are available to users from app markets. Users release their location in order to experience personalized/customized services (such as friend-seeker and navigation service). However, location sharing may introduce a new class of privacy threats ranging from localizing an individual to profiling and identifying him based on the places he visits [1, 2] in mobile social networks.Traditionally,k-anonymity [3] is the most widely used in privacy protection. It aims at protecting the user’s identity, requiring that the attacker cannot infer the target user among other k-1 different users. In the scope of the location privacy protection, spatialk-anonymity requires that it is undistinguishable among k points of interest (POI) [4]. One way to achieve this is through the use of dummy locations [5–7]. This technique needs to generate k-1 dummy POIs and performk queries to the location-based service (LBS) server, using the real and k-1 dummy locations. Another way is cloaking [8, 9], which involves creating a region that includesk POIs and sending the cloaking region to the LBS server. However, such seemingly perfectk-anonymity-based methods almost need to establish some unreasonable assumptions. These methods typically assume an adversary that knows only some aspects of background knowledge and tries to prevent it from learning some other aspects. One can attack such privacy notions by changing either what the adversary already knows or what the adversary tries to learn. For example, dummy locations are feasible if and only if they look equally likely to be the real location from the view of the attacker. Any auxiliary information that allows to rule out any of those POIs, as having low probability of being the real location by some semantic properties, would immediately violate the privacy. Moreover, these existing methods mostly focus on “single shot” scenario, which fails to protect the privacy when applied to inference attack due to spatiotemporal correlations between the published geolocation contents.In this paper, we investigate the issue of when and where the user can release his/her geolocation information. The goal of our work is to let user enjoy location sharing service as much as possible while avoiding privacy risk. To this end, we present a context-aware location privacy-preserving scheme, called Prophet, where users’ history location information is used to create statistical fingerprints of behavior patterns. We call a fingerprint as a distinctive feature allowing identification of certain behavior patterns. In this work, a fingerprint corresponds to a first-order homogeneous Markov chain, which represents a sequence of POIs appearing in a single direction flow of user’s locations released. Based on this, Prophet is formalized as how to accurately and efficiently evaluate whether the users’ published location information meets the user’s privacy requirement. Furthermore, consider the real-life requirement that user use the location-based service. We propose a novel metricε-undistinguishable to tradeoff between the desired level of privacy and the usefulness of the service provided by the LBS server.We give formal security proof to the correctness and privacy guarantee of our mechanism. Furthermore, the extensive experiments demonstrate the validity and practicality of our scheme.In summary, the paper makes the following contributions:(1)
We first present a context-aware location privacy-preserving scheme, called Prophet, and based on this, we propose a series of novel technologies for accurately and efficiently evaluating the risk of privacy.(2)
We propose a novel metricε-undistinguishable to tradeoff between the desired level of privacy and the usefulness of the service provided by the LBS.(3)
We have implemented our scheme on our simulated testbed, and the extensive experiments demonstrate the validity and practicality of our scheme.The remainder of the paper is organized as follows. Section2 characterizes the system model and motivation and threat model briefly. In Section 3, we describe how to get behavior pattern fingerprints by Markov chain and state classification processes. Section 4 provides details on location anonymization mechanism, which is the key component in our scheme. Section 5 presents the experiment results confirming the effectiveness of the proposed mechanism based on the simulated testbed. Section 6 overviews related work, followed by the concluding remarks in Section 7.


## 2. Problem Definition

### 2.1. System Model

We begin by describing a high-level architecture for Prophet as illustrated in Figure1, which involves three types of entities: user, Prophet, and LBS.(i)
User. In the context of LBSs, the user usually has location-based requirements (such as friend-searching, and navigation); simultaneously, he/she is reluctant to access the location-based service that may disclose his/her religious affiliations or personal lifestyle.(ii)
Prophet. Prophet, as an honest middleware server, provides (1) warning service, analyzing and mining users’ behavior patterns from history location information released and, based on this, providing the early warning service when location sharing behavior of the user touches the red line of privacy, and (2) anonymity service, transforming the received user’s location information through a technique called cloaking that hides the actual location by an anonymous space region.(iii)
LBS. LBS is an honest-but-curious server in our context. On the one hand, it acts in an “honest” fashion and correctly follows the designated protocol specification. However, it is “curious” to deduce and analyze location information so as to learn users’ privacy.Figure 1
Architecture of allocating customer applications.In this framework, a user just sends his location to Prophet, while Prophet is just responsible for analyzing and anonymizing the location information sent by user without knowing the real query requirement. Similarly, when receiving the query with a certain anonymous space region, LBS provider just processes the user’s query without learning the related privacy information from the anonymous space region (ASR for short).


### 2.2. Motivation and Threat Model

State-of-the-art methods of location privacy protection focus on anonymizing sensitive location information. These methods usually assume that the privacy requirements of users are constant and isolated. However, it is not a solid reason in the real-life location-based service scenario. For example, Bob, suffering from chronic bacterial prostatitis, is convalescing in a certain urology hospital, and he does not want anyone to know he has been to the hospital. To this end, he never checks in at this hospital. However, he may be happy to share his location by MSN to meet his friends at nearby bars or cafes where he thought no location privacy would be divulged. However, when combining Bob’s check-ins and patterns of other users who have the similar behaviors, an adversary still can infer Bob’s privacy. As illustrated in Figure2, an adversary may learn that most other users follow path 3 to the hospital after leaving the bar or the cafe. During this period, even if Bob did not share any location information at hospital, the adversary can still infer that Bob probably suffers from a kind of urological disease.Figure 2
Architecture of allocating customer applications.


## 2.1. System Model

We begin by describing a high-level architecture for Prophet as illustrated in Figure1, which involves three types of entities: user, Prophet, and LBS.(i)
User. In the context of LBSs, the user usually has location-based requirements (such as friend-searching, and navigation); simultaneously, he/she is reluctant to access the location-based service that may disclose his/her religious affiliations or personal lifestyle.(ii)
Prophet. Prophet, as an honest middleware server, provides (1) warning service, analyzing and mining users’ behavior patterns from history location information released and, based on this, providing the early warning service when location sharing behavior of the user touches the red line of privacy, and (2) anonymity service, transforming the received user’s location information through a technique called cloaking that hides the actual location by an anonymous space region.(iii)
LBS. LBS is an honest-but-curious server in our context. On the one hand, it acts in an “honest” fashion and correctly follows the designated protocol specification. However, it is “curious” to deduce and analyze location information so as to learn users’ privacy.Figure 1
Architecture of allocating customer applications.In this framework, a user just sends his location to Prophet, while Prophet is just responsible for analyzing and anonymizing the location information sent by user without knowing the real query requirement. Similarly, when receiving the query with a certain anonymous space region, LBS provider just processes the user’s query without learning the related privacy information from the anonymous space region (ASR for short).


## 2.2. Motivation and Threat Model

State-of-the-art methods of location privacy protection focus on anonymizing sensitive location information. These methods usually assume that the privacy requirements of users are constant and isolated. However, it is not a solid reason in the real-life location-based service scenario. For example, Bob, suffering from chronic bacterial prostatitis, is convalescing in a certain urology hospital, and he does not want anyone to know he has been to the hospital. To this end, he never checks in at this hospital. However, he may be happy to share his location by MSN to meet his friends at nearby bars or cafes where he thought no location privacy would be divulged. However, when combining Bob’s check-ins and patterns of other users who have the similar behaviors, an adversary still can infer Bob’s privacy. As illustrated in Figure2, an adversary may learn that most other users follow path 3 to the hospital after leaving the bar or the cafe. During this period, even if Bob did not share any location information at hospital, the adversary can still infer that Bob probably suffers from a kind of urological disease.Figure 2
Architecture of allocating customer applications.


## 3. Behavior Pattern Fingerprints

### 3.1. Fingerprint Identification Based on Markov Chain

In this subsection, we propose a method based on first-order homogeneous Markov chain to model possible sequences of users’ behavior patterns. The benefits of using the first-order homogeneous Markov chain model are threefold: (1) it is effective enough; (2) it is simple for implementation; (3) it is easy to extend to any higher-order Markov chain model [10, 11]. We consider discrete-time random variable Rt as a first-order Markov chain for any t=t0,t1,…,tn∈T. It takes values Vt∈1,…,m, where Vt is a decimal code of a certain POI (e.g., 9 for the store).AsRt is a first-order Markov chain, we have(1)PRt=Vt∣Rt-1=Vt-1,Rt-2=Vt-2,…,R1=V1=PRt=Vt∣Rt-1=Vt-1.Moreover, we further assume that the first-order Markov chain is homogeneous; that is, a state transition from timet-1 to time t is time-invariant, as shown below:(2)PRt=Vt∣Rt-1=Vt-1=PRt=j∣Rt-1=i=pij,with the transition matrix(3)P=p11p12p21p22⋯p1m⋯p1m⋮⋮Pm1Pm2⋱⋮⋯pmm,where∑j=1mpij=1. We denote the Input Probability Distribution (IPD) by(4)Q=q1,q2,…,qm,where qi=P (Rt=i) at time t0, and we define(5)W=w1,w2,…,wm,as the Output Probability Distribution (OPD), wherewi denotes the probability that the location share operation (at one cycle, such as one day) finishes when it is in state i at time tn. Note that IPD and OPD are independent in the Markov chain, which represent the probabilities to enter and leave the Markov chain. In traditional Markov chain models [11], there is an initial state and one or several ending states. In our case, IPD defines the probability to enter the state of the Markov chain, and OPD expresses the probability of aborting/leaving the Markov chain from the state set. According to these definitions, the resulting probability that a sequence of states R1,…,RT representing a behavior cycle occurs is as follows:(6)PR1,…,RT=qV1×∏t=2TpVt-1Vt×wVT.The resulting probability indicates how a given sequence of location information during a state transition chain is close to one user’s behavior pattern, where the larger value means that the behavior trace is closer to the model.To illustrate the process of the fingerprint creation, consider the examples in Figures3 and 4 of the behavior pattern sequences observed during behavior cycles in a training location information composed of only three users’ behavior traces in one cycle.Figure 3
An example of decimal codes for POIs and event type.Figure 4
An example of the fingerprint for users’ states.There are 7 different Markov states in the example, as shown in Figure3. The transition probability between states is derived from frequencies observed in the sequences, for example, P(9:101;5:104)→(13:110)=92.6%, P(10:105)→(13:110)=95.2%. The probabilities are the parameters of the Markov chain fingerprint for the example in Figure 4. Based on this model, we can find the probability that an observed user would appear in one place based on the behavior sequences.


### 3.2. State Classification

In this subsection, we describe the state classification technique, which is the preliminary work of the fingerprint identifying.The released location information is organized in the form of record, where each record contains the whole ordinal published geolocation contents of the corresponding user for one day. Such data is a kind of set-valued data which is sparse and high dimensional. The core idea is to find a set of states which can be used to classify into different clusters.To this end, we introduce a data structure, named concept [12]. Given a dataset with users shared location information D(U,A,F), where U=x1,…,xn, each xi (i≤n) is a shared information which records a user shared location-content sequence for one day; A=a1,…,am, each aj (j≤m) is a state; F:U×A→V∈0,1, the concept set is denoted by C(I,E,h,g), where I denotes the state set, called the intension of the concept; E is the corresponding records, called the extension of the concept; and h and g are a pair of dual operators, defined by, for I⊆A and E⊆U,(7)hE=a∈A∣x,a∈F∀x∈U,gI=x∈U∣x,a∈F∀a∈A.Specifically, whenI contains sensitive states AS (AS≠∅, AS⊆A), we called the corresponding concept as privacy concept CS; otherwise, the concept is called information concept CI.Based on this, we can see that the problem of identifying the core states can be reduced into the mapping relation from information conceptCI to CS. Specifically, we first partition dataset into several parts horizontally, according to the value difference of IS. Then, focusing on the extension set of CS(IS,ES) by the operation gIS, we need to find all information concepts CI with the intension set IS. Here, to prevent the dimension disaster caused by the sparse and high dimensional state set, we use two parameters (k, m) as the threshold of state aggregation, where k denotes the minimum support threshold of the states and m denotes the confidence threshold of the state aggregation, which requires that, focusing on a state aggregation, any m state as a whole meets the minimum support threshold.Lemma 1 (a priori property).
Given a conceptCI,E over D(U,A,F), where I≠∅ and E≥k, for any concept CiIi,Ei with Ii⊆I (Ii≠∅), we have Ei≥k.
There is a fact that if a conceptCiIi,Ei does not meet the support threshold k, all of the higher-dimensional concepts CI,E with I⊃Ii will not meet the support threshold as well. According to Lemma 1, generating the i-dimensional concept set Ci (i>1) just needs the previous concept set Ci-1. Specifically, given the threshold parameters (k, m), we generate all of i-dimensional concept set (i≤m) iteratively as follows:(1)
Generate candidate 1-dimensional concept set. Each state constitutes the intension of a candidate 1-dimensional concept. The algorithm scans all of the records in the target cluster, recording the corresponding extension and the size of the extension domain.(2)
GenerateC1. Based on the threshold k, the 1-dimensional concept set C1 can be determined. It consists of the candidate 1-dimensional concept set, where Ej of each concept Cj is equal to or greater than k.(3)
Generatei-dimensional concept set Ci (i>1) based on the concept set Ci-1. The algorithm first uses the join Ii-1⋈Ii-1 to generate a candidate i-dimensional intension set. Then, based on the a priori property (Lemma 1) that all subconcepts of a higher-dimensional concept satisfying the threshold also satisfy the support threshold, we can prune the candidate intension sets that do not satisfy the a priori property. For each of the rest candidate intension sets, we compute the intersection of extension sets corresponding to i-1-dimensional concepts. Then, the i-dimension concept set can be determined. It consists of the concepts, where qIi of Ci is equal to or greater than k.(4)
Jump to Step (3) untilCi=∅ or i=m.
We can see that, given the parameters (k, m), the issue of finding all information concepts CI with the intension set IS is transferred to the m rounds concept-generating.
Next, we say that one privacy conceptCS is a domain. By building the discernibility matrix [13] from the information concept set C1,…,Ci to CS, we can find the core state set.Definition 2 (discernibility matrix).
Given a domainCS(IS,ES) and the corresponding information concept set C1,…,Ci, the discernibility set(8)DSCIi,CIj=ak∈A∣EIi≠EIjISi∩ISj=∅∅ISi∩ISj≠∅.We say that DM=DSCIi,CIj∣IIi,IIj∈AI is the discernibility matrix.
Based on Definition2, we can find the core state set Ac as shown in(9)Ac=⋂DSCIi,CIj∈DMDSCIi,CIj.


## 3.1. Fingerprint Identification Based on Markov Chain

In this subsection, we propose a method based on first-order homogeneous Markov chain to model possible sequences of users’ behavior patterns. The benefits of using the first-order homogeneous Markov chain model are threefold: (1) it is effective enough; (2) it is simple for implementation; (3) it is easy to extend to any higher-order Markov chain model [10, 11]. We consider discrete-time random variable Rt as a first-order Markov chain for any t=t0,t1,…,tn∈T. It takes values Vt∈1,…,m, where Vt is a decimal code of a certain POI (e.g., 9 for the store).AsRt is a first-order Markov chain, we have(1)PRt=Vt∣Rt-1=Vt-1,Rt-2=Vt-2,…,R1=V1=PRt=Vt∣Rt-1=Vt-1.Moreover, we further assume that the first-order Markov chain is homogeneous; that is, a state transition from timet-1 to time t is time-invariant, as shown below:(2)PRt=Vt∣Rt-1=Vt-1=PRt=j∣Rt-1=i=pij,with the transition matrix(3)P=p11p12p21p22⋯p1m⋯p1m⋮⋮Pm1Pm2⋱⋮⋯pmm,where∑j=1mpij=1. We denote the Input Probability Distribution (IPD) by(4)Q=q1,q2,…,qm,where qi=P (Rt=i) at time t0, and we define(5)W=w1,w2,…,wm,as the Output Probability Distribution (OPD), wherewi denotes the probability that the location share operation (at one cycle, such as one day) finishes when it is in state i at time tn. Note that IPD and OPD are independent in the Markov chain, which represent the probabilities to enter and leave the Markov chain. In traditional Markov chain models [11], there is an initial state and one or several ending states. In our case, IPD defines the probability to enter the state of the Markov chain, and OPD expresses the probability of aborting/leaving the Markov chain from the state set. According to these definitions, the resulting probability that a sequence of states R1,…,RT representing a behavior cycle occurs is as follows:(6)PR1,…,RT=qV1×∏t=2TpVt-1Vt×wVT.The resulting probability indicates how a given sequence of location information during a state transition chain is close to one user’s behavior pattern, where the larger value means that the behavior trace is closer to the model.To illustrate the process of the fingerprint creation, consider the examples in Figures3 and 4 of the behavior pattern sequences observed during behavior cycles in a training location information composed of only three users’ behavior traces in one cycle.Figure 3
An example of decimal codes for POIs and event type.Figure 4
An example of the fingerprint for users’ states.There are 7 different Markov states in the example, as shown in Figure3. The transition probability between states is derived from frequencies observed in the sequences, for example, P(9:101;5:104)→(13:110)=92.6%, P(10:105)→(13:110)=95.2%. The probabilities are the parameters of the Markov chain fingerprint for the example in Figure 4. Based on this model, we can find the probability that an observed user would appear in one place based on the behavior sequences.


## 3.2. State Classification

In this subsection, we describe the state classification technique, which is the preliminary work of the fingerprint identifying.The released location information is organized in the form of record, where each record contains the whole ordinal published geolocation contents of the corresponding user for one day. Such data is a kind of set-valued data which is sparse and high dimensional. The core idea is to find a set of states which can be used to classify into different clusters.To this end, we introduce a data structure, named concept [12]. Given a dataset with users shared location information D(U,A,F), where U=x1,…,xn, each xi (i≤n) is a shared information which records a user shared location-content sequence for one day; A=a1,…,am, each aj (j≤m) is a state; F:U×A→V∈0,1, the concept set is denoted by C(I,E,h,g), where I denotes the state set, called the intension of the concept; E is the corresponding records, called the extension of the concept; and h and g are a pair of dual operators, defined by, for I⊆A and E⊆U,(7)hE=a∈A∣x,a∈F∀x∈U,gI=x∈U∣x,a∈F∀a∈A.Specifically, whenI contains sensitive states AS (AS≠∅, AS⊆A), we called the corresponding concept as privacy concept CS; otherwise, the concept is called information concept CI.Based on this, we can see that the problem of identifying the core states can be reduced into the mapping relation from information conceptCI to CS. Specifically, we first partition dataset into several parts horizontally, according to the value difference of IS. Then, focusing on the extension set of CS(IS,ES) by the operation gIS, we need to find all information concepts CI with the intension set IS. Here, to prevent the dimension disaster caused by the sparse and high dimensional state set, we use two parameters (k, m) as the threshold of state aggregation, where k denotes the minimum support threshold of the states and m denotes the confidence threshold of the state aggregation, which requires that, focusing on a state aggregation, any m state as a whole meets the minimum support threshold.Lemma 1 (a priori property).
Given a conceptCI,E over D(U,A,F), where I≠∅ and E≥k, for any concept CiIi,Ei with Ii⊆I (Ii≠∅), we have Ei≥k.
There is a fact that if a conceptCiIi,Ei does not meet the support threshold k, all of the higher-dimensional concepts CI,E with I⊃Ii will not meet the support threshold as well. According to Lemma 1, generating the i-dimensional concept set Ci (i>1) just needs the previous concept set Ci-1. Specifically, given the threshold parameters (k, m), we generate all of i-dimensional concept set (i≤m) iteratively as follows:(1)
Generate candidate 1-dimensional concept set. Each state constitutes the intension of a candidate 1-dimensional concept. The algorithm scans all of the records in the target cluster, recording the corresponding extension and the size of the extension domain.(2)
GenerateC1. Based on the threshold k, the 1-dimensional concept set C1 can be determined. It consists of the candidate 1-dimensional concept set, where Ej of each concept Cj is equal to or greater than k.(3)
Generatei-dimensional concept set Ci (i>1) based on the concept set Ci-1. The algorithm first uses the join Ii-1⋈Ii-1 to generate a candidate i-dimensional intension set. Then, based on the a priori property (Lemma 1) that all subconcepts of a higher-dimensional concept satisfying the threshold also satisfy the support threshold, we can prune the candidate intension sets that do not satisfy the a priori property. For each of the rest candidate intension sets, we compute the intersection of extension sets corresponding to i-1-dimensional concepts. Then, the i-dimension concept set can be determined. It consists of the concepts, where qIi of Ci is equal to or greater than k.(4)
Jump to Step (3) untilCi=∅ or i=m.
We can see that, given the parameters (k, m), the issue of finding all information concepts CI with the intension set IS is transferred to the m rounds concept-generating.
Next, we say that one privacy conceptCS is a domain. By building the discernibility matrix [13] from the information concept set C1,…,Ci to CS, we can find the core state set.Definition 2 (discernibility matrix).
Given a domainCS(IS,ES) and the corresponding information concept set C1,…,Ci, the discernibility set(8)DSCIi,CIj=ak∈A∣EIi≠EIjISi∩ISj=∅∅ISi∩ISj≠∅.We say that DM=DSCIi,CIj∣IIi,IIj∈AI is the discernibility matrix.
Based on Definition2, we can find the core state set Ac as shown in(9)Ac=⋂DSCIi,CIj∈DMDSCIi,CIj.


## 4. Location Anonymization Mechanism

To protect user’s location privacy from LBS provider, the Prophet would generate an anonymous space region that contains several POIs located next to the user’s exact location. Normally, in the perspective of the information publisher, the bigger the ASR is, the higher the accuracy loss of the released information is. Unfortunately, this rule is not always true: an adversary can fast narrow it down by eliminating fallacious POIs. Here, we propose a novelε-undistinguishable anonymity mechanism to solve this issue, which contains two stages: preprocessing and region-anonymizing.


### 4.1. Preprocessing

To quantitatively customize the ASR, in this stage, we need to location POIs. de Berg et al. [14] adopt the Voronoi diagram to divide the space into a set of Voronoi cells (Vcells), where each POI is assigned to a Vcell. However, it gives rise to the following problems: (a) due to the irregular ASR generated by Voronoi rule, it is difficult to be transformed by the coordinate representation. Moreover, the size of each subregion is inhomogeneous, which makes it difficult to quantitatively assess the mapping relation on the basis of generating the ASR between users’ distribution and the distribution of the POIs; (b) Because the number of subregions partitioned by the Voronoi rule is equal to the number of POIs, the target region could not be subdivided. To this end, on top of the Voronoi diagram, we use Hilbert space-filling curve, which superimposes a regular N×N grid where each grid cell (Gcell) stores information about the Vcells intersecting it. The information recorded in each Gcell Gij can be viewed as a tuple (X, H), where X is POIs contained in this Gcell and H is an index set that records such Gcells: (a) when X=∅, H records the Hilbert number of such Gcells that contain POIs in the Vcells intersecting of the target Gcell Gij; (b) X≠∅, H records all Hilbert numbers in the Vcells covering X. For example, Figure 5 shows a 4×4 grid, where G12 containing x2 stores x2,H1,H3,H4,H5,H6,H8 and G13 intersected by V2, V3 stores ∅,H4,H10, and so on.Figure 5
Computing the Voronoi diagram for the POIs.


### 4.2. Region-Anonymizing

k-anonymity is one of the most popular security metrics, which makes each published record undistinguishable from at least k-1 other records. However, in the context of LBS, k-anonymity is not so nice as it seems. Kalnis et al. [8] show a set of attacks against space k-anonymity. In this subsection, we define a novel privacy metrics ε-indistinguishability, which expresses a user’s privacy requirement and information availability, simultaneously.In the view of privacy protection, the covered POIs (containing the selectedk-1 POIs and the target POI) in ASR should be undistinguishable in the probability. Here, we assume that the adversary has held some auxiliary information S (the target user’s previous tracks). Consider two POIs x and x′; we say x and x′ are ε-undistinguishableiff(10)PxPx′=Px∣SPx′∣S=eεε>0.Intuitively, since two locationsx and x′ produce a reported value in S with similar transition probabilities, S reveals little information about whether the actual location is x or x′.In the view of information availability, it is obvious that the information availability of the released location relevant content is distance-dependent. That is, given an information loss levell, it is proportional to the radius r of the ASR, more formally:(11)lr=ε′rr≫ε′>0,where the parameter ε′ can be thought as the level of information loss at one unit of distance. This definition requires that the user is protected within any radius r, but with a level l that increases with the distance.Combining (10) and (11), we get the final definition of ε-undistinguishable.Definition 3 (ε-indistinguishability).
Assuming that the adversary has held some auxiliary informationS (the target user’s previous tracks), we say a mechanism satisfies ε-undistinguishableiff for any two POIs x and x′(12)Px∣SPx′∣S=eε/rr≫ε>0,dx,x′≤r.
Based on Definition3, we can see that (1) when ε→0, the strength of privacy protection is also strengthened gradually; (2) when r reduces gradually, information loss is also reduced but the strength of privacy protection is affected; and (3) by adjusting the parameters ε and r, the issue of building ASR which can make a tradeoff between privacy and information availability can be transformed into the following optimization problem:(13)Maximizemaxxi∈ASR⁡Pxi∣Sminxj∈ASR⁡Pxj∣S+λ1Oxmax-Oxmin×Oymax-Oyminsubjectto∑xi∈ASR1≥k,maxxi∈ASR⁡Pxi∣Sminxj∈ASR⁡Pxj∣S≤eε,(14)Oxmax-Oxmin×Oymax-Oymin≤4r2,where (Oxmax-Oxmin)×(Oymax-Oymin) are the area of the ASR and λ is a nonnegative weight.
Obviously, this is a NP-complete problem which can be reduced into the 0-1 knapsack. Therefore, we propose a heuristic algorithm, as follows.Algorithm 4.
Before describing the details of the proposed algorithm, we first introduce its core idea. When receiving the location sharing requirement, Prophet first checks user’s behavior fingerprint. If the shared location belongs to “the core state set” and the probability of inferring sensitive/privacy location based on the computation of the transition matrix is greater than the preset threshold, Prophet would issue an alarm to the user. After getting the response from the user, Prophet builds the corresponding ASR satisfying the privacy requirement and information availability. The heuristic rule of building the ASR is shown in Algorithm1: Step (1): locating the Hilbert number of the shared location, the algorithm traverses space regions alone of the Hilbert space-filling curve until finding k-1 neighboring POIs. And then it computes the corresponding privacy strength and the area of the ASR. If user’s requirements are satisfied, the algorithm terminates; otherwise, three conditions are discussed. Step (2) (Condition 1: privacy strength is lower than the threshold): eliminating the POIs (xi and xj) whose P(xi∣S)/P(xj∣S)>eε, it finds the median of the Hilbert number among the rest of POIs, and based on the median, it adds two different neighboring POIs which is similar to Step (1). Step (3) (Condition 2: the area of ASR is greater than the threshold): eliminating two POIs (the one having the biggest abscissa value and the one having the biggest ordinate value), it finds the median of the Hilbert number among the rest POIs, and based on the median, it adds two different neighboring POIs which is similar to Step (1). Step (4): it iteratively performs Steps (2) and (3) until satisfying user’s requirement or aborting due to being unable to find a convergence of the solution space.Algorithm 1:Building the ASR.
INPUT:k,ε // anonymity parameters
r // information availability parameters
qloc // user’s exact location
T // the Hilbert threaded regions
OUTPUT:ASR // anonymous space region
BuildASR(m,k,e,qloc,T)
(1)qx=qloc;
// Step (1)
(2)Loc=qx;
(3)num=Hilbert (qloc);
(4)do
(5)   num++;
(6)Loc=Loc∪Hilbert-1(num);
(7)while  Loc≥k;
(8)for  i=1; i++; i≤Loc  do
(9)for  j=i+1; j++; i≤Loc  do
(10)Eij=P(qi∣S)P(qj∣S);
(11)for each  Eij in E  do // Step (2)
(12)  ifEij>eε then
(13)   record the correspond POIsqi and qj into Q;
(14) delete POIs ofQ from Loc;
(15)num=Hilbert (median(Loc));
(16) jump to Step (1);
// Step (3)
(17) find the pointsOtop-left, Obottom-right from E;
(18) compute the area of ASR (Otop-left, Obottom-right);
(19)if  ASR>4r2  then
(20)  delete POIs corresponding withOtop-left, Obottom-right;
(21)num=Hilbert (median(Loc));
(22) jump to Step (1);
(23) return ASR;


### 4.3. Security Analysis

Due to introducing Prophet as a trusted third party (TTP for short), there is no collusion attack from Prophet and LBS server. Based on right decentralization mechanism, LBS server cannot accurately infer the sensitive location hided by user. Furthermore, against inference attack, Prophet adopts two-stage privacy protection strategy: Markov chain-based reverse inference mechanism (Section3) and location anonymization mechanism (Section 4). The strategy proposed in Section 3 can estimate the probability that the adversary infers user based on the published check-in chains. Based on this, the strategy proposed in Section 4 further anonymizes user’s location before publishing. Based on the proposed region-anonymizing mechanism, the adversary cannot infer more privacy information than the published one. Integrating the proposed two anonymous strategies, we are able to assess the probability that the adversary infers the sensitive location hidden by user. Assume that adversary has known the check-in chain containing m regions (k POIs for each region); the final inference probability P is as follows:(15)P=∏i=1m-1pi→i+1×ki→i+1×αi→i+1,where pi→i+1 denotes the inference probability that the target user checks in from POI i to POI i+1; ki→i+1 denotes the number of POIs contained in the ith region; αi→i+1 is the attenuation ration; and α decreases along with the check-in chain.


## 4.1. Preprocessing

To quantitatively customize the ASR, in this stage, we need to location POIs. de Berg et al. [14] adopt the Voronoi diagram to divide the space into a set of Voronoi cells (Vcells), where each POI is assigned to a Vcell. However, it gives rise to the following problems: (a) due to the irregular ASR generated by Voronoi rule, it is difficult to be transformed by the coordinate representation. Moreover, the size of each subregion is inhomogeneous, which makes it difficult to quantitatively assess the mapping relation on the basis of generating the ASR between users’ distribution and the distribution of the POIs; (b) Because the number of subregions partitioned by the Voronoi rule is equal to the number of POIs, the target region could not be subdivided. To this end, on top of the Voronoi diagram, we use Hilbert space-filling curve, which superimposes a regular N×N grid where each grid cell (Gcell) stores information about the Vcells intersecting it. The information recorded in each Gcell Gij can be viewed as a tuple (X, H), where X is POIs contained in this Gcell and H is an index set that records such Gcells: (a) when X=∅, H records the Hilbert number of such Gcells that contain POIs in the Vcells intersecting of the target Gcell Gij; (b) X≠∅, H records all Hilbert numbers in the Vcells covering X. For example, Figure 5 shows a 4×4 grid, where G12 containing x2 stores x2,H1,H3,H4,H5,H6,H8 and G13 intersected by V2, V3 stores ∅,H4,H10, and so on.Figure 5
Computing the Voronoi diagram for the POIs.


## 4.2. Region-Anonymizing

k-anonymity is one of the most popular security metrics, which makes each published record undistinguishable from at least k-1 other records. However, in the context of LBS, k-anonymity is not so nice as it seems. Kalnis et al. [8] show a set of attacks against space k-anonymity. In this subsection, we define a novel privacy metrics ε-indistinguishability, which expresses a user’s privacy requirement and information availability, simultaneously.In the view of privacy protection, the covered POIs (containing the selectedk-1 POIs and the target POI) in ASR should be undistinguishable in the probability. Here, we assume that the adversary has held some auxiliary information S (the target user’s previous tracks). Consider two POIs x and x′; we say x and x′ are ε-undistinguishableiff(10)PxPx′=Px∣SPx′∣S=eεε>0.Intuitively, since two locationsx and x′ produce a reported value in S with similar transition probabilities, S reveals little information about whether the actual location is x or x′.In the view of information availability, it is obvious that the information availability of the released location relevant content is distance-dependent. That is, given an information loss levell, it is proportional to the radius r of the ASR, more formally:(11)lr=ε′rr≫ε′>0,where the parameter ε′ can be thought as the level of information loss at one unit of distance. This definition requires that the user is protected within any radius r, but with a level l that increases with the distance.Combining (10) and (11), we get the final definition of ε-undistinguishable.Definition 3 (ε-indistinguishability).
Assuming that the adversary has held some auxiliary informationS (the target user’s previous tracks), we say a mechanism satisfies ε-undistinguishableiff for any two POIs x and x′(12)Px∣SPx′∣S=eε/rr≫ε>0,dx,x′≤r.
Based on Definition3, we can see that (1) when ε→0, the strength of privacy protection is also strengthened gradually; (2) when r reduces gradually, information loss is also reduced but the strength of privacy protection is affected; and (3) by adjusting the parameters ε and r, the issue of building ASR which can make a tradeoff between privacy and information availability can be transformed into the following optimization problem:(13)Maximizemaxxi∈ASR⁡Pxi∣Sminxj∈ASR⁡Pxj∣S+λ1Oxmax-Oxmin×Oymax-Oyminsubjectto∑xi∈ASR1≥k,maxxi∈ASR⁡Pxi∣Sminxj∈ASR⁡Pxj∣S≤eε,(14)Oxmax-Oxmin×Oymax-Oymin≤4r2,where (Oxmax-Oxmin)×(Oymax-Oymin) are the area of the ASR and λ is a nonnegative weight.
Obviously, this is a NP-complete problem which can be reduced into the 0-1 knapsack. Therefore, we propose a heuristic algorithm, as follows.Algorithm 4.
Before describing the details of the proposed algorithm, we first introduce its core idea. When receiving the location sharing requirement, Prophet first checks user’s behavior fingerprint. If the shared location belongs to “the core state set” and the probability of inferring sensitive/privacy location based on the computation of the transition matrix is greater than the preset threshold, Prophet would issue an alarm to the user. After getting the response from the user, Prophet builds the corresponding ASR satisfying the privacy requirement and information availability. The heuristic rule of building the ASR is shown in Algorithm1: Step (1): locating the Hilbert number of the shared location, the algorithm traverses space regions alone of the Hilbert space-filling curve until finding k-1 neighboring POIs. And then it computes the corresponding privacy strength and the area of the ASR. If user’s requirements are satisfied, the algorithm terminates; otherwise, three conditions are discussed. Step (2) (Condition 1: privacy strength is lower than the threshold): eliminating the POIs (xi and xj) whose P(xi∣S)/P(xj∣S)>eε, it finds the median of the Hilbert number among the rest of POIs, and based on the median, it adds two different neighboring POIs which is similar to Step (1). Step (3) (Condition 2: the area of ASR is greater than the threshold): eliminating two POIs (the one having the biggest abscissa value and the one having the biggest ordinate value), it finds the median of the Hilbert number among the rest POIs, and based on the median, it adds two different neighboring POIs which is similar to Step (1). Step (4): it iteratively performs Steps (2) and (3) until satisfying user’s requirement or aborting due to being unable to find a convergence of the solution space.Algorithm 1:Building the ASR.
INPUT:k,ε // anonymity parameters
r // information availability parameters
qloc // user’s exact location
T // the Hilbert threaded regions
OUTPUT:ASR // anonymous space region
BuildASR(m,k,e,qloc,T)
(1)qx=qloc;
// Step (1)
(2)Loc=qx;
(3)num=Hilbert (qloc);
(4)do
(5)   num++;
(6)Loc=Loc∪Hilbert-1(num);
(7)while  Loc≥k;
(8)for  i=1; i++; i≤Loc  do
(9)for  j=i+1; j++; i≤Loc  do
(10)Eij=P(qi∣S)P(qj∣S);
(11)for each  Eij in E  do // Step (2)
(12)  ifEij>eε then
(13)   record the correspond POIsqi and qj into Q;
(14) delete POIs ofQ from Loc;
(15)num=Hilbert (median(Loc));
(16) jump to Step (1);
// Step (3)
(17) find the pointsOtop-left, Obottom-right from E;
(18) compute the area of ASR (Otop-left, Obottom-right);
(19)if  ASR>4r2  then
(20)  delete POIs corresponding withOtop-left, Obottom-right;
(21)num=Hilbert (median(Loc));
(22) jump to Step (1);
(23) return ASR;


## 4.3. Security Analysis

Due to introducing Prophet as a trusted third party (TTP for short), there is no collusion attack from Prophet and LBS server. Based on right decentralization mechanism, LBS server cannot accurately infer the sensitive location hided by user. Furthermore, against inference attack, Prophet adopts two-stage privacy protection strategy: Markov chain-based reverse inference mechanism (Section3) and location anonymization mechanism (Section 4). The strategy proposed in Section 3 can estimate the probability that the adversary infers user based on the published check-in chains. Based on this, the strategy proposed in Section 4 further anonymizes user’s location before publishing. Based on the proposed region-anonymizing mechanism, the adversary cannot infer more privacy information than the published one. Integrating the proposed two anonymous strategies, we are able to assess the probability that the adversary infers the sensitive location hidden by user. Assume that adversary has known the check-in chain containing m regions (k POIs for each region); the final inference probability P is as follows:(15)P=∏i=1m-1pi→i+1×ki→i+1×αi→i+1,where pi→i+1 denotes the inference probability that the target user checks in from POI i to POI i+1; ki→i+1 denotes the number of POIs contained in the ith region; αi→i+1 is the attenuation ration; and α decreases along with the check-in chain.


## 5. Evaluation and Experiment

We now evaluate some performance results of our scheme using real-world dataset, Foursquare, made available by Gao et al. [15]. It contains the check-in history of 18107 users ranging from March 2010 to January 2011. Our simulated testbed is implemented on a workstation with 2 Intel Xeon E3 core processors running at Intel 2.13 GHz CPUs, 32 GB dual-channel 1333 GHz memory for Prophet server and LBS provider server, respectively. We report the performance and effectiveness of the proposed anonymity algorithm, respectively. The implementation for the proposed algorithms uses Python.


### 5.1. Building Transition Matrix

As mentioned above, transition matrix is the core preliminary work of proposed location anonymization scheme. Hence the overhead in building transition matrix phase directly affects the whole scheme. Now, we begin by estimating the cost in terms of building transition matrix. Suppose that the number of users varies from 100 to 2,000, in steps of 100, in the following experiment. Under this setting, we quantify the cost introduced by the building transition matrix in terms of fingerprint identification as well as state classification, as shown in Figure6.Figure 6
The overhead of building transition matrix.The experimental results in Figure6 show the overhead in building transition matrix with varying numbers of users. For comparison, we include a direct scheme of building transition matrix as a baseline, which does not contain the step of state classification. We also can see that the overhead of building transition matrix in state classification phase increases, as the number of users increases compared with the direct scheme.Specifically, there are only 60.12 seconds in building transition matrix phase for 2000 users. This experimental results demonstrate the effectiveness of proposed state classification phase by concept data structure. In other words, this overhead is acceptable, even for very large number of users. This result demonstrates the basic usability of our scheme for fingerprint identification calculating phase.


### 5.2. Building ASR

As discussed in Section4, the overhead of building ASR is closely related to parameters r and ε. Hence, we evaluate this effectiveness through multigroup experiments. Then the next group of experiments illustrate the performance of the proposed anonymity scheme from the following phases, where k is 3, 5, 7, 9, and 11.Figure7 shows the execution timings of building ASR as r=1 km. Obviously, the overhead of building ASR grows slowly on different ε value. With the increasing of ε, the overhead of building ASR increases gradually. This result confirms the effectiveness of our behavior pattern fingerprints recognition scheme, which is the core preliminary work for the proposed region-anonymizing scheme.Figure 7
The overhead of building ASR on differentε.On the other side, Figure8 shows the overhead of building ASR experimental results where ε=0.1. Obviously, it takes much more time to build ASR with r increasing. For example, it only takes 1030.4ms to construct ASR by Prophet, where k=11 km and r=3 km. The main reason of low computation overhead in ASR building phase is that the preprocessing process normalizes the pattern fingerprints for each user and performs excellently for classification.Figure 8
The overhead of building ASR on differentr.In short, the overhead of building ASR does not introduce much more negative impact on the whole scheme by differentr and ε. That is because the preprocessing phase mainly focuses on minimizing the computation overhead in building ASR process. Hence, the proposed location anonymization mechanism releases Prophet from heavy computational overhead in building ASR phase, which satisfies real-world situations.


### 5.3. Effectiveness

Next, we focus on evaluating the performance of our privacy-preserving scheme during the preprocessing and anonymizing procedure. As discussed in Section4, the proposed location anonymization scheme is a heuristic algorithm. That is, the constructed ASR may not be the optimal one in theory. Therefore, we calculate the average error of our scheme compared to theoretical value through 100 simulated experiments.Figure9 plots the average error of our proposed scheme on different ε values. As it can be seen, the higher average error is only 8.33% where k=11 and ε=0.3. One important reason of this result is that our proposed region-anonymizing heuristic algorithm can find the optimal value effectively. Compared to the theoretical value, the high accuracy of the proposed scheme can be proved directly. Figure 10 shows the average error of our proposed scheme on different r values; similar to the above experiment, the average error is not very high (about 7%), which also satisfies the real-world situations.Figure 9
The average error of Prophet on differentε.Figure 10
The average error of Prophet on differentr.


### 5.4. Performance

As previously mentioned, the real sensitive locations are usually hidden by users in our datasets Foursquare. In order to evaluate the location indistinguishability among Prophet, CLPP [16], and DP [17], we selected two sensitive locations in our next experiment as illustrated in [16]. Two hidden locations sets, HL1 and HL2, are generated by randomly marking off a portion of POIs and adding POIs which are geographically located between the POIs, respectively.There are two metrics designed to evaluate the accuracy among Prophet, DP, and CLPP: (1) average confidence of hidden location set HL1, denoted as true positive, and (2) average confidence of hidden location set HL2, denoted as false positive [16]. In detail, we select 1,000 users and choose l1 and l2 in each user’s check-in history records. We randomly mark off 1,2,3,…,10 POIs between l1 and l2 as HL1 and add 5, 10, 15, 20, 25, and 30 un-checked-in POIs between l1 and l2 as HL2.The experimental results shown in Figures11 and 12 demonstrate that Prophet has better performance than CLPP and DP in terms of true positive probability and false positive probability under all experimental values. This is because some users’ check-in historical data are always personal and unusual, which makes it difficult for CLPP and DP to evaluate whether the user has visited the hidden locations within large amounts of users’ historical check-in historical data in Foursquare. It is important to note that the higher the true positive probability in Figure 11 is, the better the scheme is, while false positive probability in Figure 12 shows the opposite. Those results further denote that our proposed region-anonymizing strategy performs quite well as discussed in Section 4.3. Meanwhile, we can conclude that the increasing number of marked-off or added POIs does not seriously affect the true confidence or false confidence of Prophet.Figure 11
Performance evaluation on true positive probability.Figure 12
Performance evaluation on false positive probability.


## 5.1. Building Transition Matrix

As mentioned above, transition matrix is the core preliminary work of proposed location anonymization scheme. Hence the overhead in building transition matrix phase directly affects the whole scheme. Now, we begin by estimating the cost in terms of building transition matrix. Suppose that the number of users varies from 100 to 2,000, in steps of 100, in the following experiment. Under this setting, we quantify the cost introduced by the building transition matrix in terms of fingerprint identification as well as state classification, as shown in Figure6.Figure 6
The overhead of building transition matrix.The experimental results in Figure6 show the overhead in building transition matrix with varying numbers of users. For comparison, we include a direct scheme of building transition matrix as a baseline, which does not contain the step of state classification. We also can see that the overhead of building transition matrix in state classification phase increases, as the number of users increases compared with the direct scheme.Specifically, there are only 60.12 seconds in building transition matrix phase for 2000 users. This experimental results demonstrate the effectiveness of proposed state classification phase by concept data structure. In other words, this overhead is acceptable, even for very large number of users. This result demonstrates the basic usability of our scheme for fingerprint identification calculating phase.


## 5.2. Building ASR

As discussed in Section4, the overhead of building ASR is closely related to parameters r and ε. Hence, we evaluate this effectiveness through multigroup experiments. Then the next group of experiments illustrate the performance of the proposed anonymity scheme from the following phases, where k is 3, 5, 7, 9, and 11.Figure7 shows the execution timings of building ASR as r=1 km. Obviously, the overhead of building ASR grows slowly on different ε value. With the increasing of ε, the overhead of building ASR increases gradually. This result confirms the effectiveness of our behavior pattern fingerprints recognition scheme, which is the core preliminary work for the proposed region-anonymizing scheme.Figure 7
The overhead of building ASR on differentε.On the other side, Figure8 shows the overhead of building ASR experimental results where ε=0.1. Obviously, it takes much more time to build ASR with r increasing. For example, it only takes 1030.4ms to construct ASR by Prophet, where k=11 km and r=3 km. The main reason of low computation overhead in ASR building phase is that the preprocessing process normalizes the pattern fingerprints for each user and performs excellently for classification.Figure 8
The overhead of building ASR on differentr.In short, the overhead of building ASR does not introduce much more negative impact on the whole scheme by differentr and ε. That is because the preprocessing phase mainly focuses on minimizing the computation overhead in building ASR process. Hence, the proposed location anonymization mechanism releases Prophet from heavy computational overhead in building ASR phase, which satisfies real-world situations.


## 5.3. Effectiveness

Next, we focus on evaluating the performance of our privacy-preserving scheme during the preprocessing and anonymizing procedure. As discussed in Section4, the proposed location anonymization scheme is a heuristic algorithm. That is, the constructed ASR may not be the optimal one in theory. Therefore, we calculate the average error of our scheme compared to theoretical value through 100 simulated experiments.Figure9 plots the average error of our proposed scheme on different ε values. As it can be seen, the higher average error is only 8.33% where k=11 and ε=0.3. One important reason of this result is that our proposed region-anonymizing heuristic algorithm can find the optimal value effectively. Compared to the theoretical value, the high accuracy of the proposed scheme can be proved directly. Figure 10 shows the average error of our proposed scheme on different r values; similar to the above experiment, the average error is not very high (about 7%), which also satisfies the real-world situations.Figure 9
The average error of Prophet on differentε.Figure 10
The average error of Prophet on differentr.


## 5.4. Performance

As previously mentioned, the real sensitive locations are usually hidden by users in our datasets Foursquare. In order to evaluate the location indistinguishability among Prophet, CLPP [16], and DP [17], we selected two sensitive locations in our next experiment as illustrated in [16]. Two hidden locations sets, HL1 and HL2, are generated by randomly marking off a portion of POIs and adding POIs which are geographically located between the POIs, respectively.There are two metrics designed to evaluate the accuracy among Prophet, DP, and CLPP: (1) average confidence of hidden location set HL1, denoted as true positive, and (2) average confidence of hidden location set HL2, denoted as false positive [16]. In detail, we select 1,000 users and choose l1 and l2 in each user’s check-in history records. We randomly mark off 1,2,3,…,10 POIs between l1 and l2 as HL1 and add 5, 10, 15, 20, 25, and 30 un-checked-in POIs between l1 and l2 as HL2.The experimental results shown in Figures11 and 12 demonstrate that Prophet has better performance than CLPP and DP in terms of true positive probability and false positive probability under all experimental values. This is because some users’ check-in historical data are always personal and unusual, which makes it difficult for CLPP and DP to evaluate whether the user has visited the hidden locations within large amounts of users’ historical check-in historical data in Foursquare. It is important to note that the higher the true positive probability in Figure 11 is, the better the scheme is, while false positive probability in Figure 12 shows the opposite. Those results further denote that our proposed region-anonymizing strategy performs quite well as discussed in Section 4.3. Meanwhile, we can conclude that the increasing number of marked-off or added POIs does not seriously affect the true confidence or false confidence of Prophet.Figure 11
Performance evaluation on true positive probability.Figure 12
Performance evaluation on false positive probability.


## 6. Related Work

Privacy-preserving has attached much more attentions in mobile social networks research field areas. Most of current privacy-preserving schemes which focus on sensitive data sharing issues are dependent on anonymization techniques [16–19] or cryptographic algorithm [20]. CLPP is used to evaluate whether the users’ published location information meets their privacy requirement in location-based social network through traditional mining algorithm [16]. However, CLPP is not sufficient to ensure user’s location privacy due the weak classifier of mining algorithm compared to our proposed Prophet. To address data sparsity problem, DP strategy selects a minimum number of locations a user has to hide on the trajectory by subtrajectory synthesis algorithm in order to avoid privacy leakage risk [17]. But unlike CLPP and DP, in our work, ε-indistinguishability strategy based on fingerprint identification is a novel aspect of this work. Bilogrevic et al. [19] propose a privacy-preserving method for mobile devices to the server based scheduling problem which takes full use of the homomorphic properties of asymmetric cryptosystems to calculate common user availabilities in order to meet user’s personalized privacy requirements. Different from traditional privacy-preserving research in cloud environment, several researches focus on methodologies for the implementation of context-aware environment in mobile cloud. Lin et al. [18] provided a reliable recommendation and privacy-preserving based cross-layer reputation mechanism (RP-CRM) to provide secure and privacy-aware communication process in mobile cloud environment. Chen et al. [21] discussed how to use local trust value, which is calculated based on user call behavioral attributes in order to protect user’s sensitive behavior patterns of mobile cloud user. Those works focus on privacy-preserving research on DaaS (Data as a Service) and privacy-aware communication in cloud. Biswas and Vidyasankar [20] resort to integrating transactional and cryptographic primitive scheme to realize privacy-preserving of sensitive data against untrusted cloud servers. Reference [22] used a range of applications of Virtual Individual Servers (VIS) proxies to protect mobile device privacy. However, different from traditional method, [23] provides oblivious transfer and private information retrieval interaction scheme to achieve an efficient and practical location-based privacy-preserving problems based on queries.Some research works focus on the privacy-preserving of healthcare information in mobile health monitoring environment [24, 25]. Cloud-assisted mobile health (mHealth) monitoring is a revolutionary way to improve the quality of healthcare service. However, this situation poses a serious risk on both clients’ privacy and intellectual property. Cloud-assisted mHealth monitoring system (CAM) [24] which relies on the anonymous Boneh-Franklin identity-based encryption (IBE) in medical diagnostic programs. SPOC [25] is a secure and privacy-preserving opportunistic computing framework which is based on attribute-based access control and a new privacy-preserving scalar product computation (PPSPC) technique to protect the users’ personal health information (PHI) security.The study of location-based anonymize scheme has gained the great interest from the research community recently, and we briefly review some of them related to our work [26–31]. In [26], users’ location is encrypted when shared in mobile social applications and can be only decrypted by the data owner. In [27], the credential information is updated on the basis of mobile cloud packets exchange, protecting against credential faking or stealing attacks. MobiShare [28] is a location privacy framework in mobile online social networks by separating user identities and anonymized location updates. Secure mobile user-based data service mechanism (SDSM) [29] provided confidentiality access control for data stored in the cloud by identity-based proxy reencryption scheme. FINE [30] employed a ciphertext-policy anonymous attribute-based encryption technique to achieve location privacy for mobile devices. FindU [31] which is a set of privacy-preserving distributed profile matching schemes in mobile social networks resorts to Shamir secret sharing as the main secure computing technique. Although these schemes solve location anonymizing problem in mobile cloud, they do not emphasize how to transfer the workload of the involved parties to the cloud without violating the privacy of involved parties. Since our scheme scenario contains preprocessing phase, it is helpful to release heavy computational load on Prophet in behavior pattern fingerprints phase.


## 7. Conclusion

In this paper, we design a context-aware location privacy-preserving scheme in mobile cloud environment, named Prophet, which is an effective security scheme for mobile cloud users to protect the mobile user’s sharing locations. Moreover, we propose a novel location anonymization mechanism, which adopts aε-indistinguishability strategy to protect user’s sensitive location information published. In addition, through extensive performance evaluation, we have also demonstrated that Prophet can balance the privacy requirement and acceptable information availability.



---

*Source: 6814832-2017-05-08.xml*