# Unchained Cellular Obfuscation Areas for Location Privacy in Continuous Location-Based Service Queries

Authors: Jia-Ning Luo; Ming-Hour Yang
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

To access location-based service (LBS) and query surrounding points of interest (POIs), smartphone users typically use built-in positioning functions of their phones when traveling at unfamiliar places. However, when a query is submitted, personal information may be leaked when they provide their real location. Current LBS privacy protection schemes fail to simultaneously consider real map conditions and continuous querying, and they cannot guarantee privacy protection when the obfuscation algorithm is known. To provide users with secure and effective LBSs, we developed an unchained regional privacy protection method that combines query logs and chained cellular obfuscation areas. It adopts a multiuser anonymizer architecture to prevent attackers from predicting user travel routes by using background information derived from maps (e.g., traffic speed limits). The proposed scheme is completely transparent to users when performing continuous location-based queries, and it combines the method with actual road maps to generate unchained obfuscation areas that conceal the actual locations of users. In addition to using a caching approach to enhance performance, the proposed scheme also considers popular tourist POIs to enhance the cache data hit ratio and query performance.


---

## Body

## 1. Introduction

Currently, most mobile devices feature built-in positioning functions, and smartphone users frequently use location-based services (LBS) to query points of interest (POIs) within their vicinity (e.g., when searching for Chinese restaurants within a 10 km radius). Although using LBSs to rapidly locate places and routes is highly convenient, LBS providers may exploit the opportunity to collect the query contents and travel routes of specific users and then analyze these datasets to determine the users’ dietary habits, shopping preferences, and even personal medical histories. These behaviours are a severe breach of LBS user’ right to privacy.Numerous previous scholars [1, 2] developed peer-to-peer (P2P) cloaking algorithms to mask the identity and location of users to guarantee location privacy. These P2P algorithms satisfy k-anonymity by sharing the user location with other users. However, the approaches proposed in those studies search for k-1 conspirators surrounding the user, which may enable attackers to triangulate a user within an obfuscation area (OA) and deploy a variance-based attack (VBA) [3]. In [3], an approach was proposed that searches for other conspirators surrounding a user. Subsequently, a random conspirator in the group is selected to search for other conspirators. This process is repeated until the k-anonymity requirement is satisfied; that is, the user cannot be triangulated within an obfuscation area. Subsequently, P2P necessitates the exchange of location information between users. Therefore, users are required to trust other users in the obfuscation area. A malicious user could select different k to obtain the location of the other users by using the k-anonymity algorithm in [3]. They may even partner with LBS providers to steal personal data from regular users, increasing the risk of privacy leaks.Recent studies have proposed methods for masking the identity [4, 5], location [6–8], and query information [9] of users by using secure third-party anonymizers to encode the location of a user or POI. Anonymizers not only protect user privacy but also reduce communication time and costs. One study [4] proposed using an anonymizer to mask the identities of a group of query users by using the identity of one random user in the group. These queries, which contain the same metadata, are transmitted to the LBS server. Another study [7] used a Hilbert curve to create an obfuscation area to mask the location of users. Anonymizers mask users by randomly selecting a representative user in proximity to a group of users. The metadata of the representative are copied to all queries before they are transmitted to the LBS server, thereby satisfying k-anonymity and obfuscation requirements. Anonymizers typically create obfuscation areas in grid [7, 10–12] or pyramid structure to mask user locations. In [13], a method was proposed to resolve the incompatibility between the original obfuscation area and query criteria by creating an additional obfuscated query area to keep privacy.Even when a user is masked within an obfuscation area to satisfyk-anonymity, LBS servers can collect user queries for area information when they submit continuous LBS queries in a short period. Users are more likely to use LBSs in unfamiliar rural tourist locations (rather than in urban areas) where roads are more dispersed. The simpler road network structures of rural areas enable LBS servers to determine the locations of users by analyzing maps and road conditions. To prevent LBS servers from cross-referencing continuous queries to obtain user location information, previous scholars have added reachable query routes to confuse LBS servers [14–18]. However, LBS servers can extrapolate known data, such as user habits, interests, and actual maps, to determine the most probable route of travel through an elimination process. In [19], a method was proposed to determine reasonable POIs within a user’s query area by analyzing his or her past query records. Subsequently, the user’s actual location is combined with a corresponding reasonable POI to generate a dummy query, preventing LBS servers from filtering out unreasonable dummy queries. A subsequent study [20] proposed a method that selects a nearby insensitive location from a user’s past travel routes to substitute sensitive query locations. However, this method was prone to leak the query location because it failed to account for map data and user mobility. In response, another study [17] combined an anonymizer with map data (all intersection branches within the road network) and user mobility. To confuse LBS servers, the anonymizer used in that study generated obfuscation areas that include the section of road extending from the user’s current intersection, but they do not include blind alleys or overlapping routes according to the user’s privacy requirements.In this study, we proposed a method combining the anonymizer provided by trusted third-party servers with actual road maps and users’ movement patterns to create multiple virtual paths. When user content cannot be detected in the cache, the mechanism is applied to guarantee the privacy of user queries. The proposed method provides users with high query performance when the query volume is high while guaranteeing location privacy. The method uses the popular query characteristics of tourist locations to enhance the cache hit ratio, query performance, and protection of users’ POI and query locations. The proposed method also considers similarities between pseudoqueries and users’ actual queries, as well as cached POIs, to prevent the generated pseudoqueries from being filtered out by the LBS server, thereby increasing the cache life and hit ratio. The proposed method in the present study is suitable for continuous queries. It has the following contributions:(1)
The privacy of users’ POIs is maintained, even during continuous querying.(2)
POIs that are difficult for LBS servers to filter out are generated by incorporating area characteristics, logs, and user queries.(3)
User privacy requirements are satisfied, even when the location obfuscation algorithm is known to the attacker.(4)
Obfuscation areas are generated from real-time maps, thereby avoiding exposing user locations.(5)
Cache data are used to reduce the communication costs and time of the anonymizer and LBS server.The remainder of this paper is organized as follows. Section2 describes the system architecture and initialization phase, and Section 3 discusses the development of the proposed method. The security analysis and the performance analysis are discussed in Section 4, and Section 5 presents the conclusion.


## 2. System Architecture

The system architecture is illustrated in Figure1. When multiple users access LBSs to submit queries, the queries are transmitted to a trusted obfuscated server to protect user privacy. An anonymizer cross-references the query content with the cache database. If POI data matching the query content are detected, the query results are encrypted and returned to the users. In Figure 1, the queries “night market” and “super market” are returned to users from the anonymizer (indicated by the dotted line). If relevant data are not cached, the anonymizer obfuscates the user’s query and location and transmits the obfuscated query to the LBS server. In Figure 1, the user’s “fast food” query and location are obfuscated and transmitted to the LBS server (indicated by the solid line). Once the anonymizer receives the POIs within the obfuscation area from the LBS server, it updates the cache database, filters out the pseudodata, encrypts the query results, and returns the results to the user.Figure 1
System architecture.To reduce the computation load of the LBS server for processing user queries, the proposed method uses cell numbers instead of coordinates to represent the query range sent to the LBS server. However, this process necessitates additional computations and transmission costs to synchronize the maps, cell sizes, and cell numbers on the anonymizer and LBS server. Accordingly, we adopted a numbering system for the cellular structure to reduce the overhead costs. This method synchronizes only the center point of the map and the sides of the cells to maintain consistent map segregation and numbering between the anonymizer and LBS server.The proposed method adopts a trusted anonymizer to protect users’ queries from being collected by the LBS server or other attackers. However, five criteria must be met to successfully implement the proposed method. First, the map on the LBS server must be divided into a cellular structure with a cell side lengthR (Figure 2(a)), and the user’s query range must be an inscribed circle of the cellular structure (Figure 2(b)), where the query radius is the POI within the range of (3/2)R. Second, the LBS server cannot frequently revise the cellular structure of the map. Third, the anonymizer must be reliable for masking user locations. Fourth, the maps on the anonymizer must contain intersections, length of road sections, and speed-limit information. Fifth, the algorithm must be available to the public.Figure 2
Cellular structure; (a) cell numbering; (b) query range.
(a)
(b)Threat models for the LBS server and general attackers are defined in this section. The effectiveness of the proposed method for guarding against these threat models is discussed in Section4. First, the LBS servers and general attackers can continuously tap, collect, and leak user information. However, they do not alter inbound or outbound query information (e.g., query number). Second, attackers use the open obfuscation algorithm and their background knowledge on known intersections, road sections, and traffic speed limits to deduce users’ travel routes and determine their locations. Third, query results are returned from the LBS server to the anonymizer. This creates the opportunity for the LBS server or general attackers to analyze the cache data of the anonymizer by using known cache algorithms. Fourth, the LBS server and general attackers can cross-reference the obfuscation areas queried by different user IDs in different locations and at different times to identify the associations between different queries and determine the query information submitted by the same user.Without changing the center and side lengths of the cells, the initialization of the anonymizer and LBS server needs to be performed only once (procedures are presented in Section2.1). We developed a three-phase unchained location privacy protection method for processing user queries (procedures are presented in Section 3). The following section provides the initialization model. Notations lists and explains the notations used in this paper.


### 2.1. System Initiation

Once the anonymizer obtains the center coordinates(Hx(0,0),HY(0,0)) from the LBS server, it uses these coordinates to number each cell and determine their center points. The term (Hx(i,j),Hy(i,j)) denotes the center coordinates of each cell, where (i,j) represents the x- and y-axes of the cell. The cellular-structure map illustrated in Figure 2(a) is used to generate a cellular structure comprising cells with 1+3n(n+1) side lengths = R, where n represents the number of layers in the structure. The cells are numbered according to the (i,j) order, where the center of the map is (0,0). Assuming that the hexagonal cell has six directions, i increases in increments of 1 to the right and decreases in increments of 1 to the left; j increases in increments of 1 to the upper right and decreases in increments of 1 to the bottom left; i increases and j decreases in increments of 1 to the bottom right; and i decreases and j increases in increments of 1 to the upper left. Results are illustrated in Figure 2(a).Once all the cells in the anonymizer are numbered, setV (all intersection in G=(V,E), which is a figure containing section length weights) and set E with all sections linking two intersections in G=(V,E) are matched to each cell.(1)Vi,j⊆V∣Vi,j=Vi,j1∪Vi,j2∪⋯∪Vi,j6,Vi,j≠∅,Ei,j⊆E∣Ei,j=Ei,j1∪Ei,j2∪⋯∪Ei,j6,Ei,j≠∅,where V(i,j)Tir represents the intersections contained in triangle Tir in cell (i,j) and E(i,j)Tir represents the sections with length weights contained in the triangle Tir in cell (i,j).The numbering method for triangle Tir is illustrated in Figure3. Tir=1, 2, 3, 4, 5, and 6 refer to ΔP1P2P7, ΔP2P3P7, ΔP3P4P7, ΔP4P5P7, ΔP5P6P7, and ΔP6P1P7, respectively. This method enables the fewest cells in the obfuscation area to be used to cover the query range. Details concerning the generation procedures and verification of the obfuscation areas are presented in Section 3.Figure 3
A cell divided into 6 equilateral triangles.


## 2.1. System Initiation

Once the anonymizer obtains the center coordinates(Hx(0,0),HY(0,0)) from the LBS server, it uses these coordinates to number each cell and determine their center points. The term (Hx(i,j),Hy(i,j)) denotes the center coordinates of each cell, where (i,j) represents the x- and y-axes of the cell. The cellular-structure map illustrated in Figure 2(a) is used to generate a cellular structure comprising cells with 1+3n(n+1) side lengths = R, where n represents the number of layers in the structure. The cells are numbered according to the (i,j) order, where the center of the map is (0,0). Assuming that the hexagonal cell has six directions, i increases in increments of 1 to the right and decreases in increments of 1 to the left; j increases in increments of 1 to the upper right and decreases in increments of 1 to the bottom left; i increases and j decreases in increments of 1 to the bottom right; and i decreases and j increases in increments of 1 to the upper left. Results are illustrated in Figure 2(a).Once all the cells in the anonymizer are numbered, setV (all intersection in G=(V,E), which is a figure containing section length weights) and set E with all sections linking two intersections in G=(V,E) are matched to each cell.(1)Vi,j⊆V∣Vi,j=Vi,j1∪Vi,j2∪⋯∪Vi,j6,Vi,j≠∅,Ei,j⊆E∣Ei,j=Ei,j1∪Ei,j2∪⋯∪Ei,j6,Ei,j≠∅,where V(i,j)Tir represents the intersections contained in triangle Tir in cell (i,j) and E(i,j)Tir represents the sections with length weights contained in the triangle Tir in cell (i,j).The numbering method for triangle Tir is illustrated in Figure3. Tir=1, 2, 3, 4, 5, and 6 refer to ΔP1P2P7, ΔP2P3P7, ΔP3P4P7, ΔP4P5P7, ΔP5P6P7, and ΔP6P1P7, respectively. This method enables the fewest cells in the obfuscation area to be used to cover the query range. Details concerning the generation procedures and verification of the obfuscation areas are presented in Section 3.Figure 3
A cell divided into 6 equilateral triangles.


## 3. Unchained Location Protection Scheme

When a user submits a query, he transmits his ID,Pa(Lx,Ly), POI for the query, and the k-anonymity requirements to the anonymizer. The anonymizer applies the three-phase obfuscation algorithm (Figure 4) to obfuscate his location prior to sending the query to the LBS server. The server then returns the queried information to the anonymizer, which filters out nonuser information before returning the POIs to the user. In Phase 1, the user’s real coordinates are used to calculate the cell number of the user location and the triangle Tir within the cell. If the cell number and POI information are already cached in the anonymizer, the algorithm skips to Phase 3. Otherwise, it continues to the next phase. In Phase 2, multiple obfuscation areas are generated according to the user’s privacy requirements. The obfuscation area that contains the query range is substituted with a pseudo-ID and a pseudoquery order before it is transmitted to the LBS server. The anonymizer then caches the information returned by the LBS server (including the user’s original query and generated pseudoquery). This information can then be used for similar queries in the future. Finally, the anonymizer uses the substituted user ID to retrieve the POI results. In Phase 3, the filtered query results are returned to the user.Figure 4
Query process.Calculation of the cell numbers is explained in Section3.1, generation of users’ obfuscation areas is described in Section 3.2, generation of multiple pseudoobfuscation areas to protect the privacy of multiple users simultaneously submitting queries and using the cache to achieve unchained location protection are presented in Section 3.3, and query submission is outlined in Section 3.4.


### 3.1. Calculating User Cell Number

Once the anonymizer receives the current location coordinates of the user(Pa(Lx,Ly)), it applies (2) to calculate the vertical displacement of the user relative to the center coordinates of the map Hx0,0,Hy0,0. The anonymizer then incorporates the vertical displacement into (3) to determine the cell number i,j of the user. The calculation process is discussed as follows: (2)j=2Ly-Hy0,0+d3R+e,whereLy≥Hy0,0-2Ly-Hy0,0+d3R-e,whereLy<Hy0,0(3)e=1ifLy-Hy0,0+dmod⁡3R2d>10ifLy-Hy0,0+dmod⁡3R2d≤1.First, the vertical distance between the user(Ly) and origin (Hy0,0) is used to calculate j of the cell number for the user location. The distance between the center points of two vertically adjacent cells (e.g., (0, 0) and (−1, 2) in Figure 5(a)) is 3R, and the cell numbers of these two cells differ by 2. When Ly is located above the center coordinates (Ly≥Hy0,0), Lx,Hy0,0 on y=Hy0,0 is added to Ly-Hy0,0. This point extends downward vertically to the cell boundary for distance d. The number of cells within d is calculated and incorporated into (3) to determine whether the final section smaller than 3R crosses over to another cell. In Example 1 (Figure 5(b)), the user is located on a random point (Pa) of Lx,Ly above the center coordinates. Ly-Hy0,0+d can be expressed as PaPc¯=PaPb¯+PbPc¯=3R+PaPd¯ and j=2+e (see (2)). Moreover, e=0 because PaPb-<2d (see (3)). Thus, the user in Example 1 is located in j=2 on the y-axis. In Example 3 (Figure 5(c)), j=0+e because PaPc¯<3R (see (2)). However, e=1 because PaPc¯>2d (see (3)). Thus, the user in Example 2 is located in j=1. The cell number (j) of users can be determined using (2) and (3).Figure 5
Calculating the distance between cells; (a) distance of vertically adjacent cells; (b) user within the same cell (e=0); (c) user crossing over to another cell (e=1).
(a)
(b)
(c)The preceding discussion indicates thatd must be determined before j is calculated. The length of d is associated with a user’s Lx coordinate. The value of d gradually increases as Lx shifts from the cell boundary (d=R/2) to the center of the cell (d=R). Figure 6 shows that the center distance between two cells is 2R∗cos⁡30°=3R. In other words, one length cycle of d is 3R.(4)d=fLx=13αLx-32R+R2(5)αLx=Lx-Hx0,0mod3RFigure 6
Distance between two horizontally adjacent cells.The termd can be expressed as a triangular wave by using R≤d≤R/2 and a length cycle of 3R. The wave equation is expressed in (4), where 1/3 is the positive slope of 0≤x≤3R and R/2 is the vertical displacement distance. Because each 3R represents one cycle (see (5)), the relationship diagram between Lx and d can be illustrated by calculating the location of Lx in a single cycle, as shown in Figure 7.Figure 7
Effects ofLx on d.Coordinates on they-axis increase by 3/2R when 1 is added to the y-axis. Therefore, the offset (j∗3/2R) caused by the change in the Y-coordinates must be subtracted when calculating the X-coordinates. Then, the current distance between Lx and the origin on the x-axis is multiplied by a unit length to obtain i on the x-axis, as illustrated in Figure 5(b). We know that Lx,Ly is located in i,2, j=2, and the distance between Hx0,0 and Lx is less than 3/2R. Hence, a user cell number of i=-1 can be calculated using (3). Therefore, when the location of the user is known Lx,Ly, (Hx0,0,Hy0,0) and (2) and (3) can be used to determine the current location of the user, that is, (-1,2) in Figure 5(b).


### 3.2. Determining the Obfuscation Area

Once the cell number containing the user location and center coordinates is confirmed and if the user query information has not been cached, the anonymizer produces an obfuscation area for the user query and transmits the obfuscation area to the LBS server. The triangle Tir of the cell in which the user is located must be determined to obtain the number of cells required to encompass the query range and produce the minimum obfuscation areas. First, three straight lines passing through a random cell in the cellular-structure map are conceptualized (the three red lines in the cell illustrated in Figure3). The three lines divide the cell into six equilateral triangles. Without loss of generalizability, the linear equations of the three straight lines intersecting the cell containing the current location of the user (i,j) can be used to determine the equilateral triangle with the user (Figure 8):Linear equation ofP1P4¯,  f0x,y:x-Hxi,j=0Linear equation ofP2P5¯,  f1x,y:x-Hxi,j-3y-Hyi,j=0Linear equation ofP3P6¯,  f2x,y:x-Hxi,j+3y-Hyi,j=0Figure 8
The obfuscation area: (a) user inTir=1;(b) user inTir=2.
(a)
(b)For example, whenf0(Lx,Ly)≥0, f1(Lx,Ly)<0, and f2(Lx,Ly)>0, f0(Lx,Ly) represent that the user is either on or to the right of P1P4¯; f1(Lx,Ly) indicates that the user is on P2P5¯; and f2(Lx,Ly) means that the user is on P3P6¯. A combined analysis of the three lines shows that the user is in ΔP1P2P7 of Tir=1 (Figure 8(a)). Thus, four cells are selected as the obfuscation area for the user’s query. These cells are numbered (i,j), (i,j+1), (i+1,j), and (i-1,j+1). If the user’s location is at the center of the cell (Lx=Hxi,j) and Ly=Hyi,j, a random equilateral triangle can be represented the user’s query location. In Algorithm 1,QHpt represents the obfuscation area of query t in p, and p=1 is the obfuscation area of the location provided by the user.Algorithm 1:Generating an obfuscation area to cover the query range of users.
Obfuscation Area
Input: User position Pa(Lx,Ly), User Cell No. (iPa,jPa)
Output: QH
(1)i,j=iPa,jPa
(2)Tir=0
(3)ifLx=Hxi,jandLy=Hyi,j
(4)Tir=Random1,2,…,6
(5)endif
(6)if((f0(Lx,Ly)≥0andf1(Lx,Ly)<0)orTir=1)
(7)QH=i,j,i,j+1,i+1,j,i-1,j+1
(8)elseif((f0(Lx,Ly)>0andf2(Lx,Ly)>0)orTir=2)
(9)QH=i,j,i+1,j,i,j+1,i+1,j-1
(10)elseiff0Lx,Ly>0andf1(Lx,Ly)>0andf2(Lx,Ly)≤0orTir=3
(11)QH=i,j,i+1,j,i,j-1,i+1,j-1
(12)elseiff0(Lx,Ly)≤0andf1(Lx,Ly)>0andf2(Lx,Ly)<0orTir=4
(13)QH=i,j,i-1,j,i,j-1,i+1,j-1
(14)elseif((f0(Lx,Ly)<0andf1(Lx,Ly)≤0andf2(Lx,Ly)<0)orTir=5)
(15)QH=i,j,i-1,j,i,j-1,i-1,j+1
(16)else
(17)QH=i,j,i-1,j,i,j+1,i-1,j+1
(18)endif
(19)returnQHSubsequently, whether the four cells encompass the user’s query range must be determined. In Algorithm1, three cells neighboring a random triangular section of (i,j) in Figure 8 are selected to form four cells. Because of the similarities among the three triangles, a random location in the upper-right triangular section of i,j is selected, without loss of generalizability, to verify that the combined area of the four shaded cells is the minimum obfuscation area to encompass the user’s query range (Figure 9).Figure 9
Query range and the obfuscation area.Supporting Theorem 1.If the query range center isPa, the radius of the query range is3/2R. The user is in a random location in a triangular section with pointsP1=(Hxi,j,Hyi,j+R),P2=(Hxi,j+3/2R,Hyi,j+1/2R), andP7=(Hxi,j,Hyi,j)and a side lengthR(Figure9). Subsequently, the query range must include the cell with the triangular section and three neighboring cells to create an OA comprising four cells, specifically(Hxi,j,Hyi,j),(Hxi+1,j,Hyi+1,j),Hxi-1,j+1,Hyi-1,j+1, and(Hxi,j+1,Hyi,j+1).Proof.
In Figure9, if Pa is located between P1=(Hxi,j,Hyi,j+R) and P2=(Hxi,j+3/2R,Hyi,j+1/2R) on a line expressed as x+3y=3R, then a parallel line (x+3y=23R) with a vertical distance of 3/2R can be determined. Subsequently, two points can be observed on x+3y=23R, namely, P9=Hxi,j,Hyi,j+2R and P11=Hxi,j+3R,Hyi,j+R, which denotes that P2P11¯=P1P9¯=R and the vertical distance from P1P2¯ to P9P11¯ is 3/2R. Similarly, a parallel line to P1P7¯ with a distance of 3/2R can be observed (P5P8¯). Therefore, P1P8¯=P5P7¯=R. A parallel line to P2P7¯ with a distance of 3/2R can be observed (P4P11¯). Therefore, P4P7¯=P2P12¯=R. Subsequently, the vertical distances from P1 to P9P11¯, from P2 to P4P12¯, and from P7 to P5P8¯ are all 3/2R. Thus, a circular query range with a radius of 3/2R and a center point anywhere within the triangle created by P1, P2, and P7 inevitably encompasses a section of the hexagonal section created by P4, P5, P8, P9, P11, and P12. Moreover, the polygon created by P4, P5, P8, P9, P11, and P12 encompasses (Hxi,j,Hyi,j), (Hxi+1,j,Hyi+1,j), (Hxi-1,j+1,Hyi-1,j+1), and (Hxi,j+1,Hyi,j+1). Therefore, Supporting Theorem 1 holds.Supporting Theorem 1 confirms that the obfuscation areas generated using the four cells encompasses the user’s query range. We subsequently developed an additional theorem to test whether a fewer number of cells can be used to encompass the user’s query range.Supporting Theorem 2.If the query range center isPa, the radius of the query range is3/2R. The user is in a random location within a triangular section with pointsP1=(Hxi,j,Hyi,j+R),P2=(Hxi,j+3/2R,Hyi,j+1/2R), andP7=(Hxi,j,Hyi,j)and a side lengthR(Figure9). Subsequently, at least four cells are required to encompass the user’s query range.Proof.
Assume thatPa is in a random location in ΔP1P2P7. Subsequently, only three cells are required to encompass the user’s query range. From Figure 9, the center point of the Pa on P1P2¯ can be identified. With only three cells, the diameter of the query range must be less than or equivalent to R of P1P2¯ (query diameter ≤R). In actuality, the query diameter is greater than R(3R>R). Thus, this hypothesis is contrary to fact, verifying that at least four cells are required for the obfuscation area to encompass the users query range.Theorem 1.
If the user appears in a random location on the map, his or her query range is a circle with a radius of3/2R. The proposed algorithm can use the lowest number of cells to encompass the user’s query range. The algorithm can maintain one-third of the size of the obfuscation area when the obfuscation algorithm is known to the attacker.Proof.
Supporting Theorem 1 indicates that an obfuscation area comprising four cells could sufficiently encompass the user’s query range when the user is located in a random location inΔP1P2P7. Supporting Theorem 2 indicates that at least four obfuscated cells are required in order to sufficiently encompass the user’s query range when the user is located in a random location in ΔP1P2P7. Naturally, the user must be in ΔP1P2P7 or ΔP1P2P10 for the LBS server to produce the shaded obfuscation areas with the algorithm (Figure 9). The combined area of the two triangles is guaranteed to be one-third of the obfuscation areas.The user is located within a cell comprising six equilateral triangles. Therefore, the location of the user inΔP1P2P7 is verified regardless of which triangle the user is located in. This suggests that if the user is located anywhere on the map, the proposed obfuscation algorithm produces an obfuscation area of at least four cells, which is the lowest number of cells required, and guarantees that the area of the cells is at least one-third of the obfuscation areas.


### 3.3. Producing the Obfuscation Areas of Multiple Pseudoqueries

Section3.2 describes how an obfuscated query area is produced to prevent attackers from obtaining the locations of users in sensitive areas such as special clinics or gyms. Users largely assume that attackers have a 1 in k chance of intercepting submitted queries (k-anonymity). Thus, we developed an algorithm that can produce multiple pseudoqueries to satisfy users’ k-anonymity settings. To enhance the relevance of the pseudoqueries and reduce the number of obfuscation areas, we developed an algorithm that produces multiple pseudoqueries in batches so that individual obfuscation areas and queries can serve as pseudoqueries for other users. Finally, the algorithm replenishes inadequate queries while satisfying individual privacy requirements.When the anonymizer receivest privacy requests (k1t,k2t,…,kut) in T from u users in different locations (CN1t,CN2t,…,CNut) and no matches are cached, these queries must be transmitted to the LBS server. The anonymizer uses the proposed algorithm (Algorithm 1) to generate different obfuscation areas for the users (QH1t,QH2t,…,QHut). If the users collectively form an OA, then QSt=QH1t,QH2t,…,QHut can satisfy the maximum privacy requirement of the users.(6)kMAXt=max⁡k1t,k2t,…,kut.In other words, the OA collectively formed by theu users must contain four times as many cells than the number of cells required for the maximum privacy requirements. (7)QH1t∪QH2t∪⋯∪QHut≥4∗kMAXt.The privacy requirements ofu users can be satisfied by combining the obfuscation areas of their query locations. However, the number of obfuscation areas must be generated when too few users are available or when users are close together (blue area in Figure 10). For example, Users A, B, and C in Figure 10 request a privacy strength of only 2. Therefore, k1t=k2t=k3t=2. However, the three users area within the same obfuscation area generated by the anonymizer, causing QH1t∪QH2t∪QH3t=4. In this instance, a pseudoobfuscation area consisting of four cells must be generated (Figure 10) to meet the obfuscated cell requirement of 4∗kMAXt=8.Figure 10
Overlapping user location causing inadequate privacy strength.To generate a pseudoobfuscation area that meets the privacy requirements, we developed a method for producing multiuser pseudoobfuscation areas (Algorithm2). The method follows three criteria to repeatedly produce obfuscation areas until the obfuscation requirement of kMAXt is met:(1)
Avoid VBAs [3] in the center location of the pseudoobfuscation area generated for the user’s location.(2)
Avoid generating pseudoobfuscation areas already cached in the anonymizer. Based on the open obfuscation area generation algorithm, attackers know that the queries transmitted to the LBS server are not cached in the anonymizer. Subsequently, the LBS server deduces the cache data of the anonymizer by using the open cache algorithm. Therefore, the pseudoqueries that are detected as cached queries by the LBS server are filtered out.(3)
Create new pseudocell numbers (CNdummyt) three layers from the user cell (CNselt) to avoid generating an obfuscation area that overlaps CNdummyt and CNselt and reinforce obfuscation strength more rapidly. Therefore, the anonymizer randomly selects one out of six cells three layers away from CNselt, namely, (isel+2,jsel+1), (isel+3,jsel-2), (isel+1,jsel-3), (isel-2,jsel-1), (isel-3,jsel+2), and isel-1,jsel+3, as CNdummyt to generate the obfuscation area.Algorithm 2:Producing an OA that satisfies all users.
Generate
k
M
A
X
t
Obfuscation Area
Input: kMAXt,CNt=CN1t,CN2t,…,CNut,
Q
S
t
=
Q
H
1
t
,
Q
H
2
t
,
…
,
Q
H
u
t,
NumOfCells=QH1t∪QH2t∪⋯∪QHut
Output: QSt
(1)while(NumOfCells<4∗kMAXt)
(2)CNselt=RandomCNt
(3)CNdummyt=FindDummyCellCNselt
(4)if(CNdummyt≠null)
(5)CNt=CNt+CNdummyt
(6)(dx,dy)=Random(VCNdummyt)
(7)tempQSt=ObfuscationAreadx,dy,CNdummyt
(8)if(tempQSt∉Cache)
(9)QSt=QSt+tempQSt
(10)NumOfCells=|QSt|
(11)endif
(12)endif
(13)endwhile
(14)returnQSt
FindDummyCell
Input: (CNselt)
(1)side=Random[1,2,…,6]
(2)if(side=1andVisel+2,jsel+1≠∅)
(3)CNdummyt=(isel+2,jsel+1)
(4)elseif(side=2andVisel+3,jsel-2≠∅)
(5)CNdummyt=(isel+3,jsel-2)
(6)elseif(side=3andVisel+1,jsel-3≠∅)
(7)CNdummyt=(isel+1,jsel-3)
(8)elseif(side=4andVisel-2,jsel+1≠∅)
(9)CNdummyt=(isel-2,jsel-1)
(10)elseif(side=5andVisel-3,jsel+2≠∅)
(11)CNdummyt=(isel-3,jsel+2)
(12)elseif(side=6andVisel-1,jsel+3≠∅)
(13)CNdummyt=isel-1,jsel+3
(14)else
(15) CNdummyt=null
(16)endif
(17)returnCNdummytA cell is randomly selected fromCNt to serve as the center point (Row (2)) to meet Criterion 1. Then, a pseudocell number CNdummyt (Row (3)) is randomly selected from the cells surrounding CNselt to meet Criteria 2 and 3. Subsequently, CNdummyt must contain an intersection. The pseudocell number CNdummyt is added to CNt so that CNt=CNt+CNdummyt (Row (5)), and the pseudoobfuscation area generated using CNdummyt is added to QSt (Rows (6) to (9)). This process is repeated until QHqt is generated to meet the obfuscation requirement of kMAXt. Finally, an obfuscation area set is produced.(8)QSt=QH1t,QH2t,…,QHqt∣∀i,j∈QHat,Vi,j≠0,1≤a≤q.In Figure11, Users A, B, and C move along the red line and transmit queries at the red points at different times. The blue, yellow, and red areas represent the three obfuscation areas generated by the anonymizer for the users’ queries transmitted to the LBS server. The anonymizer receives the privacy requirements of Users A and B, which are kA1=1 and kB1=2. However, QH11 and QH21 generated for the locations of Users A and B overlap, creating an OA with only seven cells. This fails to meet User B’s privacy requirement of 2, which requires eight cells (4∗kB1=8). The anonymizer selects a random cell (CNBt=(1,1)) three layers away from CNAt and CNBt. It identifies iB-2,jB-1=-1,0 and uses this cell to generate a pseudoobfuscation area (QH31). This generates an obfuscation area with 11 > 4∗kB1 (blue area in Figure 10), which meets the privacy requirements of Users A and B.Figure 11
Unchained obfuscation area generated for the continuous queries of three users.Then, the anonymizer separately receives the privacy requirements ofkA2=5, kB2=2, and kC2=3 from Users A, B, and C, respectively. Because the query of User A is already cached in the anonymizer, it can directly respond to that query. It then generates obfuscation areas for Users B and C and transmits them to the LBS server. Therefore, three obfuscation areas are created to satisfy the requirement of 4∗kC2=12 obfuscated cells, namely, QH12, QH22, and QH32 (yellow area in Figure 11).Finally, the anonymizer receives the privacy requirements ofkA2=1and kB2=2 from Users A and B, respectively. Because the query of User B is already cached in the anonymizer, it generates an obfuscation area only for User A in order to satisfy the two obfuscation requirements (red area in Figure 11).The preceding obfuscation method have two problems. First, the anonymizer can immediately respond to the user without accessing the LBS server when a similar query is cached. Existing methods aimed at enhancing the cache hit ratio ‎[25–27] effectively reduce the likelihood of exposing queries to the LBS server while conserving the communication cost and computation load of the anonymizer. For example, the proposed method uses a hierarchical clustering method ‎[28–31] to group the cached queries according to popularity. These groups are then used to generate corresponding pseudoqueries to prevent attacks that exploit an uneven query distribution [32].Second, when the anonymizer transmits user IDs to the LBS server, attackers can determine users’ travel routes by analyzing the queries of similar IDs, even when the location of the user is obfuscated. The following section proposes a method for generating unrepeated random pseudouser IDs for eachQHqt.


### 3.4. Generating Obfuscated Query Information

We developed a method to prevent LBS servers from combining obfuscation areas and user IDs to deduce users’ travel routes. Even when a simple algorithm is applied to substitute different user IDs with the same ID, LBS servers can still combine intersection and traffic speed-limit data to deduce users’ travel range and travel routes [33–36]. To prevent this problem, when the anonymizer generates q obfuscation areas for uh user queries QSt=QH1t,QH2t,…,QHqt to satisfy their user privacy requirements, it randomly produces theq pseudo-IDs:(9)VIDt=VID1t,VID2t,…,VIDqt∣q∈N+,∀VIDyt,VIDzt∈VIDt,VIDyt≠VIDzt.Then, the anonymizer combines all obfuscation areas and the corresponding POIs to generate(10)LocPoit=QH1t∥POI1t,QH2t∥POI2t,…,QHqt∥POIqt.The content is randomly interchanged to generate(11)LocPoit′=QH1t′∥POI1t′,QH2t′∥POI2t′,…,QHqt′∥POIqt′.Directly transmitting the query without changing the order ofLocPoit allows the LBS server to use the known algorithm to identify QH1t to be the real user location. Changes are logged with the anonymizer and used to filter user query results once they are returned by the LBS server. Finally, VIDt and LocPoit′ are combined to transmit the protected query to the LBS server:(12)Queryt=VIDt,LocPoit′.


## 3.1. Calculating User Cell Number

Once the anonymizer receives the current location coordinates of the user(Pa(Lx,Ly)), it applies (2) to calculate the vertical displacement of the user relative to the center coordinates of the map Hx0,0,Hy0,0. The anonymizer then incorporates the vertical displacement into (3) to determine the cell number i,j of the user. The calculation process is discussed as follows: (2)j=2Ly-Hy0,0+d3R+e,whereLy≥Hy0,0-2Ly-Hy0,0+d3R-e,whereLy<Hy0,0(3)e=1ifLy-Hy0,0+dmod⁡3R2d>10ifLy-Hy0,0+dmod⁡3R2d≤1.First, the vertical distance between the user(Ly) and origin (Hy0,0) is used to calculate j of the cell number for the user location. The distance between the center points of two vertically adjacent cells (e.g., (0, 0) and (−1, 2) in Figure 5(a)) is 3R, and the cell numbers of these two cells differ by 2. When Ly is located above the center coordinates (Ly≥Hy0,0), Lx,Hy0,0 on y=Hy0,0 is added to Ly-Hy0,0. This point extends downward vertically to the cell boundary for distance d. The number of cells within d is calculated and incorporated into (3) to determine whether the final section smaller than 3R crosses over to another cell. In Example 1 (Figure 5(b)), the user is located on a random point (Pa) of Lx,Ly above the center coordinates. Ly-Hy0,0+d can be expressed as PaPc¯=PaPb¯+PbPc¯=3R+PaPd¯ and j=2+e (see (2)). Moreover, e=0 because PaPb-<2d (see (3)). Thus, the user in Example 1 is located in j=2 on the y-axis. In Example 3 (Figure 5(c)), j=0+e because PaPc¯<3R (see (2)). However, e=1 because PaPc¯>2d (see (3)). Thus, the user in Example 2 is located in j=1. The cell number (j) of users can be determined using (2) and (3).Figure 5
Calculating the distance between cells; (a) distance of vertically adjacent cells; (b) user within the same cell (e=0); (c) user crossing over to another cell (e=1).
(a)
(b)
(c)The preceding discussion indicates thatd must be determined before j is calculated. The length of d is associated with a user’s Lx coordinate. The value of d gradually increases as Lx shifts from the cell boundary (d=R/2) to the center of the cell (d=R). Figure 6 shows that the center distance between two cells is 2R∗cos⁡30°=3R. In other words, one length cycle of d is 3R.(4)d=fLx=13αLx-32R+R2(5)αLx=Lx-Hx0,0mod3RFigure 6
Distance between two horizontally adjacent cells.The termd can be expressed as a triangular wave by using R≤d≤R/2 and a length cycle of 3R. The wave equation is expressed in (4), where 1/3 is the positive slope of 0≤x≤3R and R/2 is the vertical displacement distance. Because each 3R represents one cycle (see (5)), the relationship diagram between Lx and d can be illustrated by calculating the location of Lx in a single cycle, as shown in Figure 7.Figure 7
Effects ofLx on d.Coordinates on they-axis increase by 3/2R when 1 is added to the y-axis. Therefore, the offset (j∗3/2R) caused by the change in the Y-coordinates must be subtracted when calculating the X-coordinates. Then, the current distance between Lx and the origin on the x-axis is multiplied by a unit length to obtain i on the x-axis, as illustrated in Figure 5(b). We know that Lx,Ly is located in i,2, j=2, and the distance between Hx0,0 and Lx is less than 3/2R. Hence, a user cell number of i=-1 can be calculated using (3). Therefore, when the location of the user is known Lx,Ly, (Hx0,0,Hy0,0) and (2) and (3) can be used to determine the current location of the user, that is, (-1,2) in Figure 5(b).


## 3.2. Determining the Obfuscation Area

Once the cell number containing the user location and center coordinates is confirmed and if the user query information has not been cached, the anonymizer produces an obfuscation area for the user query and transmits the obfuscation area to the LBS server. The triangle Tir of the cell in which the user is located must be determined to obtain the number of cells required to encompass the query range and produce the minimum obfuscation areas. First, three straight lines passing through a random cell in the cellular-structure map are conceptualized (the three red lines in the cell illustrated in Figure3). The three lines divide the cell into six equilateral triangles. Without loss of generalizability, the linear equations of the three straight lines intersecting the cell containing the current location of the user (i,j) can be used to determine the equilateral triangle with the user (Figure 8):Linear equation ofP1P4¯,  f0x,y:x-Hxi,j=0Linear equation ofP2P5¯,  f1x,y:x-Hxi,j-3y-Hyi,j=0Linear equation ofP3P6¯,  f2x,y:x-Hxi,j+3y-Hyi,j=0Figure 8
The obfuscation area: (a) user inTir=1;(b) user inTir=2.
(a)
(b)For example, whenf0(Lx,Ly)≥0, f1(Lx,Ly)<0, and f2(Lx,Ly)>0, f0(Lx,Ly) represent that the user is either on or to the right of P1P4¯; f1(Lx,Ly) indicates that the user is on P2P5¯; and f2(Lx,Ly) means that the user is on P3P6¯. A combined analysis of the three lines shows that the user is in ΔP1P2P7 of Tir=1 (Figure 8(a)). Thus, four cells are selected as the obfuscation area for the user’s query. These cells are numbered (i,j), (i,j+1), (i+1,j), and (i-1,j+1). If the user’s location is at the center of the cell (Lx=Hxi,j) and Ly=Hyi,j, a random equilateral triangle can be represented the user’s query location. In Algorithm 1,QHpt represents the obfuscation area of query t in p, and p=1 is the obfuscation area of the location provided by the user.Algorithm 1:Generating an obfuscation area to cover the query range of users.
Obfuscation Area
Input: User position Pa(Lx,Ly), User Cell No. (iPa,jPa)
Output: QH
(1)i,j=iPa,jPa
(2)Tir=0
(3)ifLx=Hxi,jandLy=Hyi,j
(4)Tir=Random1,2,…,6
(5)endif
(6)if((f0(Lx,Ly)≥0andf1(Lx,Ly)<0)orTir=1)
(7)QH=i,j,i,j+1,i+1,j,i-1,j+1
(8)elseif((f0(Lx,Ly)>0andf2(Lx,Ly)>0)orTir=2)
(9)QH=i,j,i+1,j,i,j+1,i+1,j-1
(10)elseiff0Lx,Ly>0andf1(Lx,Ly)>0andf2(Lx,Ly)≤0orTir=3
(11)QH=i,j,i+1,j,i,j-1,i+1,j-1
(12)elseiff0(Lx,Ly)≤0andf1(Lx,Ly)>0andf2(Lx,Ly)<0orTir=4
(13)QH=i,j,i-1,j,i,j-1,i+1,j-1
(14)elseif((f0(Lx,Ly)<0andf1(Lx,Ly)≤0andf2(Lx,Ly)<0)orTir=5)
(15)QH=i,j,i-1,j,i,j-1,i-1,j+1
(16)else
(17)QH=i,j,i-1,j,i,j+1,i-1,j+1
(18)endif
(19)returnQHSubsequently, whether the four cells encompass the user’s query range must be determined. In Algorithm1, three cells neighboring a random triangular section of (i,j) in Figure 8 are selected to form four cells. Because of the similarities among the three triangles, a random location in the upper-right triangular section of i,j is selected, without loss of generalizability, to verify that the combined area of the four shaded cells is the minimum obfuscation area to encompass the user’s query range (Figure 9).Figure 9
Query range and the obfuscation area.Supporting Theorem 1.If the query range center isPa, the radius of the query range is3/2R. The user is in a random location in a triangular section with pointsP1=(Hxi,j,Hyi,j+R),P2=(Hxi,j+3/2R,Hyi,j+1/2R), andP7=(Hxi,j,Hyi,j)and a side lengthR(Figure9). Subsequently, the query range must include the cell with the triangular section and three neighboring cells to create an OA comprising four cells, specifically(Hxi,j,Hyi,j),(Hxi+1,j,Hyi+1,j),Hxi-1,j+1,Hyi-1,j+1, and(Hxi,j+1,Hyi,j+1).Proof.
In Figure9, if Pa is located between P1=(Hxi,j,Hyi,j+R) and P2=(Hxi,j+3/2R,Hyi,j+1/2R) on a line expressed as x+3y=3R, then a parallel line (x+3y=23R) with a vertical distance of 3/2R can be determined. Subsequently, two points can be observed on x+3y=23R, namely, P9=Hxi,j,Hyi,j+2R and P11=Hxi,j+3R,Hyi,j+R, which denotes that P2P11¯=P1P9¯=R and the vertical distance from P1P2¯ to P9P11¯ is 3/2R. Similarly, a parallel line to P1P7¯ with a distance of 3/2R can be observed (P5P8¯). Therefore, P1P8¯=P5P7¯=R. A parallel line to P2P7¯ with a distance of 3/2R can be observed (P4P11¯). Therefore, P4P7¯=P2P12¯=R. Subsequently, the vertical distances from P1 to P9P11¯, from P2 to P4P12¯, and from P7 to P5P8¯ are all 3/2R. Thus, a circular query range with a radius of 3/2R and a center point anywhere within the triangle created by P1, P2, and P7 inevitably encompasses a section of the hexagonal section created by P4, P5, P8, P9, P11, and P12. Moreover, the polygon created by P4, P5, P8, P9, P11, and P12 encompasses (Hxi,j,Hyi,j), (Hxi+1,j,Hyi+1,j), (Hxi-1,j+1,Hyi-1,j+1), and (Hxi,j+1,Hyi,j+1). Therefore, Supporting Theorem 1 holds.Supporting Theorem 1 confirms that the obfuscation areas generated using the four cells encompasses the user’s query range. We subsequently developed an additional theorem to test whether a fewer number of cells can be used to encompass the user’s query range.Supporting Theorem 2.If the query range center isPa, the radius of the query range is3/2R. The user is in a random location within a triangular section with pointsP1=(Hxi,j,Hyi,j+R),P2=(Hxi,j+3/2R,Hyi,j+1/2R), andP7=(Hxi,j,Hyi,j)and a side lengthR(Figure9). Subsequently, at least four cells are required to encompass the user’s query range.Proof.
Assume thatPa is in a random location in ΔP1P2P7. Subsequently, only three cells are required to encompass the user’s query range. From Figure 9, the center point of the Pa on P1P2¯ can be identified. With only three cells, the diameter of the query range must be less than or equivalent to R of P1P2¯ (query diameter ≤R). In actuality, the query diameter is greater than R(3R>R). Thus, this hypothesis is contrary to fact, verifying that at least four cells are required for the obfuscation area to encompass the users query range.Theorem 1.
If the user appears in a random location on the map, his or her query range is a circle with a radius of3/2R. The proposed algorithm can use the lowest number of cells to encompass the user’s query range. The algorithm can maintain one-third of the size of the obfuscation area when the obfuscation algorithm is known to the attacker.Proof.
Supporting Theorem 1 indicates that an obfuscation area comprising four cells could sufficiently encompass the user’s query range when the user is located in a random location inΔP1P2P7. Supporting Theorem 2 indicates that at least four obfuscated cells are required in order to sufficiently encompass the user’s query range when the user is located in a random location in ΔP1P2P7. Naturally, the user must be in ΔP1P2P7 or ΔP1P2P10 for the LBS server to produce the shaded obfuscation areas with the algorithm (Figure 9). The combined area of the two triangles is guaranteed to be one-third of the obfuscation areas.The user is located within a cell comprising six equilateral triangles. Therefore, the location of the user inΔP1P2P7 is verified regardless of which triangle the user is located in. This suggests that if the user is located anywhere on the map, the proposed obfuscation algorithm produces an obfuscation area of at least four cells, which is the lowest number of cells required, and guarantees that the area of the cells is at least one-third of the obfuscation areas.


## 3.3. Producing the Obfuscation Areas of Multiple Pseudoqueries

Section3.2 describes how an obfuscated query area is produced to prevent attackers from obtaining the locations of users in sensitive areas such as special clinics or gyms. Users largely assume that attackers have a 1 in k chance of intercepting submitted queries (k-anonymity). Thus, we developed an algorithm that can produce multiple pseudoqueries to satisfy users’ k-anonymity settings. To enhance the relevance of the pseudoqueries and reduce the number of obfuscation areas, we developed an algorithm that produces multiple pseudoqueries in batches so that individual obfuscation areas and queries can serve as pseudoqueries for other users. Finally, the algorithm replenishes inadequate queries while satisfying individual privacy requirements.When the anonymizer receivest privacy requests (k1t,k2t,…,kut) in T from u users in different locations (CN1t,CN2t,…,CNut) and no matches are cached, these queries must be transmitted to the LBS server. The anonymizer uses the proposed algorithm (Algorithm 1) to generate different obfuscation areas for the users (QH1t,QH2t,…,QHut). If the users collectively form an OA, then QSt=QH1t,QH2t,…,QHut can satisfy the maximum privacy requirement of the users.(6)kMAXt=max⁡k1t,k2t,…,kut.In other words, the OA collectively formed by theu users must contain four times as many cells than the number of cells required for the maximum privacy requirements. (7)QH1t∪QH2t∪⋯∪QHut≥4∗kMAXt.The privacy requirements ofu users can be satisfied by combining the obfuscation areas of their query locations. However, the number of obfuscation areas must be generated when too few users are available or when users are close together (blue area in Figure 10). For example, Users A, B, and C in Figure 10 request a privacy strength of only 2. Therefore, k1t=k2t=k3t=2. However, the three users area within the same obfuscation area generated by the anonymizer, causing QH1t∪QH2t∪QH3t=4. In this instance, a pseudoobfuscation area consisting of four cells must be generated (Figure 10) to meet the obfuscated cell requirement of 4∗kMAXt=8.Figure 10
Overlapping user location causing inadequate privacy strength.To generate a pseudoobfuscation area that meets the privacy requirements, we developed a method for producing multiuser pseudoobfuscation areas (Algorithm2). The method follows three criteria to repeatedly produce obfuscation areas until the obfuscation requirement of kMAXt is met:(1)
Avoid VBAs [3] in the center location of the pseudoobfuscation area generated for the user’s location.(2)
Avoid generating pseudoobfuscation areas already cached in the anonymizer. Based on the open obfuscation area generation algorithm, attackers know that the queries transmitted to the LBS server are not cached in the anonymizer. Subsequently, the LBS server deduces the cache data of the anonymizer by using the open cache algorithm. Therefore, the pseudoqueries that are detected as cached queries by the LBS server are filtered out.(3)
Create new pseudocell numbers (CNdummyt) three layers from the user cell (CNselt) to avoid generating an obfuscation area that overlaps CNdummyt and CNselt and reinforce obfuscation strength more rapidly. Therefore, the anonymizer randomly selects one out of six cells three layers away from CNselt, namely, (isel+2,jsel+1), (isel+3,jsel-2), (isel+1,jsel-3), (isel-2,jsel-1), (isel-3,jsel+2), and isel-1,jsel+3, as CNdummyt to generate the obfuscation area.Algorithm 2:Producing an OA that satisfies all users.
Generate
k
M
A
X
t
Obfuscation Area
Input: kMAXt,CNt=CN1t,CN2t,…,CNut,
Q
S
t
=
Q
H
1
t
,
Q
H
2
t
,
…
,
Q
H
u
t,
NumOfCells=QH1t∪QH2t∪⋯∪QHut
Output: QSt
(1)while(NumOfCells<4∗kMAXt)
(2)CNselt=RandomCNt
(3)CNdummyt=FindDummyCellCNselt
(4)if(CNdummyt≠null)
(5)CNt=CNt+CNdummyt
(6)(dx,dy)=Random(VCNdummyt)
(7)tempQSt=ObfuscationAreadx,dy,CNdummyt
(8)if(tempQSt∉Cache)
(9)QSt=QSt+tempQSt
(10)NumOfCells=|QSt|
(11)endif
(12)endif
(13)endwhile
(14)returnQSt
FindDummyCell
Input: (CNselt)
(1)side=Random[1,2,…,6]
(2)if(side=1andVisel+2,jsel+1≠∅)
(3)CNdummyt=(isel+2,jsel+1)
(4)elseif(side=2andVisel+3,jsel-2≠∅)
(5)CNdummyt=(isel+3,jsel-2)
(6)elseif(side=3andVisel+1,jsel-3≠∅)
(7)CNdummyt=(isel+1,jsel-3)
(8)elseif(side=4andVisel-2,jsel+1≠∅)
(9)CNdummyt=(isel-2,jsel-1)
(10)elseif(side=5andVisel-3,jsel+2≠∅)
(11)CNdummyt=(isel-3,jsel+2)
(12)elseif(side=6andVisel-1,jsel+3≠∅)
(13)CNdummyt=isel-1,jsel+3
(14)else
(15) CNdummyt=null
(16)endif
(17)returnCNdummytA cell is randomly selected fromCNt to serve as the center point (Row (2)) to meet Criterion 1. Then, a pseudocell number CNdummyt (Row (3)) is randomly selected from the cells surrounding CNselt to meet Criteria 2 and 3. Subsequently, CNdummyt must contain an intersection. The pseudocell number CNdummyt is added to CNt so that CNt=CNt+CNdummyt (Row (5)), and the pseudoobfuscation area generated using CNdummyt is added to QSt (Rows (6) to (9)). This process is repeated until QHqt is generated to meet the obfuscation requirement of kMAXt. Finally, an obfuscation area set is produced.(8)QSt=QH1t,QH2t,…,QHqt∣∀i,j∈QHat,Vi,j≠0,1≤a≤q.In Figure11, Users A, B, and C move along the red line and transmit queries at the red points at different times. The blue, yellow, and red areas represent the three obfuscation areas generated by the anonymizer for the users’ queries transmitted to the LBS server. The anonymizer receives the privacy requirements of Users A and B, which are kA1=1 and kB1=2. However, QH11 and QH21 generated for the locations of Users A and B overlap, creating an OA with only seven cells. This fails to meet User B’s privacy requirement of 2, which requires eight cells (4∗kB1=8). The anonymizer selects a random cell (CNBt=(1,1)) three layers away from CNAt and CNBt. It identifies iB-2,jB-1=-1,0 and uses this cell to generate a pseudoobfuscation area (QH31). This generates an obfuscation area with 11 > 4∗kB1 (blue area in Figure 10), which meets the privacy requirements of Users A and B.Figure 11
Unchained obfuscation area generated for the continuous queries of three users.Then, the anonymizer separately receives the privacy requirements ofkA2=5, kB2=2, and kC2=3 from Users A, B, and C, respectively. Because the query of User A is already cached in the anonymizer, it can directly respond to that query. It then generates obfuscation areas for Users B and C and transmits them to the LBS server. Therefore, three obfuscation areas are created to satisfy the requirement of 4∗kC2=12 obfuscated cells, namely, QH12, QH22, and QH32 (yellow area in Figure 11).Finally, the anonymizer receives the privacy requirements ofkA2=1and kB2=2 from Users A and B, respectively. Because the query of User B is already cached in the anonymizer, it generates an obfuscation area only for User A in order to satisfy the two obfuscation requirements (red area in Figure 11).The preceding obfuscation method have two problems. First, the anonymizer can immediately respond to the user without accessing the LBS server when a similar query is cached. Existing methods aimed at enhancing the cache hit ratio ‎[25–27] effectively reduce the likelihood of exposing queries to the LBS server while conserving the communication cost and computation load of the anonymizer. For example, the proposed method uses a hierarchical clustering method ‎[28–31] to group the cached queries according to popularity. These groups are then used to generate corresponding pseudoqueries to prevent attacks that exploit an uneven query distribution [32].Second, when the anonymizer transmits user IDs to the LBS server, attackers can determine users’ travel routes by analyzing the queries of similar IDs, even when the location of the user is obfuscated. The following section proposes a method for generating unrepeated random pseudouser IDs for eachQHqt.


## 3.4. Generating Obfuscated Query Information

We developed a method to prevent LBS servers from combining obfuscation areas and user IDs to deduce users’ travel routes. Even when a simple algorithm is applied to substitute different user IDs with the same ID, LBS servers can still combine intersection and traffic speed-limit data to deduce users’ travel range and travel routes [33–36]. To prevent this problem, when the anonymizer generates q obfuscation areas for uh user queries QSt=QH1t,QH2t,…,QHqt to satisfy their user privacy requirements, it randomly produces theq pseudo-IDs:(9)VIDt=VID1t,VID2t,…,VIDqt∣q∈N+,∀VIDyt,VIDzt∈VIDt,VIDyt≠VIDzt.Then, the anonymizer combines all obfuscation areas and the corresponding POIs to generate(10)LocPoit=QH1t∥POI1t,QH2t∥POI2t,…,QHqt∥POIqt.The content is randomly interchanged to generate(11)LocPoit′=QH1t′∥POI1t′,QH2t′∥POI2t′,…,QHqt′∥POIqt′.Directly transmitting the query without changing the order ofLocPoit allows the LBS server to use the known algorithm to identify QH1t to be the real user location. Changes are logged with the anonymizer and used to filter user query results once they are returned by the LBS server. Finally, VIDt and LocPoit′ are combined to transmit the protected query to the LBS server:(12)Queryt=VIDt,LocPoit′.


## 4. Analysis

This section analyzes the security and performance of the proposed method and compares the results with those of previous studies. In Section4.1, we present the security analysis items and compare past security problems. In Section 4.2, the method is applied to a map to examine the method’s real-time performance.


### 4.1. Security Analysis

The unchained location privacy protection method developed in the present study was based on a trusted anonymizer and existing user/anonymizer security architectures to protect information confidentiality. Therefore, this section discusses four threat models derived from attacks that occur during the communication between the trusted LBS server and anonymizer. The results verify that the proposed method can effectively guard against most LBS attacks when the algorithm is known to the attacker.When attackers possess the background knowledge of the maps and the capacity to continuously monitor user query content, they can issue the following attacks on user privacy:Location Homogeneity Attack (LHA). Attackers collect queries from a particularly sensitive area to collect user information, such as a hospital specializing in cardiology and heart surgery, to gain information on heart patients.Map Matching (MM). Attackers use background knowledge to filter out unlikely query source locations (e.g., lakes) to enhance the likelihood of identifying the actual locations of users.When LBS servers and general attackers use known location obfuscation algorithms to analyze the queries submitted by multiple users in obfuscated locations, they can perform the following attacks on user privacy:Known Algorithm Attack (KAA). Attackers who are aware of the obfuscation algorithm can use the algorithm to calculate the obfuscation areas generated in different locations and filter out the less likely results to reduce the obfuscation strength of user locations.Distance VBA. Attackers calculate the center points of obfuscation areas to estimate the actual locations of users ‎[3].When LBS servers and general attackers cross-reference the obfuscation areas of queries submitted by different IDs in different locations at different times, they can perform the following attacks on user privacy.Maximum Movement Boundary (MMB). Attackers examine the traffic speed limits of the map to calculate the maximum movement boundary of the user. They eliminate the areas that the user cannot reach to reduce the obfuscation areas of continuous queries.Multiple Query Attack (MQA). Attackers cross-reference the members and movement of users in different obfuscation areas to filter out pseudousers and identify real users.The results in Table1 show that the proposed method effectively guards against all known attacks. The symbol “O” denotes that the method can defend against this type of attack, and the symbol “X” denotes that the method fails to defend against this type of attack. In ‎[3, 21], methods were proposed to obfuscate the locations of numerous querying users. However, these methods failed to consider user locations that approximate sensitive areas, which enables attackers to exploit these areas by using LHAs to obtain user locations. In [3, 22], algorithms were developed to obfuscate multiquery submissions. However, these methods could not continuously obfuscate locations when the user is moving, which enables attackers to observe the route of the users by performing MQAs. In [20], a method was proposed to substitute sensitive query locations with nearby insensitive locations cached in the anonymizer. However, this method failed to consider user movement speeds, enabling attackers to filter user locations by performing MMBs. Moreover, [20] used the center location of users to generate obfuscation areas, enabling attackers to estimate the actual location of users by performing VBAs ‎[14, 21, 23–25]. Attackers could also confirm the center location of users in an obfuscation area once the algorithm is known to the attacker. In [22], a method was proposed for generating road network obfuscation areas by searching neighboring intersections to avoid placing users on the same road. However, systematically searching neighboring intersections enables attackers to perform KAs to map the obfuscation method and identify user locations.Table 1
Security comparison chart for multi-LBS queries.
Protocols
Attacker knowledge
LHA
MM
MQA
MMB
VBA
KA
Xu and Cai ‎[21]
X
O
O
O
X
X
Xu and Cai‎ [14]
O
O
O
O
X
X
Shankar et al. ‎[15]
O
O
O
O
O
O
Wang and Liu [22]
O
O
X
O
O
X
Ardagna et al. ‎[20]
O
O
O
X
O
O
Lee et al. ‎[23]
O
O
O
O
X
X
Song et al. ‎[24]
O
O
O
O
X
X
Niu et al.‎ [25]
O
O
O
O
X
X
Niu et al.‎ [3]
X
O
X
O
O
O
Our scheme
O
O
O
O
O
O


### 4.2. Performance Analysis

We implemented simulations in Java 8 on a computer equipped with an Intel i5-4570 CPU to create a test environment with a road map of Oldenburg, Germany [37]. Figure 12 shows that the anonymizer expanded the side length of the map from 10 to 40 km while generating cells to satisfy R. Notably, reducing the R-value increased the number of cells generated on maps with similar side lengths, reducing the content of each cell. The proposed method uses the same number of cells to obfuscate user query range. Therefore, lower R-values reduce the user query range and decrease the amount of data required to return query results from the LBS server.Figure 12
Effects of map size and cell size on the cell quantity.We observed intersection conditions by dividing the Oldenburg map intoR-sized cells (Figure 13). Results showed that smaller cells contained fewer intersections. Although Figure 12 shows that cells with shorter sides reduce the transmission load, the results in Figure 13 indicate that smaller cells reduce the number of intersections per cell. Fewer intersections increase the likelihood of attackers estimating the actual location of users. Therefore, a balance between transmission efficiency and the privacy strength must be achieved.Figure 13
Effects of the Oldenburg map and cell side length(R) on the number of intersections per cell.In Figure14, the privacy requirement of each user is assumed to be k=5 and R=1200 to compare the required average number of queries transmitted to the LBS server. Compared with the result of [25] regarding the number of queries submitted by a single user to generate an obfuscation area, our cache hit ratio was 0, indicating that, without using the cache, four users or more are required to simultaneously transmit a query to meet the privacy requirements with a reduced number of pseudoqueries sent by the anonymizer to the LBS server. The proposed method can combine the user queries of similar obfuscation areas to meet various privacy requirements. In [25], a cache was used to reduce computation and transmission loads. In the present study, we adopted a cache hit ratio of 70%, similar to that used in [25]. Regardless of the number of users, we maintained the privacy protection strength equivalent to that reported in [25], and the performance of the proposed method improved as the number of users was increased. In our proposed method, the number of obfuscation areas must be generated when too few users are available or when users are close together. When the number of users is 2, only 3 queries are submitted to the LBS in [25], and our method requires 6.185 queries with hit rate = 0% or 3.32 queries with hit rate = 70%. But in our method, the obfuscation areas of the query locations can be combined when the number of users increases, which reduce the number of queries that needs to be sent to the LBS. In Figure 14, when the number of users = 8, 12 queries is submitted to the LBS in [25], our method needs 8.019 queries with hit rate = 0% and only 6.427 queries with hit rate = 70%. In this situation, our performance is better than [25].Figure 14
Comparing the number of users and the query volume transmitted to the LBS Server.Figure15 shows that the average road lengths in the Oldenburg map that satisfy the k-anonymity when the radius R=1,200. In [22], the roads were simply extended to obfuscate the location of users. Niu et al.’s method [3] uses a random walk-based cloaking algorithm, and the method proposed in the present study divides the map into cells. Therefore, the average road lengths of the overall obfuscated areas using the proposed method and [3] were markedly longer than that determined using the method proposed in [22]. Moreover, we generate extra queries to simulate a multiuser environment which requires generating additional obfuscation areas when the cells overlap. The proposed method generated 4.88% longer road length than [3] when k=10.Figure 15
The relationship of thek-anonymity value and the average road length in the map.


## 4.1. Security Analysis

The unchained location privacy protection method developed in the present study was based on a trusted anonymizer and existing user/anonymizer security architectures to protect information confidentiality. Therefore, this section discusses four threat models derived from attacks that occur during the communication between the trusted LBS server and anonymizer. The results verify that the proposed method can effectively guard against most LBS attacks when the algorithm is known to the attacker.When attackers possess the background knowledge of the maps and the capacity to continuously monitor user query content, they can issue the following attacks on user privacy:Location Homogeneity Attack (LHA). Attackers collect queries from a particularly sensitive area to collect user information, such as a hospital specializing in cardiology and heart surgery, to gain information on heart patients.Map Matching (MM). Attackers use background knowledge to filter out unlikely query source locations (e.g., lakes) to enhance the likelihood of identifying the actual locations of users.When LBS servers and general attackers use known location obfuscation algorithms to analyze the queries submitted by multiple users in obfuscated locations, they can perform the following attacks on user privacy:Known Algorithm Attack (KAA). Attackers who are aware of the obfuscation algorithm can use the algorithm to calculate the obfuscation areas generated in different locations and filter out the less likely results to reduce the obfuscation strength of user locations.Distance VBA. Attackers calculate the center points of obfuscation areas to estimate the actual locations of users ‎[3].When LBS servers and general attackers cross-reference the obfuscation areas of queries submitted by different IDs in different locations at different times, they can perform the following attacks on user privacy.Maximum Movement Boundary (MMB). Attackers examine the traffic speed limits of the map to calculate the maximum movement boundary of the user. They eliminate the areas that the user cannot reach to reduce the obfuscation areas of continuous queries.Multiple Query Attack (MQA). Attackers cross-reference the members and movement of users in different obfuscation areas to filter out pseudousers and identify real users.The results in Table1 show that the proposed method effectively guards against all known attacks. The symbol “O” denotes that the method can defend against this type of attack, and the symbol “X” denotes that the method fails to defend against this type of attack. In ‎[3, 21], methods were proposed to obfuscate the locations of numerous querying users. However, these methods failed to consider user locations that approximate sensitive areas, which enables attackers to exploit these areas by using LHAs to obtain user locations. In [3, 22], algorithms were developed to obfuscate multiquery submissions. However, these methods could not continuously obfuscate locations when the user is moving, which enables attackers to observe the route of the users by performing MQAs. In [20], a method was proposed to substitute sensitive query locations with nearby insensitive locations cached in the anonymizer. However, this method failed to consider user movement speeds, enabling attackers to filter user locations by performing MMBs. Moreover, [20] used the center location of users to generate obfuscation areas, enabling attackers to estimate the actual location of users by performing VBAs ‎[14, 21, 23–25]. Attackers could also confirm the center location of users in an obfuscation area once the algorithm is known to the attacker. In [22], a method was proposed for generating road network obfuscation areas by searching neighboring intersections to avoid placing users on the same road. However, systematically searching neighboring intersections enables attackers to perform KAs to map the obfuscation method and identify user locations.Table 1
Security comparison chart for multi-LBS queries.
Protocols
Attacker knowledge
LHA
MM
MQA
MMB
VBA
KA
Xu and Cai ‎[21]
X
O
O
O
X
X
Xu and Cai‎ [14]
O
O
O
O
X
X
Shankar et al. ‎[15]
O
O
O
O
O
O
Wang and Liu [22]
O
O
X
O
O
X
Ardagna et al. ‎[20]
O
O
O
X
O
O
Lee et al. ‎[23]
O
O
O
O
X
X
Song et al. ‎[24]
O
O
O
O
X
X
Niu et al.‎ [25]
O
O
O
O
X
X
Niu et al.‎ [3]
X
O
X
O
O
O
Our scheme
O
O
O
O
O
O


## 4.2. Performance Analysis

We implemented simulations in Java 8 on a computer equipped with an Intel i5-4570 CPU to create a test environment with a road map of Oldenburg, Germany [37]. Figure 12 shows that the anonymizer expanded the side length of the map from 10 to 40 km while generating cells to satisfy R. Notably, reducing the R-value increased the number of cells generated on maps with similar side lengths, reducing the content of each cell. The proposed method uses the same number of cells to obfuscate user query range. Therefore, lower R-values reduce the user query range and decrease the amount of data required to return query results from the LBS server.Figure 12
Effects of map size and cell size on the cell quantity.We observed intersection conditions by dividing the Oldenburg map intoR-sized cells (Figure 13). Results showed that smaller cells contained fewer intersections. Although Figure 12 shows that cells with shorter sides reduce the transmission load, the results in Figure 13 indicate that smaller cells reduce the number of intersections per cell. Fewer intersections increase the likelihood of attackers estimating the actual location of users. Therefore, a balance between transmission efficiency and the privacy strength must be achieved.Figure 13
Effects of the Oldenburg map and cell side length(R) on the number of intersections per cell.In Figure14, the privacy requirement of each user is assumed to be k=5 and R=1200 to compare the required average number of queries transmitted to the LBS server. Compared with the result of [25] regarding the number of queries submitted by a single user to generate an obfuscation area, our cache hit ratio was 0, indicating that, without using the cache, four users or more are required to simultaneously transmit a query to meet the privacy requirements with a reduced number of pseudoqueries sent by the anonymizer to the LBS server. The proposed method can combine the user queries of similar obfuscation areas to meet various privacy requirements. In [25], a cache was used to reduce computation and transmission loads. In the present study, we adopted a cache hit ratio of 70%, similar to that used in [25]. Regardless of the number of users, we maintained the privacy protection strength equivalent to that reported in [25], and the performance of the proposed method improved as the number of users was increased. In our proposed method, the number of obfuscation areas must be generated when too few users are available or when users are close together. When the number of users is 2, only 3 queries are submitted to the LBS in [25], and our method requires 6.185 queries with hit rate = 0% or 3.32 queries with hit rate = 70%. But in our method, the obfuscation areas of the query locations can be combined when the number of users increases, which reduce the number of queries that needs to be sent to the LBS. In Figure 14, when the number of users = 8, 12 queries is submitted to the LBS in [25], our method needs 8.019 queries with hit rate = 0% and only 6.427 queries with hit rate = 70%. In this situation, our performance is better than [25].Figure 14
Comparing the number of users and the query volume transmitted to the LBS Server.Figure15 shows that the average road lengths in the Oldenburg map that satisfy the k-anonymity when the radius R=1,200. In [22], the roads were simply extended to obfuscate the location of users. Niu et al.’s method [3] uses a random walk-based cloaking algorithm, and the method proposed in the present study divides the map into cells. Therefore, the average road lengths of the overall obfuscated areas using the proposed method and [3] were markedly longer than that determined using the method proposed in [22]. Moreover, we generate extra queries to simulate a multiuser environment which requires generating additional obfuscation areas when the cells overlap. The proposed method generated 4.88% longer road length than [3] when k=10.Figure 15
The relationship of thek-anonymity value and the average road length in the map.


## 5. Conclusion

We developed a privacy protection scheme to protect the real location suitable for moving users. The scheme produces multiuser pseudoqueries and uses obfuscation areas to prevent LBS servers from directly deducing users’ real queries and precise locations. We verified that the method produces obfuscation areas with the least number of cells and guarantees one-third the original obfuscation areas size when the algorithm is disclosed. We also considered the distinct characteristic of user queries in different areas and adopted a grouping approach coupled with actual maps to reduce the likelihood of the pseudodata being filtered out by the LBS server, thereby satisfying users’ privacy requirements. Furthermore, we incorporated a caching system to store users’ continuous queries. The cache system coupled with multiuser queries prevents the LBS server from completing deducing users’ routes. Instead, the LBS server can generate only scattered and obfuscated user locations. Therefore, the proposed method effectively protects location privacy during continuous querying. The cache approach also reduces the likelihood of user locations being transmitted to the LBS server, decreases the computation and transmission loads of the anonymizer, and enhances system performance. The proposed method is fully compatible with various user devices. They can use their original mobile devices and Internet service providers to access the trusted anonymizer to protect their location details when submitting a query. Finally, we verified that the proposed method effectively protects users’ identities, locations, and interests and guards against most currently known attacks on location privacy. We also used a real-time road map to test the proposed method. Figure14 shows that the proposed method uses a cache approach to greatly reduce the amount of query information exposed to the LBS server. A summary of the results illustrated in Figures 14 and 15 shows that the proposed method outperformed other existing methods.



---

*Source: 7391982-2017-09-28.xml*