# A User-Defined Location-Sharing Scheme with Efficiency and Privacy in Mobile Social Networks

Authors: Tao Peng; Jierong Liu; Guojun Wang; Qin Liu; Jianer Chen; Jiawei Zhu
Journal: Scientific Programming
 (2020)

---

## Abstract

The popularity of the modern smart devices and mobile social networks (MSNs) brings mobile users better experiences and services by taking advantage of location-aware capabilities. Location sharing, as an important function of MSNs, has attracted attention with growing popularity. While the users get great benefits and conveniences from MSNs, they also have high concerns about the privacy of location. However, in the existing solution, the privacy of users can hardly be guaranteed without the assumption of full trust in the service provider (SP), and few previous research studies have discussed the individual requirement of mobile users in MSNs. In this paper, we propose a user-defined location-sharing scheme (ULSS) to achieve enhanced privacy preservation under different contexts. We present a coarse-grained proximity detection method and a lightweight order-preserving encryption- (OPE-) based method to provide the users with flexible privacy preservation at different privacy levels. The proposed scheme preserves user’s location privacy with respect to SP, friends, and other adversaries, getting rid of the introduction of fully trusted party (TTP). Extensive experiments were conducted to verify the effectiveness and efficiency of our proposed scheme.


---

## Body

## 1. Introduction

With the development of the smartphone and wireless communications technology, mobile social networks (MSNs) have seen a tremendous rise and are becoming a kind of important tool for our daily communication. MSNs such as Foursquare, Wechat, and Google Latitude bridge the users’ physical and social worlds taking advantage of location-aware capabilities by mobile devices. Sharing and interaction around content and information is the key feature of the MSNs. In particular,location sharing [1], as an important function of MSNs, allows users to share their current locations to the friends on the social networks or to find the nearby friends within a certain physical distance. Based on it, MSNs bring mobile users better experiences and services by various location-based and personalized services, e.g., proximity-based detection [2] and friend locator [3], or just simple location sharing [1].MSNs facilitate the mobile users and make it easier for social friends to connect in real life. While the users reap great benefit and convenience from MSNs, they also have high concerns about the privacy of location, since the users have to submit their exact location information to their friends or to the service provider (SP) when they enjoy the service. The centralized SP collects all user’s information, e.g., the user identity, the exact location, and query content. If the private information is disclosed by potentially untrustworthy SP or is compromised by an adversary, it will put the users’ sensitive information in jeopardy. Specifically, in MSNs, the user’s location information is associated with the social network ID and the social relationships of users, which makes the user privacy preservation more significant and more complicated [4–7]. Therefore, there are both the development chance and challenge in MSNs, and the key is how to protect the privacy of users when providing high-quality services.Over the past years, some approaches have been proposed to address location privacy in MSNs [8–10], and a few solutions [11–14] were presented to focus on user privacy preservation in case of location sharing. Li et al. [11] presented a secure location-sharing scheme in which the user information was stored in two kinds of servers, e.g., location server (LS) and social network server (SNS), which incurs high communication cost due to the multiple-round interaction between the user and the servers. Moreover, the privacy of users can hardly be guaranteed without the assumption of full trust in the SP. In our previous work [3], we proposed a lightweight privacy-aware friend locator (PAFL) to provide privacy guarantee for the user at low computational and communication cost. However, the coarse-grained friend locator method cannot meet the personalized needs of mobile users. The challenge is that the user may submit diverse requirements and wants to set different levels of privacy protection due to the varying contextual conditions. Here is a typical example of proximity-based location sharing: Alice travels to a city, she first wants to find out the friends who are located in the destination she is visiting by the MSNs, e.g., Facebook Connect. Next, according to the name list returned by server, Alice wants to query some specified friends whether they are in the nearby vicinity region defined by her, e.g., within a mile or so. In this application, Alice refuses to reveal her exact location to any third party (including SP and other users), whether she is the initiator of the query or the location provider (friend). While the existing schemes [11, 14] are inflexible for users to change the privacy setting, it is difficult to meet the individualized demand preferences for different users in the traditional system.In this paper, to satisfy the users’ individual requirements, we propose a user-defined location-sharing scheme (ULSS) to realize proximity query of users in different scales of vicinity regions. Our motivation is to provide the mobile users with flexible privacy controls under different contexts in an efficient and friendly way. We first propose a coarse-grained proximity detection method based on the Hilbert curve to determine the friends in a wide range of vicinity. Then, we provide a lightweight order-preserving encryption- (OPE-) based method to enable users to query the specular friends in the nearby specified vicinity, e.g., within 5 km. In the whole process, users can submit their proximity query according to their individual requirements and different personal privacy settings, without revealing the exact location information to any SP or to any other possibly malicious users.Our main contributions are summarized as follows:(1)
We propose a flexible ULSS for private proximity detection, which allows each user to maintain his own privacy-preserving policy and provides the users with flexible privacy protection at different privacy levels.(2)
We propose two protocols to process the user queries in different phases, which preserve user’s location privacy with respect to SP, friends, and other adversaries. We also prove that the proposed scheme is secure under the stronger security model with enhanced privacy.(3)
We evaluate the performance of our ULSS scheme by extensive experiments. Experiment results demonstrate that our scheme is extremely efficient for coarse-grained proximity detection and provides user-defined nearby friend locator at low computational and communication cost as well.In our scheme, the fully-trusted third party is not required, the SP is assumed to be “honest but curious,” and it honestly executes instructions in the system, like storing user data, handling user’s queries, and returning the results to the issuer. However, it is curious about the collected information of users and may try to determine or locate a query user.The remainder of this paper is organized as follows. In Section2, we briefly introduce the technical preliminaries, including Hilbert curve and OPE. Then, the overview of the system is stated in Section 3. In Section 4, we describe the system design, and the security analysis of our scheme is provided in Section 5. We conduct a set of experiments to evaluate the effectiveness of our scheme in Section 6. The related work is presented in Section 7. Finally, the conclusion and future work are discussed in Section 8.


## 2. Preliminaries

### 2.1. Hilbert Curve

The Hilbert curve is a space-filling curve [15], which visits each point once and once only in a specified order by some algorithms in 2-dimensional (2-D) or multidimensional space. Given 2-D square space with the resolution of n∗n divided into 2N ∗ 2N, n = 2N equal-sized cells, the N-order Hilbert curve recursively resolves the space into four equal-sized blocks by a defined way. For the N-order Hilbert curve, the iterative process is described as four subblocks that are replicated and partitioned after rotation and reflection from the (N-1)-order curve blocks.According to the order of the curve traverses, the sequence number for each cell is determined, which ranges from 0 to22N−1. The integer value associated with each cell is denoted as the Hilbert value (H-value). For example, Figure 1 shows the 2-order Hilbert curve goes through 22∗22 cells in the given space, and each cell is given a sequence number (H-value). The Hilbert curve is often used as one of the space transformation tools, transforming a 2-D space point into 1-D H-value. Similar to our previous work [3], we present each cell in the given square space by a grid coordinate <X, Y>, and the corresponding Hilbert value of each cell can be determined by a Hilbert curve.Figure 1
Hilbert curve: (a) 1-order; (b) 2-order.
(a)(b)Definition 1.
Given a Hilbert curve visiting each cell in a 2-D square space, the grid coordinate of a cellc<Xc,Yc> can be transformed to 1-D Hilbert value by a function f· as follows:(1)Hc=f·Xc,Yc,where f· is the spatial transformation function and 0≤Xc,Yc≤2N−1,0≤Hc≤22N−1. Once the Hilbert curve setting parameters are determined, the generated H-values mapping to all cell are assigned. The setting parameters in the generating algorithm refer to the curve’s starting point <Xo, Yo>, curve order N, curve orientation Γ, and curve scale factor Θ. We term this parameter as spatial transformation parameter (STP), STP=Xo,Yo,N,Γ,Θ. In our example, in Figure 1, users a, b, c, and d are with the grid coordinates of 1,0,2,0,1,2,​and2,2. As the 2-order Hilbert curve orderly visits each cell, generated Hilbert values of these users are 1, 14, 7, and 8, respectively.
In our study, we use the Hilbert curve to transform the user’s real location for the purpose of privacy preservation. From the security aspect, the space transformation functionf· should be a one-way function, which is presented that it is easy to encode the elements of two-dimension space and generate one-dimension H-value but difficult to decode the one-dimension H-value back to the original space. The Hilbert curve has the above features and is suitable for our scheme. For an adversary without the STP, it is computationally impossible [15, 16] to reverse the function f·−1 and determine the correct Hilbert curve by comparing the H-values for all original spaces.


### 2.2. Order-Preserving Encryption

Order-preserving encryption (OPE) [17–20] is a deterministic symmetric encryption scheme which preserves the sort order of plaintexts in the ciphertexts. This character makes OPE very useful when performing range queries on encrypted data. It allows a remote untrusted database server to index the encrypted data and directly performs range queries without decrypting the ciphertexts [21] (returning a result in the database whose decryptions fall within a specified range, e.g., [a, b]).Definition 2.
Order-preserving function. For anyA,B⊂N, |A| < |B|,function f:A⟶B is order preserving, if for all i,j∈A, fi>fj, and only if i > j.Definition 3.
Order-preserving encryption. A deterministic encryption schemeSε=K,E⋅,D⋅, with associated plaintext-space D, ciphertext-space ℛ, and encryption key-space K, for all K, if E(·) is an order-preserving function from D to ℛ, the deterministic encryption scheme Sε=K,E⋅,D⋅ is order preserving.
The OPE-based scheme in our system consists of the following algorithms, whereEncL and EncR are interactive, KeyGen is probabilistic, and the rest are deterministic:
Key Generation: KeyGen1k⟶SK. The KeyGen runs on the user side, it takes the security parameters k as input and outputs a secret key SK.
Location Encryption: EncLl,SK⟶l′. Given a location point l, the user outputs the ciphertext l′ with the secret key SK.
Range Encryption: EncRR,SK⟶R′. Given a 2-element vector R, R = l1,l2, the user outputs the ciphertext R′with the secret key SK.
Decryption: Decl′,SK⟶l. Dec is a decryption algorithm taking the ciphertext l′ and secret key SK as inputs and outputs the plaintext l.
Detection: DetR,l′⟶0,1. It takes the ciphertext R′ and l′ as inputs, performs the vicinity detection, and outputs 1 if l falls into the range R, otherwise, it outputs 0.


## 2.1. Hilbert Curve

The Hilbert curve is a space-filling curve [15], which visits each point once and once only in a specified order by some algorithms in 2-dimensional (2-D) or multidimensional space. Given 2-D square space with the resolution of n∗n divided into 2N ∗ 2N, n = 2N equal-sized cells, the N-order Hilbert curve recursively resolves the space into four equal-sized blocks by a defined way. For the N-order Hilbert curve, the iterative process is described as four subblocks that are replicated and partitioned after rotation and reflection from the (N-1)-order curve blocks.According to the order of the curve traverses, the sequence number for each cell is determined, which ranges from 0 to22N−1. The integer value associated with each cell is denoted as the Hilbert value (H-value). For example, Figure 1 shows the 2-order Hilbert curve goes through 22∗22 cells in the given space, and each cell is given a sequence number (H-value). The Hilbert curve is often used as one of the space transformation tools, transforming a 2-D space point into 1-D H-value. Similar to our previous work [3], we present each cell in the given square space by a grid coordinate <X, Y>, and the corresponding Hilbert value of each cell can be determined by a Hilbert curve.Figure 1
Hilbert curve: (a) 1-order; (b) 2-order.
(a)(b)Definition 1.
Given a Hilbert curve visiting each cell in a 2-D square space, the grid coordinate of a cellc<Xc,Yc> can be transformed to 1-D Hilbert value by a function f· as follows:(1)Hc=f·Xc,Yc,where f· is the spatial transformation function and 0≤Xc,Yc≤2N−1,0≤Hc≤22N−1. Once the Hilbert curve setting parameters are determined, the generated H-values mapping to all cell are assigned. The setting parameters in the generating algorithm refer to the curve’s starting point <Xo, Yo>, curve order N, curve orientation Γ, and curve scale factor Θ. We term this parameter as spatial transformation parameter (STP), STP=Xo,Yo,N,Γ,Θ. In our example, in Figure 1, users a, b, c, and d are with the grid coordinates of 1,0,2,0,1,2,​and2,2. As the 2-order Hilbert curve orderly visits each cell, generated Hilbert values of these users are 1, 14, 7, and 8, respectively.
In our study, we use the Hilbert curve to transform the user’s real location for the purpose of privacy preservation. From the security aspect, the space transformation functionf· should be a one-way function, which is presented that it is easy to encode the elements of two-dimension space and generate one-dimension H-value but difficult to decode the one-dimension H-value back to the original space. The Hilbert curve has the above features and is suitable for our scheme. For an adversary without the STP, it is computationally impossible [15, 16] to reverse the function f·−1 and determine the correct Hilbert curve by comparing the H-values for all original spaces.


## 2.2. Order-Preserving Encryption

Order-preserving encryption (OPE) [17–20] is a deterministic symmetric encryption scheme which preserves the sort order of plaintexts in the ciphertexts. This character makes OPE very useful when performing range queries on encrypted data. It allows a remote untrusted database server to index the encrypted data and directly performs range queries without decrypting the ciphertexts [21] (returning a result in the database whose decryptions fall within a specified range, e.g., [a, b]).Definition 2.
Order-preserving function. For anyA,B⊂N, |A| < |B|,function f:A⟶B is order preserving, if for all i,j∈A, fi>fj, and only if i > j.Definition 3.
Order-preserving encryption. A deterministic encryption schemeSε=K,E⋅,D⋅, with associated plaintext-space D, ciphertext-space ℛ, and encryption key-space K, for all K, if E(·) is an order-preserving function from D to ℛ, the deterministic encryption scheme Sε=K,E⋅,D⋅ is order preserving.
The OPE-based scheme in our system consists of the following algorithms, whereEncL and EncR are interactive, KeyGen is probabilistic, and the rest are deterministic:
Key Generation: KeyGen1k⟶SK. The KeyGen runs on the user side, it takes the security parameters k as input and outputs a secret key SK.
Location Encryption: EncLl,SK⟶l′. Given a location point l, the user outputs the ciphertext l′ with the secret key SK.
Range Encryption: EncRR,SK⟶R′. Given a 2-element vector R, R = l1,l2, the user outputs the ciphertext R′with the secret key SK.
Decryption: Decl′,SK⟶l. Dec is a decryption algorithm taking the ciphertext l′ and secret key SK as inputs and outputs the plaintext l.
Detection: DetR,l′⟶0,1. It takes the ciphertext R′ and l′ as inputs, performs the vicinity detection, and outputs 1 if l falls into the range R, otherwise, it outputs 0.


## 3. Overview of the System

The main idea of our scheme is to enable users to share location information and to find their nearby friends in a flexible and privacy-preserving way. Each useru in the system determines his current location (e.g., longitude and latitude) by a GPS-equipped device, which is a point in Euclidean space, presented by a 2-tuple value xu,yu∈R. The distance between the user u and other mobile users, e.g., v is duv, duv=xu−xv2+yu−yv2. The user u in the system can specify a vicinity region, and we use the minimum bounding rectangle (MBR) to cover this region and determine it by the diagonal xVmin,yVmin,xVmax,yVmax.The mobile useru can invite his friends v to join a friend group FGu, and the invited user v may either accept or decline to join FGu. If v accepts, the friendship relation F between u and v will be built as u,v∈F. In the same way, if user u is a friend of v, then users u and v are friends, and u,v,v,u⊆F. The user u can manage the members of FGu, and SP will maintain the friend list for him. The summary of notations used in the system is illustrated in Table 1.Table 1
Summary of notations.
NotationDescriptionxu,yuPoint coordinate of useruXu,YuGrid coordinate of useruxuo,yuoOrigin of the grid useru locatedxuf,yufOffset to the ordinate origin of useruGuGrid identification number of the useruH (u)Hilbert value of the cell useru locatedXo,YoStarting point of Hilbert curve


### 3.1. System Model

The system architecture of the ULSS scheme is shown in Figure2, which consists of the service provider, location-based social network server (LBSNS), and users. In the system model for our proposed protocol, the mobile user can be a request initiator or a participant (location provider). For ease of explanation, in the set of users, we assume Alice is the request initiator, and one of her friends Bob is the participant.Figure 2
System architecture of ULSS scheme.The mobile user Alice is an initiator who intends to share her real-time location in the MSNs and request the server for the proximity detection service. To preserve location privacy, Alice preprocesses the privacy information using the preloaded modules on her mobile device and then submits the encrypted location information to the server. Alice maintains different location policies according to the various contextual conditions, including the coarse granularity location privacy-preserving policyPa and fine granularity location privacy-preserving policy Pb. With Pa, Alice can receive a user list from the server, and it shows the friends who are located over a large vicinity area (like a city) designated by her. Then, referring to some specified users on the received list, with Pb, Alice may query if they are in the nearby vicinity region (like around 2 km). The participant Bob is a friend of Alice. Bob follows the proposed protocol and the privacy policy of Alice. In the whole process, Bob only provides his encrypted location to the social network and preserves his real location information against to any other third party.The service provider is a server in MSNs, which is an untrusted entity. Unlike the previous systems in [11, 22], which deploy the social network server and location server separately, in our architecture, the SP is an integrated server LBSNS. It provides users with two kinds of services, location-based services, and social network services. LBSNS achieves integrated service delivery, such as storing users’ information and maintaining user friend list and offering dynamic user data update and adjustment. The LBSNS conducts proximity detection based on the encrypted locations of user and his friends and returns the results to mobile users based on their privacy-preserving policy.


### 3.2. Security Assumption

There are generally external attack and internal attack for the threat model [23]. The former is caused by unauthorized outsiders, and the latter is initiated by internal participant (for example, the users and LBSNS in our system). We assume the communication channels be secure by standard security schemes (such as SSL and SSH) or using cryptographic methods to resist internal attacks [24–26]. In the ULSS scheme, we consider only internal attack and assume conventional threat model in our system as follows: we consider the dishonest mobile users try to obtain other users’ information outside the scope of the authorized access privileges. For example, Alice learns the exact location of Bob; Bob obtains the vicinity area or exact location of Alice. The untrusted mobile users may use some tools to forge their location, such attacks can be detected as presented in [27]. Besides, the LBSNS is assumed to be “honest but curious” by honestly following the proposed protocol in general but being curious about the content of queries, like the exact location and the real identity of users. In our system, LBSNS integrates location-based services and social network services on one server, which stores the information of all users, and social relationship network of them as well. In the ULSS scheme, all entities (including users and LBSNS) are assumed to be potential adversaries. The main security goal of our proposed scheme is to preserve user’s location privacy against to all participants. In addition, the collusion between the malicious users and LBSNS is not allowed in our proposed ULSS scheme.


## 3.1. System Model

The system architecture of the ULSS scheme is shown in Figure2, which consists of the service provider, location-based social network server (LBSNS), and users. In the system model for our proposed protocol, the mobile user can be a request initiator or a participant (location provider). For ease of explanation, in the set of users, we assume Alice is the request initiator, and one of her friends Bob is the participant.Figure 2
System architecture of ULSS scheme.The mobile user Alice is an initiator who intends to share her real-time location in the MSNs and request the server for the proximity detection service. To preserve location privacy, Alice preprocesses the privacy information using the preloaded modules on her mobile device and then submits the encrypted location information to the server. Alice maintains different location policies according to the various contextual conditions, including the coarse granularity location privacy-preserving policyPa and fine granularity location privacy-preserving policy Pb. With Pa, Alice can receive a user list from the server, and it shows the friends who are located over a large vicinity area (like a city) designated by her. Then, referring to some specified users on the received list, with Pb, Alice may query if they are in the nearby vicinity region (like around 2 km). The participant Bob is a friend of Alice. Bob follows the proposed protocol and the privacy policy of Alice. In the whole process, Bob only provides his encrypted location to the social network and preserves his real location information against to any other third party.The service provider is a server in MSNs, which is an untrusted entity. Unlike the previous systems in [11, 22], which deploy the social network server and location server separately, in our architecture, the SP is an integrated server LBSNS. It provides users with two kinds of services, location-based services, and social network services. LBSNS achieves integrated service delivery, such as storing users’ information and maintaining user friend list and offering dynamic user data update and adjustment. The LBSNS conducts proximity detection based on the encrypted locations of user and his friends and returns the results to mobile users based on their privacy-preserving policy.


## 3.2. Security Assumption

There are generally external attack and internal attack for the threat model [23]. The former is caused by unauthorized outsiders, and the latter is initiated by internal participant (for example, the users and LBSNS in our system). We assume the communication channels be secure by standard security schemes (such as SSL and SSH) or using cryptographic methods to resist internal attacks [24–26]. In the ULSS scheme, we consider only internal attack and assume conventional threat model in our system as follows: we consider the dishonest mobile users try to obtain other users’ information outside the scope of the authorized access privileges. For example, Alice learns the exact location of Bob; Bob obtains the vicinity area or exact location of Alice. The untrusted mobile users may use some tools to forge their location, such attacks can be detected as presented in [27]. Besides, the LBSNS is assumed to be “honest but curious” by honestly following the proposed protocol in general but being curious about the content of queries, like the exact location and the real identity of users. In our system, LBSNS integrates location-based services and social network services on one server, which stores the information of all users, and social relationship network of them as well. In the ULSS scheme, all entities (including users and LBSNS) are assumed to be potential adversaries. The main security goal of our proposed scheme is to preserve user’s location privacy against to all participants. In addition, the collusion between the malicious users and LBSNS is not allowed in our proposed ULSS scheme.


## 4. System Design

In this section, we first present the user registration and then describe the user location representation and update. In our system, according to user-defined location privacy-preserving policies, we use different methods to perform proximity detection: coarse-grained proximity detection and user-defined nearby friend detection as described in this section.


### 4.1. Registration

Before each user enjoys the location-sharing services in the social network, he should first register with hisIDU on the LBSNS, who verifies and maintains the uniqueness of the ID. Generally, users can use pseudonyms in the registration for safety considerations. The initiator Alice builds a friend groupFGA by inviting her friends to join in. The LBSNS will generate a group ID (like a random 256-bit-string) for the FGA, storing the user list of it. Alice can classify the users on the list into several subgroups, like colleagues, families, classmates, and so on, defined as C1,C2,…Cn,FGA=C1,C2,…Cn The LBSNS creates a friend relationship network for each user and updates dynamically and maintains the information of friend list as requested by users.Each user should set a distance thresholdDsu to preserve the location privacy during the application’s initialization phase. Dsu defines a minimum distance with which the user u allows his friends to search him. Otherwise, a user would be precisely located by the adversary continually reducing the range of vicinity detection. For example, Alice finds Bob somewhere around her by the vicinity detection service, and she can obtain the accurate location information of Bob according to continuous queries, such as by returning results when the range is set to 2 km, 1 km, 500 m, and so on. The SP will build a profile Pr for each user to keep these settings, e.g., for Alice, Pra = (IDA,PSWA∗, FGA, DSA}, where IDA is the ID of Alice, PSWA∗ is the ciphertext of the password, FGA is the friend group of Alice, and DSA is the distance threshold. The ULSS scheme allows users to customize and personalize their profiles to satisfy different users’ needs.


### 4.2. Location Representation and Update

Each useru obtains his location in the forms of latitude-longitude by the GPS latu,lonu. The ULSS scheme enables the user to transform his location by the Hilbert curve method as described in Section 2. Thus, the system first assigns a space range, where mapping the geolocation into a coordinate point denoted by xu,yu∈ℛ in Euclidean space. For example, the system can define the square scale using the longitude and latitude of 4 points of east, west, north, and south. As shown in Figure 1, the given space range is divided into 2N ∗ 2N equal-size cells and formed a grid system. Each grid in the space is numbered uniquely from ℕ. To protect the location privacy, each user in the ULSS scheme transforms his location coordinate xu,yu into two parts. The first part xuo,yuo is the origin coordinate of the grid where he is located in the grid system, the second part xuf,yuf is the offset coordinate in the grid, and xu=xuo+xuf,yu=yuo+yuf. We assume that the location coordinate range is separated into N scale levels, the coordinates of a user can be represented as Guxuf,yuf. Here Gu is the grid identification number of the user u in the N-th scale level, and 0≤Gu≤22N−1, xuf,yuf is the offset coordinates in the corresponding grid. In the ULSS scheme, if the transformation parameter STP is defined, the H-values mapping to all cell are assigned, which means the Gu can be obtained by the H-value according to equation (1).In general, if a user’s motion or movement trajectory is in a small range (e.g., in a city), the origin coordinates of the grid in the given space are not changed, and the user can specify a time interval with which the user automatically updates his offset coordinate. While user traverses a large area, e.g., traverse different grids in the grid system, the changes in offset coordinates exceed a certain degree (e.g., greater than the unit length of a grid), and the user should recalculate his locationGuxuf,yuf and submit related information to the server. In this way, we can reduce the computation and communication overheads for the user and improve the performance of the whole system.


### 4.3. Coarse-Grained Proximity Detection

In this phase, a user queries an LBSNS and gets the results showing friends in the coarse-grained vicinity area (such as in the same city). The main idea of coarse-grained proximity detection is to utilize the Hilbert curve method to transform user’s location and the coordinates of vicinity. The scheme cloaks user and his vicinity by mapping 2-D points into identification numbers in corresponding scale level which can be presented byH-value under given STP. The LBSNS provides results by comparing the hash values of all values submitted by mobile users. The processes are shown in Figure 3, and the detailed steps are as follows:Step 1. When the user Alice logs onto the system and wants to view the friends who are located in the coarse-grained vicinity area, she can submit a queryQA = {IDA, listA, N} to the SP, where IDA is the login ID of Alice, which can be pseudonymous; listA is the user list in the friend group specified by Alice, which can be a classification of his friends. Actually, Alice can search several classifications in his friend group FGA, like {Ci, Ci+1,…,Cj}, 1 < i, j < n, for simplicity, and we denote it by listA. According to the coarse granularity location privacy-preserving policy Pa, Alice sets the granularity N. For example, Alice wants to search the friends in the listA who are located over a large vicinity area, e.g., the same city she stays. In the given space range, Alice assigns the appropriate granularity N so that the vicinity can be presented by a grid number in the Hilbert transformation. In the Hilbert STP, N is the scale level 1≤N≤16. Generally, the larger the N, the bigger the vicinity area.Step 2. Receiving upon the request from an initiator Alice, the LBSNS generates the STP according to the Hilbert curve method for users. In the STP, the scale levelN is defined by Alice. The system determines longitude and latitude coordinate ranges as curve scale factor Θ, mapping it to the points in the given space range. In this way, the given 2-D space can be transformed to be a grid system with the equal size of 2N ∗ 2N grids. Then, the SP randomly selects the curve’s starting point <Xo, Yo>, and curve orientation Γ to build the STP and determine the Hilbert curve. Next, the LBSNS searches the friend list according to the listA submitted by Alice and distributes the generated STP to Alice and users on the list.Step 3. When receiving STP, each user transforms his location point (xu, yu) to Guxuf,yuf, and the process is as follows: Alice first maps her point location in Euclidean space (xa, ya) into the 2N ∗ 2N grids system <X, Y>. For example, if the square space range Θ is determined by 4 points of east, west, north, and south, (xE, yE), (xW, yW), (xN, yN), and (xS, yS), the unit length Unit of each grid can be presented by (xW—xE)/2N or (yS—yN)/2N. With the site (xa, ya), Alice can locate her grid coordinates <Xa, Ya> in the grid system by calculating Xa = [(xW—xa)/Unit] andYa = [(ya—yS)/Unit] and also gets the offsets xaf,yaf in the corresponding grid. Then, she transforms the grid coordinates <Xa, Ya> to a Hilbert value H(a) using equation (1) by the determined STP. Now Alice obtains the G(a) and can transform her location (xa, ya) into Gaxaf,yaf. In order to prevent other entity getting real location information, Alice submits the hash value of it, hash(Ga), to the LBSNS, where hash(·) is a collision-resistant hash function. In this way, Alice cloaks her exact location into a region, presented by hash(Ga). The friends of Alice, e.g., Bob also transforms his locations and sends the hash(Gb) to the LBSNS in the same way.Step 4. The LBSNS collects the transformed location information from Alice and her friends. Then, it searches the users who have the samehash(Gu) as Alice and returns the neighboring users located in the vicinity to Alice under the coarse-grained setting Pa.Figure 3
Processes in the ULSS scheme.


### 4.4. User-Defined Nearby Friend Detection

When Alice receives the results of the coarse-grained proximity detection from LBSNS, she can further select some specified users she has interest to perform nearby friend detection under the fine granularity policyPb. For example, referring to some particular users on the received list, presented by listB, Alice may query if they are in the nearby vicinity region (like around 2 km). Note that the neighborhood range in this phase can be customized arbitrarily by Alice under the constrain conditions of security assumption. We intend to use lightweight OPE technology to implement the user-defined nearby friend detection, and the processes are as follows:Step 1. Alice generates an encryption keySK according to the OPE key generation algorithm KeyGen1k⟶SK and shares the key through the secure channel to the friends to be queried.Step 2. Alice customizes a neighborhood range to retrieve the nearby friends. For example, the range around herA meters or the range with A and B meters in the x-axis and y-axis directions. The scheme generates a rectangle R to cover this range, R = rl,ru, where rl = (xa − A, ya − B) and ru = (xa + A, ya + B) denote the lower-left corner and upper-right corner of the vicinity range R, respectively. Notice that, here we use the offset coordinates in the corresponding grid to present the vicinity R. Then, Alice encrypts R, by EncRR,SK⟶R′.Step 3. When a specific user Bob receives the request, he encrypts his own location before submitting. The location point of Boblb is presented by Gbxbf,ybf. Here, Bob only needs to send his encrypted offset coordinates to further ensure the safety of his data. In this way, even some malicious attacker can decrypt the ciphertext, he has no way to obtain the real lb without Gb. If we denote the offset coordinates of Bob by Olb, Bob inputs it to the encryption function EncLOlb,SK⟶Olb′ and submits Olb′ to the LBSNS to avoid potential security risks from trusted third party (TTP) free server.Step 4. LBSNS performs the range query on the ciphertexts directly and returns the results whetherl′ falls into the associated range by DetR′,l′⟶0,1. LBSNS collects the information from all users of listB conducting the proximity detection and returns those who is in the nearby vicinity R to Alice.


## 4.1. Registration

Before each user enjoys the location-sharing services in the social network, he should first register with hisIDU on the LBSNS, who verifies and maintains the uniqueness of the ID. Generally, users can use pseudonyms in the registration for safety considerations. The initiator Alice builds a friend groupFGA by inviting her friends to join in. The LBSNS will generate a group ID (like a random 256-bit-string) for the FGA, storing the user list of it. Alice can classify the users on the list into several subgroups, like colleagues, families, classmates, and so on, defined as C1,C2,…Cn,FGA=C1,C2,…Cn The LBSNS creates a friend relationship network for each user and updates dynamically and maintains the information of friend list as requested by users.Each user should set a distance thresholdDsu to preserve the location privacy during the application’s initialization phase. Dsu defines a minimum distance with which the user u allows his friends to search him. Otherwise, a user would be precisely located by the adversary continually reducing the range of vicinity detection. For example, Alice finds Bob somewhere around her by the vicinity detection service, and she can obtain the accurate location information of Bob according to continuous queries, such as by returning results when the range is set to 2 km, 1 km, 500 m, and so on. The SP will build a profile Pr for each user to keep these settings, e.g., for Alice, Pra = (IDA,PSWA∗, FGA, DSA}, where IDA is the ID of Alice, PSWA∗ is the ciphertext of the password, FGA is the friend group of Alice, and DSA is the distance threshold. The ULSS scheme allows users to customize and personalize their profiles to satisfy different users’ needs.


## 4.2. Location Representation and Update

Each useru obtains his location in the forms of latitude-longitude by the GPS latu,lonu. The ULSS scheme enables the user to transform his location by the Hilbert curve method as described in Section 2. Thus, the system first assigns a space range, where mapping the geolocation into a coordinate point denoted by xu,yu∈ℛ in Euclidean space. For example, the system can define the square scale using the longitude and latitude of 4 points of east, west, north, and south. As shown in Figure 1, the given space range is divided into 2N ∗ 2N equal-size cells and formed a grid system. Each grid in the space is numbered uniquely from ℕ. To protect the location privacy, each user in the ULSS scheme transforms his location coordinate xu,yu into two parts. The first part xuo,yuo is the origin coordinate of the grid where he is located in the grid system, the second part xuf,yuf is the offset coordinate in the grid, and xu=xuo+xuf,yu=yuo+yuf. We assume that the location coordinate range is separated into N scale levels, the coordinates of a user can be represented as Guxuf,yuf. Here Gu is the grid identification number of the user u in the N-th scale level, and 0≤Gu≤22N−1, xuf,yuf is the offset coordinates in the corresponding grid. In the ULSS scheme, if the transformation parameter STP is defined, the H-values mapping to all cell are assigned, which means the Gu can be obtained by the H-value according to equation (1).In general, if a user’s motion or movement trajectory is in a small range (e.g., in a city), the origin coordinates of the grid in the given space are not changed, and the user can specify a time interval with which the user automatically updates his offset coordinate. While user traverses a large area, e.g., traverse different grids in the grid system, the changes in offset coordinates exceed a certain degree (e.g., greater than the unit length of a grid), and the user should recalculate his locationGuxuf,yuf and submit related information to the server. In this way, we can reduce the computation and communication overheads for the user and improve the performance of the whole system.


## 4.3. Coarse-Grained Proximity Detection

In this phase, a user queries an LBSNS and gets the results showing friends in the coarse-grained vicinity area (such as in the same city). The main idea of coarse-grained proximity detection is to utilize the Hilbert curve method to transform user’s location and the coordinates of vicinity. The scheme cloaks user and his vicinity by mapping 2-D points into identification numbers in corresponding scale level which can be presented byH-value under given STP. The LBSNS provides results by comparing the hash values of all values submitted by mobile users. The processes are shown in Figure 3, and the detailed steps are as follows:Step 1. When the user Alice logs onto the system and wants to view the friends who are located in the coarse-grained vicinity area, she can submit a queryQA = {IDA, listA, N} to the SP, where IDA is the login ID of Alice, which can be pseudonymous; listA is the user list in the friend group specified by Alice, which can be a classification of his friends. Actually, Alice can search several classifications in his friend group FGA, like {Ci, Ci+1,…,Cj}, 1 < i, j < n, for simplicity, and we denote it by listA. According to the coarse granularity location privacy-preserving policy Pa, Alice sets the granularity N. For example, Alice wants to search the friends in the listA who are located over a large vicinity area, e.g., the same city she stays. In the given space range, Alice assigns the appropriate granularity N so that the vicinity can be presented by a grid number in the Hilbert transformation. In the Hilbert STP, N is the scale level 1≤N≤16. Generally, the larger the N, the bigger the vicinity area.Step 2. Receiving upon the request from an initiator Alice, the LBSNS generates the STP according to the Hilbert curve method for users. In the STP, the scale levelN is defined by Alice. The system determines longitude and latitude coordinate ranges as curve scale factor Θ, mapping it to the points in the given space range. In this way, the given 2-D space can be transformed to be a grid system with the equal size of 2N ∗ 2N grids. Then, the SP randomly selects the curve’s starting point <Xo, Yo>, and curve orientation Γ to build the STP and determine the Hilbert curve. Next, the LBSNS searches the friend list according to the listA submitted by Alice and distributes the generated STP to Alice and users on the list.Step 3. When receiving STP, each user transforms his location point (xu, yu) to Guxuf,yuf, and the process is as follows: Alice first maps her point location in Euclidean space (xa, ya) into the 2N ∗ 2N grids system <X, Y>. For example, if the square space range Θ is determined by 4 points of east, west, north, and south, (xE, yE), (xW, yW), (xN, yN), and (xS, yS), the unit length Unit of each grid can be presented by (xW—xE)/2N or (yS—yN)/2N. With the site (xa, ya), Alice can locate her grid coordinates <Xa, Ya> in the grid system by calculating Xa = [(xW—xa)/Unit] andYa = [(ya—yS)/Unit] and also gets the offsets xaf,yaf in the corresponding grid. Then, she transforms the grid coordinates <Xa, Ya> to a Hilbert value H(a) using equation (1) by the determined STP. Now Alice obtains the G(a) and can transform her location (xa, ya) into Gaxaf,yaf. In order to prevent other entity getting real location information, Alice submits the hash value of it, hash(Ga), to the LBSNS, where hash(·) is a collision-resistant hash function. In this way, Alice cloaks her exact location into a region, presented by hash(Ga). The friends of Alice, e.g., Bob also transforms his locations and sends the hash(Gb) to the LBSNS in the same way.Step 4. The LBSNS collects the transformed location information from Alice and her friends. Then, it searches the users who have the samehash(Gu) as Alice and returns the neighboring users located in the vicinity to Alice under the coarse-grained setting Pa.Figure 3
Processes in the ULSS scheme.


## 4.4. User-Defined Nearby Friend Detection

When Alice receives the results of the coarse-grained proximity detection from LBSNS, she can further select some specified users she has interest to perform nearby friend detection under the fine granularity policyPb. For example, referring to some particular users on the received list, presented by listB, Alice may query if they are in the nearby vicinity region (like around 2 km). Note that the neighborhood range in this phase can be customized arbitrarily by Alice under the constrain conditions of security assumption. We intend to use lightweight OPE technology to implement the user-defined nearby friend detection, and the processes are as follows:Step 1. Alice generates an encryption keySK according to the OPE key generation algorithm KeyGen1k⟶SK and shares the key through the secure channel to the friends to be queried.Step 2. Alice customizes a neighborhood range to retrieve the nearby friends. For example, the range around herA meters or the range with A and B meters in the x-axis and y-axis directions. The scheme generates a rectangle R to cover this range, R = rl,ru, where rl = (xa − A, ya − B) and ru = (xa + A, ya + B) denote the lower-left corner and upper-right corner of the vicinity range R, respectively. Notice that, here we use the offset coordinates in the corresponding grid to present the vicinity R. Then, Alice encrypts R, by EncRR,SK⟶R′.Step 3. When a specific user Bob receives the request, he encrypts his own location before submitting. The location point of Boblb is presented by Gbxbf,ybf. Here, Bob only needs to send his encrypted offset coordinates to further ensure the safety of his data. In this way, even some malicious attacker can decrypt the ciphertext, he has no way to obtain the real lb without Gb. If we denote the offset coordinates of Bob by Olb, Bob inputs it to the encryption function EncLOlb,SK⟶Olb′ and submits Olb′ to the LBSNS to avoid potential security risks from trusted third party (TTP) free server.Step 4. LBSNS performs the range query on the ciphertexts directly and returns the results whetherl′ falls into the associated range by DetR′,l′⟶0,1. LBSNS collects the information from all users of listB conducting the proximity detection and returns those who is in the nearby vicinity R to Alice.


## 5. Security Analysis

The ULSS scheme uses the Hilbert curve method to perform coarse-grained proximity detection and utilizes the OPE method to conduct user-defined nearby friend detection. We give the security analysis for these two technologies. The security assumption and requirements are described in Section3.2.


### 5.1. Hilbert Curve Transformation

In general, the privacy protection methods in most literatures are public, and the technology of Hilbert curve in the ULSS scheme may be obtained by some adversaries. Once an attacker learns some background knowledge of the users’ original locations or their transformed locations, they may guess the secret key (e.g., STP in the ULSS scheme) with a certain probability. However, some researchers in [15, 16, 28] stated that it is computably impossible to get the correct STP by comparing H values of all locations, and it can resist brute force attacks.Brute-Force Attack. In STP, we represent curve’s orientation Γ in terms of q bits, and it will generate 2q values in the entire 360° space. The malicious adversary needs to make 2q attempts to determine the right Γ. Refer to the curve’s starting point X0,Y0, and we represent the value with q bit data, respectively. To search for the correct X0,Y0 over 2q∗2q elements, it requires the adversary to try 2q∗2q candidate coordinate values on the X and Y axes. In our scheme, the square space range Θ is fixed value, and the order of the Hilbert curve N is determined by users. Therefore, we have N∗2q∗2q∗2q solutions for the entire space, where q is the number of bits presenting each parameter of STP. N is the order of the Hilbert curve, and 1≤N<16. If the value of q is big enough, the possibility of getting the correct STP by trying combinations of parameters is negligible. For example, if q = 32, the complexity of exhaustive search for the STP would be O23∗32.Therefore, for anyone without the STP, it is computationally impossible to reverse the process of the spatial transformation and get the users’ original locations. The one-way mapping of the Hilbert curve makes the transformation functionf•Xc,Yc be a secure encryption function [15, 16]. Any adversary has no way to learn the user’s real location without the encryption key STP. We can say that the Hilbert curve transformation is a very appropriate approach to preserve user location privacy in our ULSS scheme.


### 5.2. Security of Order-Preserving Encryption

The researchers in [29, 30] formalized a security requirement for OPE and proposed an efficient blockcipher-based scheme provably meeting their security definition. The OPE scheme has been proven [29] that it is security under distinct chosen-plaintext attack (IND-DCPA). Popa et al. [31] presented that the ideal security guarantee for order-preserving encryption is to reveal no additional information about the plaintext values besides their order. They proposed an ideal security protocol for OPE, which can achieve indistinguishability under ordered chosen-plaintext attack (IND-OCPA) security. The ULSS scheme utilizes the OPE method to conduct user-defined nearby friend detection. Alice and her friends hold the secret key SK, derived from the security of the OPE scheme, and any other entities including the LBSNS without the key cannot get the real location of users. Therefore, the security of user-defined nearby friend detection in the ULSS scheme can be achieved from that of the OPE scheme.


## 5.1. Hilbert Curve Transformation

In general, the privacy protection methods in most literatures are public, and the technology of Hilbert curve in the ULSS scheme may be obtained by some adversaries. Once an attacker learns some background knowledge of the users’ original locations or their transformed locations, they may guess the secret key (e.g., STP in the ULSS scheme) with a certain probability. However, some researchers in [15, 16, 28] stated that it is computably impossible to get the correct STP by comparing H values of all locations, and it can resist brute force attacks.Brute-Force Attack. In STP, we represent curve’s orientation Γ in terms of q bits, and it will generate 2q values in the entire 360° space. The malicious adversary needs to make 2q attempts to determine the right Γ. Refer to the curve’s starting point X0,Y0, and we represent the value with q bit data, respectively. To search for the correct X0,Y0 over 2q∗2q elements, it requires the adversary to try 2q∗2q candidate coordinate values on the X and Y axes. In our scheme, the square space range Θ is fixed value, and the order of the Hilbert curve N is determined by users. Therefore, we have N∗2q∗2q∗2q solutions for the entire space, where q is the number of bits presenting each parameter of STP. N is the order of the Hilbert curve, and 1≤N<16. If the value of q is big enough, the possibility of getting the correct STP by trying combinations of parameters is negligible. For example, if q = 32, the complexity of exhaustive search for the STP would be O23∗32.Therefore, for anyone without the STP, it is computationally impossible to reverse the process of the spatial transformation and get the users’ original locations. The one-way mapping of the Hilbert curve makes the transformation functionf•Xc,Yc be a secure encryption function [15, 16]. Any adversary has no way to learn the user’s real location without the encryption key STP. We can say that the Hilbert curve transformation is a very appropriate approach to preserve user location privacy in our ULSS scheme.


## 5.2. Security of Order-Preserving Encryption

The researchers in [29, 30] formalized a security requirement for OPE and proposed an efficient blockcipher-based scheme provably meeting their security definition. The OPE scheme has been proven [29] that it is security under distinct chosen-plaintext attack (IND-DCPA). Popa et al. [31] presented that the ideal security guarantee for order-preserving encryption is to reveal no additional information about the plaintext values besides their order. They proposed an ideal security protocol for OPE, which can achieve indistinguishability under ordered chosen-plaintext attack (IND-OCPA) security. The ULSS scheme utilizes the OPE method to conduct user-defined nearby friend detection. Alice and her friends hold the secret key SK, derived from the security of the OPE scheme, and any other entities including the LBSNS without the key cannot get the real location of users. Therefore, the security of user-defined nearby friend detection in the ULSS scheme can be achieved from that of the OPE scheme.


## 6. Evaluation

In this section, the efficiency and effectiveness of our ULSS scheme were evaluated by the extensive experiments. During the phase of coarse-grained proximity detection, we focus on the location transformation using the Hilbert curve method, which is mainly affected by the parameter of Hilbert orderN. During the phase of user-defined nearby friend detection, we focus on the location encryption by OPE, which is mainly affected by the size of data. We also conducted experiments to evaluate the computational and communication overheads of each entity under different system settings, like the size of vicinity s or number of friends n.All experiments were conducted on Java Development Kit (JDK).1.7 with the Intel (R) Core (TM) i7-7500U 2.70-GHz CPU and Win 10 OS. We used the 256-bit OPE symmetric encryption algorithm and 256-bit SHA hash function to ensure data confidentiality and integrity. The cryptographic algorithms were performed with JPBC library. In the experiments, we used the Web API of Amap [32] to get the GPS positioning by the function GetLongitudeAndLatitude and initialized the location of each user by calling function GetCurrentPosition. The studies utilize uniform data sets to randomly generate batches of 10,000 user locations and then map them into the points in a 65536 ∗ 65536 area in 2-D space. We assume each mobile user stores his friend list on the LBSNS, and each user has a maximum of 2,000 friends. Each mobile user can specify an arbitrary vicinity to search for his nearby friends. For the security and privacy issue, the minimum size of vicinity is set to 1 km2, and we got the average data from 20 experiment results.


### 6.1. Hilbert Curve Order

In the phase of coarse-grained proximity detection, Alice and her friends use the Hilbert curve to transform their exact locations into a cloaked region, presented by anH-value. The LBSNS gives the results of coarse-grained detection according to the hash values submitted by all users, and the computational overhead of the LBSNS is almost negligible. In this set of experiments, we mainly evaluated the processing time on the user side. When performing the Hilbert curve transformation, curve’s starting point is set to 0,0 and the curve orientation Γ is set to be clockwise, the square space range Θ is determined by 4 points of east, west, north, and south in China. Figure 4 shows the average computational cost during the location transformation with various Hilbert curve order N for the user. As shown by it, the computational processing time of the user slightly increases as N≤13, and the transformation time is no more than 0.2 second. In fact, in our ULSS scheme, if N≥16, the generated region is too small to cloak user’s exact location. Generally, in the initialization phase, we assign the value of N is no bigger than 15. After transformation, each user submits the hash value of his transformed location to the LBSNS to prevent the information leakage on the third entity. Table 2 shows that this operation completes within several milliseconds. Thus, in practical application of the scheme, for the user, we can say the Hilbert curve transformation is computationally efficient.Figure 4
Computational overhead of location transformation for the user.Table 2
Computational overhead of encryption and decryption.
Size (bytes)3264128102410 k1 MHash (ms)66891114Encryption (ms)1113211221362049Decryption (ms)10112913052243822


### 6.2. Encryption and Decryption

In the phase of user-defined nearby friend detection, we used the 256-bit OPE symmetric encryption algorithm to ensure the data confidentiality for users. Table2 shows the computational overheads of the encryption and decryption in various data sizes. In the ULSS scheme, the initiator Alice encrypts her vicinity range R, and her friend Bob encrypts his offset coordinates xbf,ybf, the size of them is no more than 64 bytes. For each user, we can see, from Table 2, the average processing time for the encryption is about 13 ms. For the LBSNS, it conducts the nearby friend detection directly on the ciphertexts since the OPE preserves the sort order of plaintexts in the ciphertexts. It means that, without decrypting any ciphertext, the LBSNS can return a result in the list whose decryptions fall within a specified range R. This process can be completed by comparing the value of ciphertexts, which ensures minimal overhead on the LBSNS.


### 6.3. Number of Friends

We gave an experiment to evaluate the efficiency of the ULSS scheme in terms of various parameters, e.g., number of friendsn and the size of vicinity s. We illustrated the experimental results by the computational time and traffic overheads from the Alice, Bob, and the LBSNS, respectively. We assumed Alice submits a coarse-grained proximity query to LBSNS, upon receiving the results, and she selected half of friends from the list to further put forward nearby friend query. In this process, we ignored the communication network transmission delay, as it was impacted by different network environments. Figure 5 shows the computational time of each entity in the scheme when the number of friends n changes from 20 to 2000, and we set the default vicinity was 2 km2. The processing time is 92–98 ms for Alice and 80–85 ms for Bob. While it grows for LBSNS with number of friends, because the server should handle the proximity detection requirement from each participant, the greater the number of friends is, the longer the time it takes. Similarly, LBSNS needs to distribute STP to Alice and her friends, and its communication cost grows linearly with n (as shown in Figure 6). During the phase of user-defined nearby friend detection, Alice should share the encryption key to her friends, the traffic also grows, and the communication cost of Bob maintains at a very low level.Figure 5
Computational overhead with various numbers of friends.Figure 6
Communication cost with various number of friends.


### 6.4. Size of Vicinity

In this set of experiments, the computational and communication cost of each entity in the ULSS scheme is evaluated when the size of vicinitys changes from 1 km2 to 20 km2. We assumed Alice first specified the Hilbert order to 5, when she got the results in the coarse-grained region, she defined a nearby vicinity (the size is s) to search for proximity friend. Figures 7 and 8 show that the computation and communication overheads for Alice, and SP slightly grow with increasing vicinity area, while it holds constant for Bob.Figure 7
Computational cost with various sizes of vicinity.Figure 8
Communication cost with various sizes of vicinity.


### 6.5. Comparison with Other Approaches and Discussion

We compared our proposed scheme with other similar approaches for a holistic evaluation of our system. Table3 shows the results in terms of TTP, server, cryptography method, and efficiency characteristics when comparing with approaches like MLS in 2017 [11], VPPLS in 2017 [13], and UDPLS in 2017 [22].Table 3
Comparison of our proposed with other protocols.
ProtocolTTPServerCryptographic methodsMLS [11]NoSeparately deployed LS and SNSAES and RSA signatureVPPLS [13]YesIntegrated LBSNSHomomorphic encryptionUDPLS [22]NoSeparately deployed LS and SNSAES and RSA signatureOur schemeNoIntegrated LBSNSOPEFrom the table, we find that some approaches, e.g., the VPPLS scheme, need a fully trusted third party (TTP) to verify the user ID and run some cryptographic computation. In the TTP-based schemes, the third party stores user’s sensitive information and some important information of the system, which may put the system in jeopardy if it is comprised. However, our scheme uses the location transformation and OPE method to protect user privacy getting rid of the introduction of TTP.Some exiting solutions, e.g., MLS and UPDLS, separately deploy two different servers including location server and social network server to store information and provide users two kinds of services, location-based services, and social network services. The main drawback of LBS/SNS separated architectures is the multiple-round interactions between the servers, which may incur higher communication cost and cause great computation and storage burden as well. In practice, mobile users can enjoy their online social network services by the wireless mobile network and, meanwhile, obtain their exact location information through the GPS equipped in the smart terminals. Nowadays, location sharing and services are important functions of MSNs, and integrating two kinds of services can bring more convenient and flexibility for users, which has become an indispensable tool of users’ daily life. In security aspect, in the LBS/SNS separated architectures, the user’s location information and user profiles are separately stored in two servers, and they are assumed to be no-collusion to guarantee the system safety. However, commonly, in some location-sharing scenarios, the location information can be easily captured by adversaries, if the server providers collude with them or collude with each other, the user privacy and system safety are insecure, which makes these distributed architectures unpractical in real life. In our model, these two kinds of servers are combined by one LBSNS, providing integrated service delivery.In terms of cryptographic methods, the VPPLS protocol used the homomorphic encryption method to compute the distance between Alice and her friends without disclosing the exact position to other party, and MLS and UDPLS rely on symmetric encryption AES and asymmetric encryption RSA signature to ensure the data integrity and confidentiality. These privacy preservation approaches can provide user location sharing privately and securely. However, the main concern is the heavy computing burden both on user and server sides when running the encryption algorithms. Different with the traditional encryption method, our scheme utilizes efficient OPE algorithm to protect user data, and the ULSS only needs to encrypt very small amount of user data, in our evaluation result, Table2 shows that user only takes several milliseconds to complete the encryption process. Besides, for the LBSNS, it can directly conduct the proximity detection by comparing the ciphertexts, without having to decrypt, which can greatly save the computing and communication resources. Thus, we can deduce that our scheme is more efficient.Discussion. In our proposed scheme, we presented two methods, Hilbert curve-based proximity detection method and lightweight order-preserving encryption- (OPE-) based method, to provide the users with flexible privacy preservation in an efficient and friendly way. The evaluation results of Hilbert curve transformation show that the processing time on the user side and server side is very small. And from the experiments with respect to order-preserving encryption, we can also find that the average processing time of users is several milliseconds. Meanwhile, due to OPE, the server can directly perform range queries without decrypting the ciphertext, which minimizes the overhead on it. Compared with the homomorphic encryption- (HE-) based method [13] and AES&RSA-based method [11, 22], we can state that our ULSS is more efficient and practical. From the aspect of security, in some existing solution, the privacy of users is guaranteed based on the assumption of fully trust in the service provider or TTP. However, the TTP-based structure results in trust issues, like the single-point failure and the bottle-neck problem of communications, and if the TTP is comprised, the security of the entire system is at risk. Our scheme is TTP-free architecture, which can protect user location privacy with respect to SP, friends, and other adversaries. We also prove that the proposed scheme is secure under the stronger security model with enhanced privacy. Moreover, unlike the multiserver structure in [11, 22], in our scheme, the LBS and SNS are integrated by one server to provide entire and convenient services, and it also can reduce communication and computational overheads and security risks as well.


## 6.1. Hilbert Curve Order

In the phase of coarse-grained proximity detection, Alice and her friends use the Hilbert curve to transform their exact locations into a cloaked region, presented by anH-value. The LBSNS gives the results of coarse-grained detection according to the hash values submitted by all users, and the computational overhead of the LBSNS is almost negligible. In this set of experiments, we mainly evaluated the processing time on the user side. When performing the Hilbert curve transformation, curve’s starting point is set to 0,0 and the curve orientation Γ is set to be clockwise, the square space range Θ is determined by 4 points of east, west, north, and south in China. Figure 4 shows the average computational cost during the location transformation with various Hilbert curve order N for the user. As shown by it, the computational processing time of the user slightly increases as N≤13, and the transformation time is no more than 0.2 second. In fact, in our ULSS scheme, if N≥16, the generated region is too small to cloak user’s exact location. Generally, in the initialization phase, we assign the value of N is no bigger than 15. After transformation, each user submits the hash value of his transformed location to the LBSNS to prevent the information leakage on the third entity. Table 2 shows that this operation completes within several milliseconds. Thus, in practical application of the scheme, for the user, we can say the Hilbert curve transformation is computationally efficient.Figure 4
Computational overhead of location transformation for the user.Table 2
Computational overhead of encryption and decryption.
Size (bytes)3264128102410 k1 MHash (ms)66891114Encryption (ms)1113211221362049Decryption (ms)10112913052243822


## 6.2. Encryption and Decryption

In the phase of user-defined nearby friend detection, we used the 256-bit OPE symmetric encryption algorithm to ensure the data confidentiality for users. Table2 shows the computational overheads of the encryption and decryption in various data sizes. In the ULSS scheme, the initiator Alice encrypts her vicinity range R, and her friend Bob encrypts his offset coordinates xbf,ybf, the size of them is no more than 64 bytes. For each user, we can see, from Table 2, the average processing time for the encryption is about 13 ms. For the LBSNS, it conducts the nearby friend detection directly on the ciphertexts since the OPE preserves the sort order of plaintexts in the ciphertexts. It means that, without decrypting any ciphertext, the LBSNS can return a result in the list whose decryptions fall within a specified range R. This process can be completed by comparing the value of ciphertexts, which ensures minimal overhead on the LBSNS.


## 6.3. Number of Friends

We gave an experiment to evaluate the efficiency of the ULSS scheme in terms of various parameters, e.g., number of friendsn and the size of vicinity s. We illustrated the experimental results by the computational time and traffic overheads from the Alice, Bob, and the LBSNS, respectively. We assumed Alice submits a coarse-grained proximity query to LBSNS, upon receiving the results, and she selected half of friends from the list to further put forward nearby friend query. In this process, we ignored the communication network transmission delay, as it was impacted by different network environments. Figure 5 shows the computational time of each entity in the scheme when the number of friends n changes from 20 to 2000, and we set the default vicinity was 2 km2. The processing time is 92–98 ms for Alice and 80–85 ms for Bob. While it grows for LBSNS with number of friends, because the server should handle the proximity detection requirement from each participant, the greater the number of friends is, the longer the time it takes. Similarly, LBSNS needs to distribute STP to Alice and her friends, and its communication cost grows linearly with n (as shown in Figure 6). During the phase of user-defined nearby friend detection, Alice should share the encryption key to her friends, the traffic also grows, and the communication cost of Bob maintains at a very low level.Figure 5
Computational overhead with various numbers of friends.Figure 6
Communication cost with various number of friends.


## 6.4. Size of Vicinity

In this set of experiments, the computational and communication cost of each entity in the ULSS scheme is evaluated when the size of vicinitys changes from 1 km2 to 20 km2. We assumed Alice first specified the Hilbert order to 5, when she got the results in the coarse-grained region, she defined a nearby vicinity (the size is s) to search for proximity friend. Figures 7 and 8 show that the computation and communication overheads for Alice, and SP slightly grow with increasing vicinity area, while it holds constant for Bob.Figure 7
Computational cost with various sizes of vicinity.Figure 8
Communication cost with various sizes of vicinity.


## 6.5. Comparison with Other Approaches and Discussion

We compared our proposed scheme with other similar approaches for a holistic evaluation of our system. Table3 shows the results in terms of TTP, server, cryptography method, and efficiency characteristics when comparing with approaches like MLS in 2017 [11], VPPLS in 2017 [13], and UDPLS in 2017 [22].Table 3
Comparison of our proposed with other protocols.
ProtocolTTPServerCryptographic methodsMLS [11]NoSeparately deployed LS and SNSAES and RSA signatureVPPLS [13]YesIntegrated LBSNSHomomorphic encryptionUDPLS [22]NoSeparately deployed LS and SNSAES and RSA signatureOur schemeNoIntegrated LBSNSOPEFrom the table, we find that some approaches, e.g., the VPPLS scheme, need a fully trusted third party (TTP) to verify the user ID and run some cryptographic computation. In the TTP-based schemes, the third party stores user’s sensitive information and some important information of the system, which may put the system in jeopardy if it is comprised. However, our scheme uses the location transformation and OPE method to protect user privacy getting rid of the introduction of TTP.Some exiting solutions, e.g., MLS and UPDLS, separately deploy two different servers including location server and social network server to store information and provide users two kinds of services, location-based services, and social network services. The main drawback of LBS/SNS separated architectures is the multiple-round interactions between the servers, which may incur higher communication cost and cause great computation and storage burden as well. In practice, mobile users can enjoy their online social network services by the wireless mobile network and, meanwhile, obtain their exact location information through the GPS equipped in the smart terminals. Nowadays, location sharing and services are important functions of MSNs, and integrating two kinds of services can bring more convenient and flexibility for users, which has become an indispensable tool of users’ daily life. In security aspect, in the LBS/SNS separated architectures, the user’s location information and user profiles are separately stored in two servers, and they are assumed to be no-collusion to guarantee the system safety. However, commonly, in some location-sharing scenarios, the location information can be easily captured by adversaries, if the server providers collude with them or collude with each other, the user privacy and system safety are insecure, which makes these distributed architectures unpractical in real life. In our model, these two kinds of servers are combined by one LBSNS, providing integrated service delivery.In terms of cryptographic methods, the VPPLS protocol used the homomorphic encryption method to compute the distance between Alice and her friends without disclosing the exact position to other party, and MLS and UDPLS rely on symmetric encryption AES and asymmetric encryption RSA signature to ensure the data integrity and confidentiality. These privacy preservation approaches can provide user location sharing privately and securely. However, the main concern is the heavy computing burden both on user and server sides when running the encryption algorithms. Different with the traditional encryption method, our scheme utilizes efficient OPE algorithm to protect user data, and the ULSS only needs to encrypt very small amount of user data, in our evaluation result, Table2 shows that user only takes several milliseconds to complete the encryption process. Besides, for the LBSNS, it can directly conduct the proximity detection by comparing the ciphertexts, without having to decrypt, which can greatly save the computing and communication resources. Thus, we can deduce that our scheme is more efficient.Discussion. In our proposed scheme, we presented two methods, Hilbert curve-based proximity detection method and lightweight order-preserving encryption- (OPE-) based method, to provide the users with flexible privacy preservation in an efficient and friendly way. The evaluation results of Hilbert curve transformation show that the processing time on the user side and server side is very small. And from the experiments with respect to order-preserving encryption, we can also find that the average processing time of users is several milliseconds. Meanwhile, due to OPE, the server can directly perform range queries without decrypting the ciphertext, which minimizes the overhead on it. Compared with the homomorphic encryption- (HE-) based method [13] and AES&RSA-based method [11, 22], we can state that our ULSS is more efficient and practical. From the aspect of security, in some existing solution, the privacy of users is guaranteed based on the assumption of fully trust in the service provider or TTP. However, the TTP-based structure results in trust issues, like the single-point failure and the bottle-neck problem of communications, and if the TTP is comprised, the security of the entire system is at risk. Our scheme is TTP-free architecture, which can protect user location privacy with respect to SP, friends, and other adversaries. We also prove that the proposed scheme is secure under the stronger security model with enhanced privacy. Moreover, unlike the multiserver structure in [11, 22], in our scheme, the LBS and SNS are integrated by one server to provide entire and convenient services, and it also can reduce communication and computational overheads and security risks as well.


## 7. Related Work

### 7.1. Location-Based Services

With the popularity of LBS, the concern of privacy leakage in LBS raises, and many researches for privacy preservation have been proposed.K-anonymity [33] is one of the popular technologies to solve the privacy leakage issue in LBS, which employs a trusted third party (TTP) called anonymizer to replace the exact location of the user by a cloaked area including at least K users so that the user location is indistinguishable from K − 1 other locations. Based on this fundamental idea, researchers [34–37] proposed efficient methods and models to construct K-anonymity spatial region (K-ASR) to protect user privacy. The authors in [36] proposed a location privacy-preserving K-anonymity method based on the credible chain, in which the optimal K value for the user is determined according to the user’s environment and social attributes. The authors in [37] proposed a privacy scheme through caching and spatial K-anonymity (CSKA) and utilized the Markov model to predict the next query location according to the user mobility in continuous LBS. The TTP-based schemes, to some extent, solve the problem of privacy leakage in LBS. However, the introduction of the anonymizer in these schemes actually transfer users’ trust from the SP to the intermediate entities. If it is compromised by the adversaries, it will pose a serious threat to users. Thus, these TTP-based schemes can only provide limited security assurance. In order to address the problem, in our previous work [38], we designed a privacy-preserving scheme based on location transformation getting rid of the fully trusted entities to provide enhanced security. The anonymizer can provide users accurate results without knowing any information about a user’s real location.The TTP-free schemes were adopted in the distributed peer to peer (P2P) environment to protect user privacy. Montazeri et al. in [39] introduced an information-theoretic notion for location privacy offering two models in both snapshot LBS and continuous LBS. Huang et al. [40] proposed a multimodal Bayesian embedding model (MMBE) for point-of-interest (POI) recommendation on location-based cyber-physical social networks. Sangaiah et al. used machine learning techniques to propose a method for conserving position confidentiality of roaming PBSs users in [41]. The authors in [42] considered the privacy and utility requirements of each user to propose an optimal user-centric location obfuscation mechanism. Sun et al. [43] introduced the location-label based (LLB) algorithm to distinguish locations of mobile users to sensitive and ordinary locations and designed three protocols to protect user privacy for different user environments. Zhang et al. [9] proposed a deviation-based query exchange (DQE) scheme to obfuscate the users’ query point to mitigate trajectory disclosure in MSNs. In our previous work [44], we presented a collaborative trajectory privacy-preserving (CTPP) scheme for continuous LBS queries, in which trajectory privacy is guaranteed by caching-aware collaboration between users. The main idea is to spatiotemporally break the correlations of continuous LBS queries to prevent the adversary from reconstructing a user’s actual trajectory. The main drawback of TTP-free scheme is that multiple-round interaction between the servers and the user may cause a higher communication cost and may incur a higher computation overhead on the user side.In addition, differential privacy technology [45–47], mix-zone method [48, 49], and encryption-based methods are also adopted to protect user privacy in LBS.


### 7.2. Location-Sharing Service

Our paper briefly focuses on a popular LBS location-sharing service, which enables users to share their current locations by the GPS-enabled devices to their friends on the MSNs or to find whether any friends are within a given vicinity area. It makes a large number of social network applications by the virtue of the smartphone and MSNs. Previous research studies [11, 12] discussed the issue of privacy preservation for the location-sharing service. In order to protect location privacy and social network privacy of mobile users, Li et al. [11] proposed a location-sharing construction with multiple location servers, in which the user’s friend set was divided into multiple subsets randomly. Zheng et al. [2] presented a location tag construction method by environmental signals to provide an unforgeable location proof and used Bloom filters to efficiently represent users’ location tags and vicinity regions. In the spatial-generalization-based method [50, 51], the user location space is divided into grids, and the precise position of user is replaced by the generalized grid prior to sending to SP. The authors in [50] proposed two protocols named “Hide and Seek” and “Hide and Crypt” based on spatial generalization to offer private proximity detection. Based on the “one degree” grid, Jing et al. in [51] presented a flexible and private proximity testing (FPODG) protocol. However, in the existing solution, the privacy of users can hardly be guaranteed without the assumption of fully trust in the service provider. Homomorphic encryption- (HE-) based privacy-preserving location-sharing scheme methods [13, 14] allow mobile users to compute distances between them and their friends without knowing the exact locations of each other. Based on HE, Tang and Cai proposed privacy-preserving location-sharing scheme (VPPLS) to build two models to enable users to query their friends’ location in a secure way, which allowed user to make a classification of his friends and provide a verification for query result. The main drawback of these methods is the large computational and communication cost of the system, which makes the scheme less practical. Li and Jung [52] used the technology of ciphertext policy attribute-based encryption (CP-ABE) to design fine-grained privacy-preserving location query protocol (PLQP), and it satisfies different levels of location query and realize fine-grained and multileveled access control. These cryptographic-based methods can provide strong privacy guarantee for users at the high expense of computation and traffic. We proposed a lightweight privacy-aware friend locator (PAFL) in our previous work [3] to provide privacy guarantee for the user in an efficient way. However, the coarse-grained friend locator method cannot meet the personalized needs of mobile users. In this paper, we proposed a flexible ULSS scheme for private proximity detection, in which each user can maintain his own privacy-preserving control policy.


## 7.1. Location-Based Services

With the popularity of LBS, the concern of privacy leakage in LBS raises, and many researches for privacy preservation have been proposed.K-anonymity [33] is one of the popular technologies to solve the privacy leakage issue in LBS, which employs a trusted third party (TTP) called anonymizer to replace the exact location of the user by a cloaked area including at least K users so that the user location is indistinguishable from K − 1 other locations. Based on this fundamental idea, researchers [34–37] proposed efficient methods and models to construct K-anonymity spatial region (K-ASR) to protect user privacy. The authors in [36] proposed a location privacy-preserving K-anonymity method based on the credible chain, in which the optimal K value for the user is determined according to the user’s environment and social attributes. The authors in [37] proposed a privacy scheme through caching and spatial K-anonymity (CSKA) and utilized the Markov model to predict the next query location according to the user mobility in continuous LBS. The TTP-based schemes, to some extent, solve the problem of privacy leakage in LBS. However, the introduction of the anonymizer in these schemes actually transfer users’ trust from the SP to the intermediate entities. If it is compromised by the adversaries, it will pose a serious threat to users. Thus, these TTP-based schemes can only provide limited security assurance. In order to address the problem, in our previous work [38], we designed a privacy-preserving scheme based on location transformation getting rid of the fully trusted entities to provide enhanced security. The anonymizer can provide users accurate results without knowing any information about a user’s real location.The TTP-free schemes were adopted in the distributed peer to peer (P2P) environment to protect user privacy. Montazeri et al. in [39] introduced an information-theoretic notion for location privacy offering two models in both snapshot LBS and continuous LBS. Huang et al. [40] proposed a multimodal Bayesian embedding model (MMBE) for point-of-interest (POI) recommendation on location-based cyber-physical social networks. Sangaiah et al. used machine learning techniques to propose a method for conserving position confidentiality of roaming PBSs users in [41]. The authors in [42] considered the privacy and utility requirements of each user to propose an optimal user-centric location obfuscation mechanism. Sun et al. [43] introduced the location-label based (LLB) algorithm to distinguish locations of mobile users to sensitive and ordinary locations and designed three protocols to protect user privacy for different user environments. Zhang et al. [9] proposed a deviation-based query exchange (DQE) scheme to obfuscate the users’ query point to mitigate trajectory disclosure in MSNs. In our previous work [44], we presented a collaborative trajectory privacy-preserving (CTPP) scheme for continuous LBS queries, in which trajectory privacy is guaranteed by caching-aware collaboration between users. The main idea is to spatiotemporally break the correlations of continuous LBS queries to prevent the adversary from reconstructing a user’s actual trajectory. The main drawback of TTP-free scheme is that multiple-round interaction between the servers and the user may cause a higher communication cost and may incur a higher computation overhead on the user side.In addition, differential privacy technology [45–47], mix-zone method [48, 49], and encryption-based methods are also adopted to protect user privacy in LBS.


## 7.2. Location-Sharing Service

Our paper briefly focuses on a popular LBS location-sharing service, which enables users to share their current locations by the GPS-enabled devices to their friends on the MSNs or to find whether any friends are within a given vicinity area. It makes a large number of social network applications by the virtue of the smartphone and MSNs. Previous research studies [11, 12] discussed the issue of privacy preservation for the location-sharing service. In order to protect location privacy and social network privacy of mobile users, Li et al. [11] proposed a location-sharing construction with multiple location servers, in which the user’s friend set was divided into multiple subsets randomly. Zheng et al. [2] presented a location tag construction method by environmental signals to provide an unforgeable location proof and used Bloom filters to efficiently represent users’ location tags and vicinity regions. In the spatial-generalization-based method [50, 51], the user location space is divided into grids, and the precise position of user is replaced by the generalized grid prior to sending to SP. The authors in [50] proposed two protocols named “Hide and Seek” and “Hide and Crypt” based on spatial generalization to offer private proximity detection. Based on the “one degree” grid, Jing et al. in [51] presented a flexible and private proximity testing (FPODG) protocol. However, in the existing solution, the privacy of users can hardly be guaranteed without the assumption of fully trust in the service provider. Homomorphic encryption- (HE-) based privacy-preserving location-sharing scheme methods [13, 14] allow mobile users to compute distances between them and their friends without knowing the exact locations of each other. Based on HE, Tang and Cai proposed privacy-preserving location-sharing scheme (VPPLS) to build two models to enable users to query their friends’ location in a secure way, which allowed user to make a classification of his friends and provide a verification for query result. The main drawback of these methods is the large computational and communication cost of the system, which makes the scheme less practical. Li and Jung [52] used the technology of ciphertext policy attribute-based encryption (CP-ABE) to design fine-grained privacy-preserving location query protocol (PLQP), and it satisfies different levels of location query and realize fine-grained and multileveled access control. These cryptographic-based methods can provide strong privacy guarantee for users at the high expense of computation and traffic. We proposed a lightweight privacy-aware friend locator (PAFL) in our previous work [3] to provide privacy guarantee for the user in an efficient way. However, the coarse-grained friend locator method cannot meet the personalized needs of mobile users. In this paper, we proposed a flexible ULSS scheme for private proximity detection, in which each user can maintain his own privacy-preserving control policy.


## 8. Conclusion

In this paper, we proposed user-defined location-sharing scheme in mobile social networks to protect user privacy in proximity detection service. We proposed two protocols, coarse-grained proximity detection and lightweight user-defined nearby friend detection to realize proximity query of users in different scales of vicinity regions. Our scheme is TTP-free architecture, in which the location-based services and social network services are integrated by one LBSNS server, making it more practical and convenient. Experimental results suggest that the ULSS scheme consumes low computational and communication overheads even for a large size of vicinity area and mount of friends. In our scheme, we used a minimum bounding rectangle to cover the user-specified vicinity region, which affects the accuracy of the results. In the future, we will propose an approach which can support the irregular shape vicinity to deliver services in more accurate ways.



---

*Source: 7832875-2020-10-26.xml*