# Towards Region Queries with Strong Location Privacy in Mobile Network

Authors: Songtao Yang; Qingfeng Jiang
Journal: Mobile Information Systems
 (2021)

---

## Abstract

With the interaction of geographic data and social data, the inference attack has been mounting up, calling for new technologies for privacy protection. Although there are many tangible contributions of spatial-temporal cloaking technologies, traditional technologies are not enough to resist privacy intrusion. Malicious attackers still steal user-sensitive information by analyzing the relationship between location and query semantics. Reacting to many interesting issues, oblivious transfer (OT) protocols are introduced to guarantee location privacy. To our knowledge, OT is a cryptographic primitive between two parties and can be used as a building block for any arbitrary multiparty computation protocol. Armed with previous privacy-preserving technologies, for example, OT, in this work, we first develop a novel region queries framework that can provide robust privacy for location-dependent queries. We then design an OT-assist privacy-aware protocol (or OTPA) for location-based service with rigorous security analysis. In short, the common query of the client in our solution can be divided into two parts, the region queryRq and the content query Cq, to achieve location k-anonymity, location m-diversity, and query r-diversity, which ensure the privacy of two parties (i.e., client and server). Lastly, we instantiate our OTPA protocol, and experiments show that the proposed OTPA protocol is reasonable and effective.


---

## Body

## 1. Introduction

Location-based services (LBS) are one of the successful mobile applications in our daily life. Armed with the help of LBS, it will be easy for you whether you want to let others track your movements, find or get to somewhere, or simply know your current location and what is around you. Obliviously, LBS along with its corresponding applications greatly improve the public living style in terms of richness and diversity. However, problems of location privacy disclosure have not raised the concern of the public. For instance, some malicious attackers will track the trace of the location using the LBS. Attackers can monitor and identify goal-oriented people, but the goal-oriented people could not be aware of being tracked [1, 2]. In this case, researchers were beginning to engage in how to conceal location and identity of users.In reality, the user can submit the points of interest (POIs) queries (e.g., “find the nearest mall”) to the LBS provider like Google Map. To conceal location and identity, users could mask the query via an anonymity tool, such ask-anonymity and obfuscation. But the attacker can deduce the user’s identity from the content of query, background knowledge, and the observation information if we just adopt a simple pseudonym to cloak the location and the identity [3]. To overcome these limitations, these proposed research schemes can be divided into three major types: (a) location k-anonymity, (b) location obfuscation, and (c) private information retrieval (PIR). However, these existing techniques cannot efficiently address the following two major problems in more detail: (a) most of the existing proposals assume that all anonymous participants are completely reliable. In contrast, the participants stay at the same level of security. Apparently, this assumption is unrealistic and inconsistent. It is often questionable with the actual scenario. Collaborator may be disclosing the accurate location information or the accurate queries information, either directly or indirectly. (b) In fact, intermediary servers or query issuers obtain a large amount of redundant data during per-query. However, these data are employed in charging customers according to actual use, whether directly or indirectly, and they are valuable assets of the LBS server.Consider an application scenario shown in Figure1. Alice wants to get a discount list of this mall located in a certain area or obtain what movie will be released in the nearby cinema. Although there are a lot of POIs around her, she is only concerned with a certain category of these POIs information. For example, she issues a service request, “find the discount price of the mall which is away from my current location about 5 km”, to trade with the LBS provider. According to LBS service mode, the NN of Alice is P6, where the set P1, P3, P4, P6, P8 represents some malls.Figure 1
Application scenario of LBS.To our knowledge, previous schemes are not conducive to the embodiment of the commercial value of the LBS information. Hence, we will ask the following question: is it possible to address the two above-mentioned problems using OT-assist privacy-aware protocol? To answer this question, in this paper, we first develop a novel region query framework that supports the private location-dependent query. We then design an OT-assist privacy-aware protocol (or OTPA) for location-based service with rigorous security analysis.The contributions can be summarized as follows:(1)
A novel region queries framework: We first developed a novel region queries framework that supports private location-dependent queries. Our framework achieves noncooperative privacy preserving via cryptographic techniques, and it does not require a trusted third party. We proposed a new fair exchanging pattern with semitrusted three parties, which includes an intersection with three subjects: users, location cloaking server, and LBS server. Assume that all the participants are semihonest in this architecture; they will honestly follow the protocol but they are curious to find out as much as information from the data that it receives and stores.(2)
An OT-assist privacy-aware protocol: We designed a privacy-aware query protocol, which guarantees the untraceability of user trajectory and unlinkability of the content. A common query is split into a region query and a content query in our solution. Further, we analyzed the user’s privacy through theory analysis and demonstrated the effectiveness by experiments.


### 1.1. Roadmap

The rest of this paper is organized as follows. We reviewed the related work in Section2. In Section 3, we presented some definitions and gave some terms. In Section 4, we introduced the region queries and designed a system model and expression. The proposed privacy-aware region queries and OTPA protocol are presented in Section 5, followed by the security analysis in Section 6 and the experiment evaluation in Section 7. Finally, we concluded the paper in Section 8.


## 1.1. Roadmap

The rest of this paper is organized as follows. We reviewed the related work in Section2. In Section 3, we presented some definitions and gave some terms. In Section 4, we introduced the region queries and designed a system model and expression. The proposed privacy-aware region queries and OTPA protocol are presented in Section 5, followed by the security analysis in Section 6 and the experiment evaluation in Section 7. Finally, we concluded the paper in Section 8.


## 2. Related Works

In numerous studies, the locationk-anonymity [4–6] is always the predominant approach. The essence of location k-anonymity is that the probability of identifying the query user cannot exceed 1/k, which is mainly focused on query privacy. Instead of sending the query to the LBS server, the user interacts with the anonymizer, which cuts off the association between user’s identities and query contents to prevent the attacker from analyzing the user’s sensitive information. However, k is not a representative of the actual location privacy of mobile users. In fact, these cloaking techniques based on the location k-anonymity metric could even be counterproductive and give the illusion of a higher location privacy level. Shokri et al. argued that the k-anonymity scheme is insufficient for protecting location privacy [7]. For example, if k users within an anonymous spatial region (ASR) are located in the same semantic location, the ASR guarantees the requester’s query privacy but discloses their location privacy. On the other hand, if k users have similar query content and distribute in different locations, the ASR guarantees users location privacy and exposes the user’s query privacy. Therefore, some researchers develop further studies for location diversity and context-aware and location semantics [8]. A complementary technique to the location k-anonymity is the location obfuscation technique. These location obfuscation techniques are achieved by deliberately reducing the resolution of the user’s location to protect user privacy, namely, using a cloaking region instead of the user’s actual location. To release ambiguous location is often used as a simple and effective technique [9–11]. Space Twist framework avoids the high computational cost and communication cost caused by the ASR. However, a lower resolution of location may cause coarse-grained service provided by the LBS server. The size of cloaking region is proportional to degree of privacy and is inversely proportional to the quality of service. Therefore, the adversary can deduce the approximate location of the user according to the context of background environment, which means leading weak privacy [12]. Collusion of LBS leads to complexity of privacy preserving in real-world applications. The correlation between geographic data and social data leads to losing effectiveness for spatial-temporal anonymity technology. As a cryptography-based oblivious transfer method, private information retrieval (PIR) was also adopted to secure the location privacy [13, 14]. OT and PIR are similar: cryptographic protection against information disclosure. The methods which employed PIR protocol or OT protocol provide provable privacy guarantees against correlation attacks and eliminate the requirement for any trusted third party. Computational PIR-based approach utilizes a PIR protocol to implement a simple query pattern, which retrieves a specific database block from the LBS server without discovering which block is retrieved. However, it leads to a prohibitive computational cost and communication cost even for a small POIs databases. Therefore, secure hard-ware-aided PIR proven efficient is currently considered as a practical mechanism for PIR. Some cryptographic technologies (such as attribute based encryption [15–17] and data integrity checking [18–20]) have potential application in location privacy, which not only guarantees secure data share but also ensures remote data integrity [21].


## 3. Preliminaries

In this section, we present some definitions for follow-up work, including the framework, privacy-aware protocol, and privacy-aware queries in LBS.Definition 1.
(P). A point of interest (POIs) is a landmark or specific location that someone may feel useful or be interested in, such as a hotel, hospital, and school. It can be formalized into a triple set: P=l,c,i. Here, we denote the i−th POIs as Pi, where, Pil is location coordinates of a Pi, Pic is category of a Pi, Pii is service content of a Pi.Definition 2.
(Rq). Region query can be formalized as follows: Rq=R,k,m. Here, R represents a geographic region illustrated by the query submitter. The k is the user-desired degree of anonymity. m is the user-desired number of different semantic locations within R.Definition 3.
(Cq). Content query can be formalized as follows: Cq=R′,C′. Here, R′ represents the minimum area meeting users’ privacy. C′ is a subset of C. It is selected by the user. C is a comprehensive POIs taxonomy set.Definition 4.
(Hli). Given an anonymous spatial region, a set of m location points L=l1,…,lm. For any location in an anonymous spatial region, the Location Entropy is denoted as Hli=−∑i=1mpililog2pili. Here, pili is the probability of user ui locating in li.Definition 5.
(Hqi). Given an anonymous set, a set of n users U=u1,…,un. For any use in an anonymous set, the Query Entropy is denoted as Hqi=−∑i=1mpiqilog2piqi. Here, piqi is the probability of user ui issuing query qi.Definition 6.
(POIIR). The POIIR is the abbreviation of “POIs influence range.” LetP=p1,…,pn indicate a set of POIs that possess identical datatype in the LBS database. Thus,(1)POIIRpi=p|distp,pi≤distp,pj,i≠j,where p is an arbitrary point in the service range.
For ease of description, we define some terminology about location privacy. The definition of notations in our work is shown in Table1.Table 1
Notations.
SymbolDescriptionlUser locationRQuery region presented by userR′A minimum cloaking region selected by MCkThe degree ofk-anonymitymLocationm-diversityrQueryr-diversityCThe set of POIs categoryC′A subset of CSnCandidate setPrCoordinate set of POIs picked by userMiService information of POIsKiEncryption key


## 4. Region Queries Framework

### 4.1. Region Queries

We map the experimental area onto a gridG composed of cells. Each cell corresponds to a Hilbert value, covers an α×α square area, where α indicates the parameter that defines the cell size of the grid G. Users regularly upload location information to a location cloaking server. The current cell of a user contains the current position of the moving object.In our solutions, the objective forRq is to find some Minimum Cloak Regions (MCRs). All these MCRs meet the requirement of user privacy. Similar to the Hilbert Cloak, given a query from the mobile client (MC) with anonymity requirement k, Location Cloaking Server (LCS) ranks the Hilbert Values and splits them into k-buckets. The LCS calculates the start and end positions defining the k-bucket that includes requester and constructs k-ASR using all users in the same bucket. The difference is that our solutions meet the requirements of the location m-diversity, while building k-ASR for each user.For example, as shown in Figure2, suppose u2 issues the query “Rq=0,0,7,7,4,3.” We can easily calculate that one of k-ASR is 0,0,3,3. Moreover, k-ASR offered by LCS is not unique, which may be 0,5,5,7. What it is designed to do is to be against inference attacks of LCS. The MC chooses a correct k-ASR that contains its real coordinates as the basis for the Cq.Figure 2
Hilbert curve map for a 2D space with8×8 space partition.


### 4.2. System Model and Expression

In a LBS system, a large number of mobile users move within a two-dimensional square unit space. Users can issue location-dependent queries, answered by LBS providers. We adopt the three-tier centralized architecture consisting of three key parts: mobile user, location cloaking server, and LBS server.Mobile clients (MC) are equipped with a positioning device, for example, GPS or sensor-based local positioning systems, to determine its current location informationl. All of the users who held MC in our model enjoy location-dependent service by the LBS server. This device is trusted, and no malicious software component running on the mobile device has access to the location sensor. That can be assured by using a trusted computational approach.LBS servers (LBSS) are the service providers of the LBS system. These LBSS are nontrusted since an attacker is aware of all the information that users provided to the LBS server and compromise user privacy. In addition, we assume that the attacker has statistical background information about the users, although in practice, it is difficult to model the exact knowledge.Location cloaking servers (LCS) are also the semitrusted party placed between MC and LBSS. All registered mobile users periodically update their location information to the LCS. These LCS construct MCRs, which meets users’ requirements of locationk-anonymity and location m-diversity.Users establish a secure connection (e.g., an SSL) with LCS, hiding the query issuer’s identity and IP address. As a hypothesis for our model, we further consider that the anonymity algorithm used by LCS is public. We support that the distribution of the population in the geographical space is uneven to conform with laws of nature.The general procedure of continuous region query processing and specification processing is shown in Figure3.(1)
A user sends a queryRq that contains the user’s privacy requirement to LCS(2)
LCS executes MCRs Finding Algorithm to form MCRs and initiatesCq to LBSS(3)
LBSS retrieve the spatial database and interact with LCS(4)
LCS minifies the candidate set before sending the results to the userFigure 3
The system model that contains three entities: MC, LCS, and LBSS.


### 4.3. MCRs Finding Algorithm

The LCS executes MCRs Finding Algorithm to calculate MCRs. We use the notationG=g1,…gn to denote Hilbert curve space; gi1≤i≤n is some of the cells. P represents the criterion of judgment and Pgi=TRUE means that gi only consists of a cell. The MCRs Finding Algorithm consists of three phases.Firstly, as shown in Figure4, region segmentation starts from a set of seed points. An alternative is to start with a single region (RqR) and subdivide the regions that do not satisfy a condition of Pgi. In other words, split into four disjoint quadrants any region Pgi for which Pgi=FALSE. Secondly, region merging is the opposite of region splitting. It starts with small regions and merges the regions that have similar characteristics. The aim of merging any adjacent region gj and gk is to find MCRs. Thirdly, we adopt an R-tree to index G. The process of constructing a G is iterative. The processing is repeated until all of MCRs satisfying privacy requirements (Rqk and Rqm) are found. The LCS randomly selects some of MCRs and sends them to the MC.Figure 4
An example of MCRs Finding Algorithm. (a) Splitted region. (b) R-tree.
(a)(b)


## 4.1. Region Queries

We map the experimental area onto a gridG composed of cells. Each cell corresponds to a Hilbert value, covers an α×α square area, where α indicates the parameter that defines the cell size of the grid G. Users regularly upload location information to a location cloaking server. The current cell of a user contains the current position of the moving object.In our solutions, the objective forRq is to find some Minimum Cloak Regions (MCRs). All these MCRs meet the requirement of user privacy. Similar to the Hilbert Cloak, given a query from the mobile client (MC) with anonymity requirement k, Location Cloaking Server (LCS) ranks the Hilbert Values and splits them into k-buckets. The LCS calculates the start and end positions defining the k-bucket that includes requester and constructs k-ASR using all users in the same bucket. The difference is that our solutions meet the requirements of the location m-diversity, while building k-ASR for each user.For example, as shown in Figure2, suppose u2 issues the query “Rq=0,0,7,7,4,3.” We can easily calculate that one of k-ASR is 0,0,3,3. Moreover, k-ASR offered by LCS is not unique, which may be 0,5,5,7. What it is designed to do is to be against inference attacks of LCS. The MC chooses a correct k-ASR that contains its real coordinates as the basis for the Cq.Figure 2
Hilbert curve map for a 2D space with8×8 space partition.


## 4.2. System Model and Expression

In a LBS system, a large number of mobile users move within a two-dimensional square unit space. Users can issue location-dependent queries, answered by LBS providers. We adopt the three-tier centralized architecture consisting of three key parts: mobile user, location cloaking server, and LBS server.Mobile clients (MC) are equipped with a positioning device, for example, GPS or sensor-based local positioning systems, to determine its current location informationl. All of the users who held MC in our model enjoy location-dependent service by the LBS server. This device is trusted, and no malicious software component running on the mobile device has access to the location sensor. That can be assured by using a trusted computational approach.LBS servers (LBSS) are the service providers of the LBS system. These LBSS are nontrusted since an attacker is aware of all the information that users provided to the LBS server and compromise user privacy. In addition, we assume that the attacker has statistical background information about the users, although in practice, it is difficult to model the exact knowledge.Location cloaking servers (LCS) are also the semitrusted party placed between MC and LBSS. All registered mobile users periodically update their location information to the LCS. These LCS construct MCRs, which meets users’ requirements of locationk-anonymity and location m-diversity.Users establish a secure connection (e.g., an SSL) with LCS, hiding the query issuer’s identity and IP address. As a hypothesis for our model, we further consider that the anonymity algorithm used by LCS is public. We support that the distribution of the population in the geographical space is uneven to conform with laws of nature.The general procedure of continuous region query processing and specification processing is shown in Figure3.(1)
A user sends a queryRq that contains the user’s privacy requirement to LCS(2)
LCS executes MCRs Finding Algorithm to form MCRs and initiatesCq to LBSS(3)
LBSS retrieve the spatial database and interact with LCS(4)
LCS minifies the candidate set before sending the results to the userFigure 3
The system model that contains three entities: MC, LCS, and LBSS.


## 4.3. MCRs Finding Algorithm

The LCS executes MCRs Finding Algorithm to calculate MCRs. We use the notationG=g1,…gn to denote Hilbert curve space; gi1≤i≤n is some of the cells. P represents the criterion of judgment and Pgi=TRUE means that gi only consists of a cell. The MCRs Finding Algorithm consists of three phases.Firstly, as shown in Figure4, region segmentation starts from a set of seed points. An alternative is to start with a single region (RqR) and subdivide the regions that do not satisfy a condition of Pgi. In other words, split into four disjoint quadrants any region Pgi for which Pgi=FALSE. Secondly, region merging is the opposite of region splitting. It starts with small regions and merges the regions that have similar characteristics. The aim of merging any adjacent region gj and gk is to find MCRs. Thirdly, we adopt an R-tree to index G. The process of constructing a G is iterative. The processing is repeated until all of MCRs satisfying privacy requirements (Rqk and Rqm) are found. The LCS randomly selects some of MCRs and sends them to the MC.Figure 4
An example of MCRs Finding Algorithm. (a) Splitted region. (b) R-tree.
(a)(b)


## 5. Privacy-Aware Region Queries

### 5.1. Motivation

Our framework focuses on continuous region query that is distinct from previous studies of single-point topk-nearest-neighbor query. Consider an application scenario shown in Figure 5; the same icons represent that these POIs belong to the same classification; and A, B, and C represent different mobile users, respectively.Figure 5
An example of a realistic road network environment.The common region queries are classified into three categories: (1) A uses its location as the center of region queries; (2) B uses one certain POI as the center of region queries, but B is not in the particular area; and (3) C uses one certain POI as the center of region queries, but C is in the particular area. Suppose that a user named Alice is moving in a bidimensional road network.The above description faces two problems. Firstly, users desire to experience both high-quality service and not to expose location and identity. Therefore, users are more concerned about privacy issues. Secondly, the LBSS do not want to publish more information about POIs, which means the LBSS also express concern about the quality of service issues and business profits. From the privacy perspective, both LBSS and MC are attackers. In addition, the IP address issue is orthogonal to our problem. It can be achieved through a widely available anonymous web browsing service.


### 5.2. OT-Assist Privacy-Aware Protocol

Oblivious transfer protocol normally runs as a building block for more complex secure protocols or as a stand-alone protocol for privacy-preserving in LBS. Efficient 1-out-of-r oblivious transfer schemes (OTr1) rely on the hardness of the decisional Diffie–Hellman problem to achieve unconditional security. Assume an order-q group Gq with a short description, where q is a large prime number. Let g and h be two generators of Gq. Parameters g, h, q, Gq are publicly accessed by every entity in our protocol, where senders and receivers refer to MC and LBSS, respectively. LBSS have r keys K1,…Kr. The MC knows one of the key Ka1≤a≤r is his/her own choice and does not want LBSS to have that data. Meanwhile, the LBSS only provide Ka for the MC but do not want MC to get more information. The implementation process of OT-assist privacy-aware protocol is shown as follows:(1)
MC choosesa1≤a≤r, generates a random number d, calculates y=gdhamodq, and sends y to LBSS.(2)
LBSS calculate two tuples of sequenceD and send D to MC. Here, D=s1,t1,…,sr,tr, si=gkimodq, ti=Kiy/hikimodq, ki∈Zq1≤i≤r.(3)
LBSS sendD to MC.(4)
MC calculatesKa=ta/sadmodq.The purpose of the OTPA protocol is to obtain one and only one key from LBSS. This scheme meets the following privacy requirements. For anya, there is d that satisfies y=gdhamodq. Therefore, LBSS cannot get any information related to a, even if it has unlimited computing power. When MC and LBSS gradually follow the protocol, although MC receives LBSS’s secrets K1,…Kr and cannot get two secrets, there is no way of getting information other than Ka.


### 5.3. Bidirectional Security Processing

Assume that the LBSS haver POIs information P=p1,…,pr and randomly generate the r key K=k1,…,kr. Query senders desire pa, but they do not wish the LBSS to know what they will get. Moreover, the LBSS also employ ka to prevent users from accessing unauthorized content. We define this query process as bidirectional security processing. We implement our solutions with secure multiparty computation theories. It is reasonable to make an assumption about which the LCS does not collude with the LBSS since the LCS stores query examples of the MC. Otherwise, it will completely subvert any method for location privacy preserving if the LCS is allowed to collude with LBSS. We consider that all the participants in a query session are semihonest. The MC and the LCS try to obtain more data than authorized. The LBSS tries to associate a user with a location or some POIs. More details of bidirectional security processing are depicted as follows, as shown in Figure 6:(1)
The MC submits a region queryRq to the LCS to find some MCRs.(2)
The LCS responds to the request of the user according to the privacy requirements of the user, executes MCRs Finding Algorithm, and sends some of MCRs to the MC.(3)
The MC randomly selects MCRs asCqR′ and submits a content query Cq to the LBSS for obtaining POIs candidate set Sn. CqC′ contains actual POIs category (ci) about this query.(4)
The LBSS calculate all candidate POIs ofCqR′’ and send candidate set Sn to MC. Sn is formulated as the following form:(2)Sn=pil|pil⊂CqR′andpic∈CqC′.Further, we can also expressSn as Sn=S1,…,Sr, where Sj1≤j≤r is a location set retrieved by cj.(5)
MC calculates the obstacle distance between its current coordinate and each element ofSi and adds the nearest point to the set Pr. MC randomly also extracts an element from Sj1≤j≤r,i≠j and adds it to the set Pr. The MC disrupts the order of Pr and sends it to the LBSS.(6)
The LBSS retrieve the spatial database and find all of POIs information in terms ofPr. It is referred to as M.(7)
The MC and the LBSS perform OTPA protocol.(8)
The LBSS can encryptM=EK1p1,…,EKrpr to prevent LCS from reading it and send it back to the LCS.(9)
The MC retrieves a particular record forEKapa, which is precisely what the user needs.Figure 6
The interactions between MC, LCS, and LBSS.


## 5.1. Motivation

Our framework focuses on continuous region query that is distinct from previous studies of single-point topk-nearest-neighbor query. Consider an application scenario shown in Figure 5; the same icons represent that these POIs belong to the same classification; and A, B, and C represent different mobile users, respectively.Figure 5
An example of a realistic road network environment.The common region queries are classified into three categories: (1) A uses its location as the center of region queries; (2) B uses one certain POI as the center of region queries, but B is not in the particular area; and (3) C uses one certain POI as the center of region queries, but C is in the particular area. Suppose that a user named Alice is moving in a bidimensional road network.The above description faces two problems. Firstly, users desire to experience both high-quality service and not to expose location and identity. Therefore, users are more concerned about privacy issues. Secondly, the LBSS do not want to publish more information about POIs, which means the LBSS also express concern about the quality of service issues and business profits. From the privacy perspective, both LBSS and MC are attackers. In addition, the IP address issue is orthogonal to our problem. It can be achieved through a widely available anonymous web browsing service.


## 5.2. OT-Assist Privacy-Aware Protocol

Oblivious transfer protocol normally runs as a building block for more complex secure protocols or as a stand-alone protocol for privacy-preserving in LBS. Efficient 1-out-of-r oblivious transfer schemes (OTr1) rely on the hardness of the decisional Diffie–Hellman problem to achieve unconditional security. Assume an order-q group Gq with a short description, where q is a large prime number. Let g and h be two generators of Gq. Parameters g, h, q, Gq are publicly accessed by every entity in our protocol, where senders and receivers refer to MC and LBSS, respectively. LBSS have r keys K1,…Kr. The MC knows one of the key Ka1≤a≤r is his/her own choice and does not want LBSS to have that data. Meanwhile, the LBSS only provide Ka for the MC but do not want MC to get more information. The implementation process of OT-assist privacy-aware protocol is shown as follows:(1)
MC choosesa1≤a≤r, generates a random number d, calculates y=gdhamodq, and sends y to LBSS.(2)
LBSS calculate two tuples of sequenceD and send D to MC. Here, D=s1,t1,…,sr,tr, si=gkimodq, ti=Kiy/hikimodq, ki∈Zq1≤i≤r.(3)
LBSS sendD to MC.(4)
MC calculatesKa=ta/sadmodq.The purpose of the OTPA protocol is to obtain one and only one key from LBSS. This scheme meets the following privacy requirements. For anya, there is d that satisfies y=gdhamodq. Therefore, LBSS cannot get any information related to a, even if it has unlimited computing power. When MC and LBSS gradually follow the protocol, although MC receives LBSS’s secrets K1,…Kr and cannot get two secrets, there is no way of getting information other than Ka.


## 5.3. Bidirectional Security Processing

Assume that the LBSS haver POIs information P=p1,…,pr and randomly generate the r key K=k1,…,kr. Query senders desire pa, but they do not wish the LBSS to know what they will get. Moreover, the LBSS also employ ka to prevent users from accessing unauthorized content. We define this query process as bidirectional security processing. We implement our solutions with secure multiparty computation theories. It is reasonable to make an assumption about which the LCS does not collude with the LBSS since the LCS stores query examples of the MC. Otherwise, it will completely subvert any method for location privacy preserving if the LCS is allowed to collude with LBSS. We consider that all the participants in a query session are semihonest. The MC and the LCS try to obtain more data than authorized. The LBSS tries to associate a user with a location or some POIs. More details of bidirectional security processing are depicted as follows, as shown in Figure 6:(1)
The MC submits a region queryRq to the LCS to find some MCRs.(2)
The LCS responds to the request of the user according to the privacy requirements of the user, executes MCRs Finding Algorithm, and sends some of MCRs to the MC.(3)
The MC randomly selects MCRs asCqR′ and submits a content query Cq to the LBSS for obtaining POIs candidate set Sn. CqC′ contains actual POIs category (ci) about this query.(4)
The LBSS calculate all candidate POIs ofCqR′’ and send candidate set Sn to MC. Sn is formulated as the following form:(2)Sn=pil|pil⊂CqR′andpic∈CqC′.Further, we can also expressSn as Sn=S1,…,Sr, where Sj1≤j≤r is a location set retrieved by cj.(5)
MC calculates the obstacle distance between its current coordinate and each element ofSi and adds the nearest point to the set Pr. MC randomly also extracts an element from Sj1≤j≤r,i≠j and adds it to the set Pr. The MC disrupts the order of Pr and sends it to the LBSS.(6)
The LBSS retrieve the spatial database and find all of POIs information in terms ofPr. It is referred to as M.(7)
The MC and the LBSS perform OTPA protocol.(8)
The LBSS can encryptM=EK1p1,…,EKrpr to prevent LCS from reading it and send it back to the LCS.(9)
The MC retrieves a particular record forEKapa, which is precisely what the user needs.Figure 6
The interactions between MC, LCS, and LBSS.


## 6. Security Analysis

Data security and user’s privacy have the absolute critical priority for a LBS system. There is much more risk of sensitive data being stolen or leaked because LBSS gather mass data from social media users. In this section, firstly, we explain the privacy threats caused by location and measurement of the privacy leakage. Moreover, we compare the proposed solution with existing works in terms of locationk-anonymity, location m-diversity, and query r-diversity.


### 6.1. Attack Expression and Privacy Metric

Location privacy is the nature of an individual to control access to their current and past location information. Figure7 shows the importance of location. There are four key factors affecting personal privacy in LBS system: identity, location, time stamp, and candidate POIs. As long as it is not associated with the particular user’s identity, query context does not lead to privacy disclosure. However, the user’s trajectory is the key link in query context and user’s identity. For example, continuous location samples have been tracked by attacks and then used to infer a user’s identity. The relationship feature between trajectory and POIs can also be used to define a user’s behavior. The combination of identity and behavior exposed the sensitive data of the user.Figure 7
Location is a key factor in the LBS system.All research related to location privacy stems from the assumption that untrusted LBS providers are the most critical threat to privacy. The LBS attacks involve two aspects: location tracing and user identification. Meanwhile, the prior knowledge of the attacker is unable to measure, and the invade mode taken by the attacker is unpredictable. As the diversity of profiles, such as user profile or user velocity, are not the same, the spatial cloaking faces continuous multiquery attacks, inference attacks, and correlation attacks.Theorem 1.
The combination of identity, location, timestamp, and candidate POIs poses a serious threat to user privacy, and location plays a significant role in the LBS system.
The concept of entropy was rooted in Shannon entropy. It gives an accurate metric of the uncertainty that an attacker infers for the user’s information. Shannon entropy also can be used to evaluate location privacy or query privacy. Before a user submits a query, the uncertainty over location obtained by LBSS has been called Priori Location Entropy. However, we can improve the degree of privacy using some techniques such as anonymity, fuzzy, and obfuscation. The uncertainty over location obtained by LBSS has been called Posterior Location Entropy after applying these techniques. The inherent feature of Location Entropy is mainly embodied in the following aspects. Firstly, when the LBSS have real-time location information of users, the Priori Location EntropyHli=0. Secondly, when the LBSS do not have any background knowledge, the maximum Priori Location Entropy Hli=log2m. Thirdly, when the LBSS have some background knowledge which is achieved through statistical analysis, the Priori Location Entropy 0<Hli<log2m.
We can easily recognize that higher entropy is associated with three things: locationk-anonymity degree, location m-diversity, and query r-diversity. In our solutions, the probabilities of location anonymity, location diversity, and query diversity are 1/k, 1/m, and 1/r, respectively. Users can freely control their privacy requirements because all of these parameters are determined by themselves. Therefore, our approaches achieved the purpose of hiding user privacy. Obviously, it is inevitable that each query provides some new knowledge for LBSS, which is more conducive to inferring the user’s sensitive data. However, our solutions improved the complexity of the invasion of privacy, although they do not overcome the inherent limitations of spatial and temporal cloaking methods. We will be establishing a privacy measure model in subsequent studies.


### 6.2. Comparison of OTPA, Spatial Cloaking, and PIR

Because it is required to submit ak-ASR to LBSS in spatial cloaking methods, the user issuing queries must be appearing in the area. The anonymous area has been gradually diminished by attackers according to user profiles, road network restrictions, and moving speed. Thus, the user’s trajectory is traceable. The quality of trajectory details relies heavily on the power of an attacker. At the same time, the candidate result set is a vital component for LBS providers to infer the user’s sensitive data. There is a direct correlation between queries content and user identity. An attacker can deduce who is most likely to issue the query. In our solutions, the region submitted to LBSS satisfies four properties: location k-anonymity, location m-diversity, query r-diversity, and reciprocal relationship of ASR. Therefore, our solutions can resist the inference attack for spatial cloaking. Firstly, the user submitting queries does not reveal the accurate location to LCS and LBSS since the calculation program of the nearest neighbor runs on the client device. However, LBSS can calculate the minimum inference region, which is the intersection of the R′ and all of disclosed POIs influence regions (POIIR). Consequently, larger value of R′ means higher location privacy for the user. The POIIR of disclosed POIs is discrete and random, which makes it difficult to trace the sequence of trajectories. Moreover, the user submitting queries confuses the query content with a plurality of POIs that are selected by themselves. Therefore, the probability of LBSS inference user query content is 1/r. Consequently, LBSS cannot associate the user with the identity by specific POIs.Theorem 2.
Assume that all of these attributes of locationk-anonymity, location l-diversity, query r-diversity, and reciprocal relationship of ASR can guarantee privacy, which makes our solution have the untraceability and the unlinkability.
OTPA is parallel to PIR. Both of them are based on encryption techniques to protect user privacy. Computational PIR relies on the quadratic residuosity problem. However, it cannot avoid a linear scan of the entire database for processing each query. The communication complexity of each query is roughlyn. The symbol n represents the size of the database. Therefore, the PIR techniques require extreme computational efficiency, where the usage of resources, such as run-time, storage, or data samples, is sublinear in the size of the candidate module. In contrast, OTPA does not have such requirements. Our solutions are superior to PIR techniques because the typical PIR framework does not limit the number of POIs obtained by the user. Thus, it does not provide an effective way to protect the valuable resources of LBS server.Theorem 3.
Assuming that the OTPA scheme is unconditionally secure, our solution achieves server-oriented security. It can be hard to maliciously get precious data of the LBS server.


## 6.1. Attack Expression and Privacy Metric

Location privacy is the nature of an individual to control access to their current and past location information. Figure7 shows the importance of location. There are four key factors affecting personal privacy in LBS system: identity, location, time stamp, and candidate POIs. As long as it is not associated with the particular user’s identity, query context does not lead to privacy disclosure. However, the user’s trajectory is the key link in query context and user’s identity. For example, continuous location samples have been tracked by attacks and then used to infer a user’s identity. The relationship feature between trajectory and POIs can also be used to define a user’s behavior. The combination of identity and behavior exposed the sensitive data of the user.Figure 7
Location is a key factor in the LBS system.All research related to location privacy stems from the assumption that untrusted LBS providers are the most critical threat to privacy. The LBS attacks involve two aspects: location tracing and user identification. Meanwhile, the prior knowledge of the attacker is unable to measure, and the invade mode taken by the attacker is unpredictable. As the diversity of profiles, such as user profile or user velocity, are not the same, the spatial cloaking faces continuous multiquery attacks, inference attacks, and correlation attacks.Theorem 1.
The combination of identity, location, timestamp, and candidate POIs poses a serious threat to user privacy, and location plays a significant role in the LBS system.
The concept of entropy was rooted in Shannon entropy. It gives an accurate metric of the uncertainty that an attacker infers for the user’s information. Shannon entropy also can be used to evaluate location privacy or query privacy. Before a user submits a query, the uncertainty over location obtained by LBSS has been called Priori Location Entropy. However, we can improve the degree of privacy using some techniques such as anonymity, fuzzy, and obfuscation. The uncertainty over location obtained by LBSS has been called Posterior Location Entropy after applying these techniques. The inherent feature of Location Entropy is mainly embodied in the following aspects. Firstly, when the LBSS have real-time location information of users, the Priori Location EntropyHli=0. Secondly, when the LBSS do not have any background knowledge, the maximum Priori Location Entropy Hli=log2m. Thirdly, when the LBSS have some background knowledge which is achieved through statistical analysis, the Priori Location Entropy 0<Hli<log2m.
We can easily recognize that higher entropy is associated with three things: locationk-anonymity degree, location m-diversity, and query r-diversity. In our solutions, the probabilities of location anonymity, location diversity, and query diversity are 1/k, 1/m, and 1/r, respectively. Users can freely control their privacy requirements because all of these parameters are determined by themselves. Therefore, our approaches achieved the purpose of hiding user privacy. Obviously, it is inevitable that each query provides some new knowledge for LBSS, which is more conducive to inferring the user’s sensitive data. However, our solutions improved the complexity of the invasion of privacy, although they do not overcome the inherent limitations of spatial and temporal cloaking methods. We will be establishing a privacy measure model in subsequent studies.


## 6.2. Comparison of OTPA, Spatial Cloaking, and PIR

Because it is required to submit ak-ASR to LBSS in spatial cloaking methods, the user issuing queries must be appearing in the area. The anonymous area has been gradually diminished by attackers according to user profiles, road network restrictions, and moving speed. Thus, the user’s trajectory is traceable. The quality of trajectory details relies heavily on the power of an attacker. At the same time, the candidate result set is a vital component for LBS providers to infer the user’s sensitive data. There is a direct correlation between queries content and user identity. An attacker can deduce who is most likely to issue the query. In our solutions, the region submitted to LBSS satisfies four properties: location k-anonymity, location m-diversity, query r-diversity, and reciprocal relationship of ASR. Therefore, our solutions can resist the inference attack for spatial cloaking. Firstly, the user submitting queries does not reveal the accurate location to LCS and LBSS since the calculation program of the nearest neighbor runs on the client device. However, LBSS can calculate the minimum inference region, which is the intersection of the R′ and all of disclosed POIs influence regions (POIIR). Consequently, larger value of R′ means higher location privacy for the user. The POIIR of disclosed POIs is discrete and random, which makes it difficult to trace the sequence of trajectories. Moreover, the user submitting queries confuses the query content with a plurality of POIs that are selected by themselves. Therefore, the probability of LBSS inference user query content is 1/r. Consequently, LBSS cannot associate the user with the identity by specific POIs.Theorem 2.
Assume that all of these attributes of locationk-anonymity, location l-diversity, query r-diversity, and reciprocal relationship of ASR can guarantee privacy, which makes our solution have the untraceability and the unlinkability.
OTPA is parallel to PIR. Both of them are based on encryption techniques to protect user privacy. Computational PIR relies on the quadratic residuosity problem. However, it cannot avoid a linear scan of the entire database for processing each query. The communication complexity of each query is roughlyn. The symbol n represents the size of the database. Therefore, the PIR techniques require extreme computational efficiency, where the usage of resources, such as run-time, storage, or data samples, is sublinear in the size of the candidate module. In contrast, OTPA does not have such requirements. Our solutions are superior to PIR techniques because the typical PIR framework does not limit the number of POIs obtained by the user. Thus, it does not provide an effective way to protect the valuable resources of LBS server.Theorem 3.
Assuming that the OTPA scheme is unconditionally secure, our solution achieves server-oriented security. It can be hard to maliciously get precious data of the LBS server.


## 7. Experiment Results and Discussion

We implement a prototype system by extending an existing work of C# program that supports OT protocol. The database is one of the widest and most interesting public data sets to analyze user trajectory which is generated by Brinkhoff’s network-based generator of moving objects. We conduct the experiments on a machine with Intel(R) Core(TM) i7-10510U CPU and 40 GB memory and some smartphones with Android 10 OS as the client. Our experimental default parameters are summarized in Table 2. We simulate 1000 users sending queries randomly to the LBS provider through a wireless network. Default values for these parameters constrain the scope of the following experiments; see Table 1 for specific meanings.Table 2
Parameters and default values.
ParametersDefault valuesR1km2k50m20r10C50Mi10kbitKi64bitIn the following experiments, we mainly focus on the communication cost and the computational cost, which is the dominating factor for the proposed solutions. In OT protocol, the cost of computation is often criticized with the comparison of communication cost. OT protocol is characteristically implemented using modular exponentiations, which are involved in the intensive computing. Therefore, researchers are more concerned about the effectiveness and availability of these algorithms in cryptographic applications.The first experiment aims at studying the time consumption with different numbers of candidate POIs. The efficiency of our approaches depends on parametersR and R′. Without loss of generality, we assume that the number of candidate POIs is directly proportional to the size of R′. The time consumption in two query phases is shown in Figure 8. The result shows that the CPU time of content query is large since the number of modular exponentiation is proportional to the number of candidate POIs.Figure 8
The time consumption in two query phases.As shown in Figures9–11, the CPU time is influenced by these parameters (R, R′, k, m, and r) in the region query and content query. We can find that more stringent privacy requirements take longer time.Figure 9
TheR and k influence on CPU time.Figure 10
TheR and m influence on CPU time.Figure 11
TheR′ and r influence on CPU time.Figure12 shows the result of the comparison with the typical method Casper and PIR. Experimental results indicate that the average processing time of the above three methods is linear to the number of candidate POIs. From computation efficiency, modular exponentiation is the most expensive. Therefore, Casper performs better than the other two methods in the average computation time.Figure 12
The comparison with the Casper and PIR.The second experiment focuses on studying the communication cost in the two-query phase. Figure13 shows that the communication cost in the region query is lower since the main communications are composed of some coordinates of POIs transferred from server to clients. The communication cost of the content query will just keep growing. However, its upper limit is around 550 kb since the category of POIs is no more than 50. The R and α affected communication cost in region query stage, and R and α are larger, which makes the traffic greater. R′ and C′ affected the communication cost in the content query stage. The larger the R′ and C′, the greater the traffic loads. At the same time, k and m have decided the area of R′, and r have limited the dimensions of C′. Therefore, the higher the user’s privacy requirement, the greater the traffic loads.Figure 13
The communication cost in the region query and content query.Finally, we observe the number of POIs that users obtain from each query since users are often charged by the LBS provider according to the number of retrieved POIs. We conduct experiments to compare with other techniques. Figure14 shows that the number of candidate POIs is linear to the number of users. The difference is due to the diversity of the querying methods. These results indicate that, in order to maintain an appropriate number of disclosed POIs, cloaking-based methods have to collect a large number of users. These result in a high cost of location updates and pose privacy concerns since all users must be trustworthy. The number of disclosed POIs is constant for PIR methods because no other users are required to construct a cloaking set. The number of candidate POIs gradually decreases from 50 to 1 as the user number increases in our solutions. However, only one candidate POI is exposed to the user submitting query. Therefore, we provide security guarantees for the resources of the LBS server.Figure 14
The relationship between candidate POIs and the number of users.


## 8. Conclusion

Our awareness of privacy has been heightened lately because some platforms abuse our personal data gathered by LBSS or LCS. Two prominent issues need to be further explored in the field of LBS privacy. Many studies assumed that the parties involved in anonymity are entirely trustworthy. In reality, participants could reveal the other location information because of the inconsistency of privacy degree of anonymous. In addition, the strategy that the LBSS confuse attackers with a plurality of redundant POIs information is not conducive to the operation of the LBS market and hinders the development of LBS. We developed a region queries framework and designed a privacy-aware query protocol-based oblivious transfer protocol, mainly to solve the aforementioned problems. Our solution has met the requirement of untraceability and unlinkability under the premise of preserving personal privacy. Therefore, it is certified that authenticated users can only obtain service information what they need, but malicious users cannot steal LBS server resources. Simulation results show a mutual influence and interactive relationship between the query processing time, the communication cost, the privacy degree, and the candidate POIs. Although it is inevitable that strict privacy requirements must confront a sacrifice of service quality, we will enhance our understanding of LBS to strengthen future work from reducing operating costs to improving efficiency and reinforcing privacy.



---

*Source: 5972486-2021-11-18.xml*