# A New Group Location Privacy-Preserving Method Based on Distributed Architecture in LBS

Authors: JingJing Wang; YiLiang Han; XiaoYuan Yang; TanPing Zhou; JiaYong Chen
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Nowadays, the location privacy problem has become an important problem for the users who enjoy the location-based services (LBSs). Researchers have focused on the problem of how to protect the location privacy of user efficiently for a long time. On one hand, many achievements adopt the centralized structure in which there is an additional center server. Additionally, some other researchers adopt the distributed structure to overcome the disadvantages brought by the center server in the centralized anonymous system structure. On the other hand, the existing methods of solving the problem are always to protect the individual user’s location privacy in LBSs, without considering the user group’s location privacy. This kind of methods is not very applicable to the status of a number of users who formed a group to complete a LBS task together by collaborative computing. In order to solve the problem of location privacy protection for a user group in the untrusted mobile social networks, a location privacy protection method based on the distributed structure is discussed in this paper. In the scheme, the special homomorphic features of BGN cryptosystem are cleverly used so that it can solve the group’s three classical location service applications simultaneously, namely, group nearest neighbor query, optimal group collection point determination, and group friend’s distance query, by only one security policy. If there are k users who formed the group, it could achieve k-anonymity without exposing the coordinate of each individual user or using any anonymous areas. Furthermore, theoretical and experimental analysis proves that the proposal can efficiently protect each user’s location privacy in the group through taking full advantage of the collaborative computing and communication capabilities of the mobile terminals. It can resist the existing distance interaction attack and collusion attack and can realize the secure and efficient fine-grained controllable location privacy protection for the user group.


---

## Body

## 1. Introduction

LBSs experience a booming period of development due to the wide applications of location-based technology and the mobile terminals [1]. However, in the mobile social network, LBSs are usually provided by a server, which is called the location service provider (SP). Generally, in order to obtain good quality of LBSs, the users need to obey the policy set by the SP, that is, “informed consent,” and have to provide their sensitive location information to the SP. However, most of the SPs are profit-oriented and they are not so reliable and trustworthy [2]. As a result, the users’ real location information, even the related personal sensitive information such as living habits, interests, and health status, may be in danger of leaking and inferring. As an alternative, the users’ location information might be completely hidden from the SP. In this scenario, the SP cannot provide the services with good quality or meet the application requirements. Therefore, how to balance the location privacy and the service quality is a key issue in the applications of LBSs.Fortunately, with the development of the mobile networks, researchers have found many methods that can realize the location privacy-preserving in the applications of LBSs. The existing methods mainly can be divided into two big categories.(1) One is mixing the user’s real location with a number of generalized fake locations. Then all the pseudolocations are sent to the SP together with the real location to get services. So it is difficult to tell which one is the user’s real location. (2) The other is reducing the accuracy of user’s location data. What the SP can get from the user is the fuzzy location information. Then the SP supports the service according to the fuzzy location.No matter which kind of above methods is, it must be designed based on a certain system model. According to the perspective of system structure, there are two main types. They are, respectively, the centralized and distributed architecture. As shown in Figure1, it is a location privacy-preserving model with the centralized system structure. The model is mainly composed of the user’s mobile terminal, the trusted center server, and the SP. In this model, either the pseudolocations method or the fuzzy method can be used to protect the user’s location privacy. Especially, in both methods, it is the trusted center server that completes the privacy protection work for the user’s location and query information. Namely, the computation of pseudolocations or obfuscation of the real location is done by the center server. Examples can be found in [7–9], in which the centralized structure with the center server was employed. This kind of model is also the conventional design.Figure 1
The location privacy-preserving system model with the centralized structure.However, there are several shortcomings in the centralized location privacy-preserving model.(1) The center server must be trusted and dependable; otherwise the user’s location collected by the server may face a serious threat. (2) Even if the center server is trustworthy, it still can become the performance bottleneck and the attack target in the applications. (3) The introduction of the center server brings the additional computation and communication consumptions. Moreover, it ignores the edge-computing capacity of the user’s terminal.In order to overcome the shortcomings of the centralized structure, more and more researches turn to the models with the distributed structure. For example, [10–14] all adopted the distributed architecture. The distributed structure system is only composed of the mobile terminals and SP. In this kind of structure, there is no central server. The users conduct the task of location privacy protection in LBSs together by their mobile terminals. In conclusion, various location privacy protection methods with different model structures have their own advantages. Researchers have considered various different scenarios and objects when designing their location privacy protection schemes.Moreover, most of these existing schemes focus on the location privacy protection from the view of the individual user. They did not consider another frequent situation in practice. Sometimes, many users in the mobile networks are willing to form a group to collaborate when they issue the LBS. They want to realize their location privacy protection and obtain good service results with other users’ cooperative computing. In the group, they can exchange some information but with their own location with other users of the same group for completing a task such as group nearest neighbor (GNN) query. Once the group jointly completes the query, each user in the group can adopt the query result returned in the LBS. However, the researches in this area are relatively rare and the existing schemes do not apply to the collaborative computing environment where many users complete the group query task together. Thus, it is necessary to design some schemes on the location privacy protection from the view of the user group.


## 2. Related Works

In fact, Hashem et al. [3] first researched on the user’s location privacy problem in the GNN query. In their solution, each user’s location in the group is fuzzied to its corresponding anonymous area. Then SP returns a series of candidate query results to the users in the group according to the anonymous areas. Then a filter algorithm is conducted to determine which one is nearest for all the users in the group. The solution has high communication overhead and cannot resist the collusion attack. In the same year, [15] proposed two schemes with centralized and distributed architecture, respectively, in the application of the GNN query. It adopts the multiparty computation to compute the object location so as to get the smallest sum of distances between the object location and all the users in the group. However, as its candidate target locations are predetermined, it would bring extra additional costs and overheads. Moreover, the leakage of distances threatened the user’s location privacy in the group. Reference [6] proposed a group location privacy protection protocol (GLP), in which the Paillier cryptosystem [16] is used to compute the center location of the user group. However, because GLP needs to compute the AV-net [17] values in advance to realize protection, multiple different query messages and candidate response results will be generated in a single service. Moreover, each user in the group needs to broadcast his message. It occupies considerable resources and contributes to high communication cost. Indeed, back in 2008, [4] has already proposed a distributed location privacy protection scheme. It did not take the user group as the research object, but it used a number of users’ disturbed location data to compute the centroid. Then it sent the centroid as the location to the SP for the nearest neighbor query in LBS. Actually, the intrinsice essence of the scheme is identical with [6]. Both [4, 6] turn the GNN query into nearest neighbor (NN) query of the group center so as to realize location privacy preserving. Similarly, [5] added random disturbance to the user’s locations first. Then the disturbed locations are encrypted by Paillier cryptosystem to well protect each user’s location privacy in the group. Furthermore, the group center location is figured out according to the secret sharing protocol. The scheme can well solve the privacy protection problem of the static GNN query. However, its construction is complex due to the secret sharing protocol. Its calculation overhead is high. The practicability is not strong.At present, more and more researches about group privacy protection have focused on the key problem of the group center computation. It is proven that the group location privacy protection and the quality of LBS can be well balanced by changing the GNN query into NN query. Namely, as shown in Figure2, in order to protect the location privacy of the user group, which is formed by users p2,⋯,pk, the center location of the group is used as the geographic anchor point instead of the user’s real location to issue queries. The SP gives the service results to the users in the group according to the center location. Therefore, the key problem of the group location privacy-preserving schemes is to calculate the center location without leaking each user’s real location. Additionally, there is no doubt that the encryption technique can be used to protect the location privacy of the user group. But, until now, only a few works have been done in this area. And none of the outcomes mentioned above considered the quantitative measure or the controllability of the privacy protection effect from the view of the user.Figure 2
The center location of the user group.In this paper, a new location privacy-preserving protocol for user group based on the distributed structure is designed. Each user’s real location is added with a noise disturbance parameter to protect the user’s location privacy. The weight coefficients are also introduced to ensure that the user who enjoys the LBS currently can freely adjust and control the contribution of other user’s location data when computing the group center. Meanwhile, without exposing any user’s real location coordinate, our scheme can realize only using one security policy, the core of BGN, to well solve three privacy protection problems in the classic LBS scenarios: the applications of GNN, the best group collection location determination, and the group friends distance query.


## 3. Our System Structure

### 3.1. Our System Model

Before the explanation of our scheme, this section puts forward our system model first. Shown as Figure3, the distributed structure without any center server is adopted in our system model. Our system is mainly composed of the positioning system (such as global position system, BeiDou Navigation Satellite System, etc.), a user group, the communication networks, and the SP.Figure 3
Our system model.In order to simplify the problem, our system model assumes that if any user needs the LBS, he can easily form a group with nearby neighbors by the way of self-organized P2P network. In the group, users can communicate with each other and get their own location through the positioning system in real time. The privacy protection for each user is completed by the cooperation of the users in the group.Compared with the existing models, in our model, the SP is semitrusted and the trusted center server is not necessary any more. It avoids the disadvantage brought by the request of trustworthy SP and the center server. The user who applies for LBS only sends the group center location as the anchor point instead of his own location to get good quality results from the SP. More importantly, our model ensures that each user never leaks their own real locations in the process of LBSs to any third party, including the other group users and the SP. Thus, it is more practical and effective in location privacy-preserving than other system models in the untrusted mobile networks.


### 3.2. Our System Basic Hypothesis

In view of the practical status of the mobile network, the system model is assumed as follows:(1)
The servers of the SP provide LBSs to the mobile users. Mobile users send LBS requests to the servers and receive corresponding location service results from the SP. In an open network environment, the SP will provide service results for users who request services. Moreover, in certain scenarios, the SP might analyze or disclose the user’s real sensitive location information. Namely, the semitrusted SP is employed in this paper.(2)
The communication between mobile users and the SP is forwarded by the communication base station, and any third party can get and record the wireless messages transmitted by the base station.(3)
The mobile users obtain their real position coordinates from the position system or the location satellite anonymously.(4)
The mobile users have fine-granular demand for their location privacy and have the specific quality of service requirements.(5)
The users in the group distrust each other, and they will never expose or send their own real location to others.


### 3.3. Our System Symbols

For convenient describtion, Table1 lists some symbols and parameters used in our system.Table 1
Symbol definitions.
G = { p 1 , p 2 , ⋯ , p k } The groupGformed by the user nodes p1,p2,⋯,pk. t The certain time of the group userp1ask for LBSs. k The group location privacy-preserving request. i = 1,2 , ⋯ , k The subscript to mark symbols. x i , y i The geographic coordinate of the userpi’s location. w i ;  ∑ i = 1 k w i = 1 The weight sequence generated by the userp1. α i , β i ; 1 k  ∑ i = 1 k α i , 1 k ∑ i = 1 k β i = 0,0 The noise sequence to disturb the users’ location coordinate produced by the noise generator. x i ∧ , y i ∧ = x i + α i , y i + β i The new coordinates after the disturbance by the noise. X G , Y G = (  ∑ i = 1 k w i x i ∧ , ∑ i = 1 k w i y i ∧ ) The center location of the user groupG.


## 3.1. Our System Model

Before the explanation of our scheme, this section puts forward our system model first. Shown as Figure3, the distributed structure without any center server is adopted in our system model. Our system is mainly composed of the positioning system (such as global position system, BeiDou Navigation Satellite System, etc.), a user group, the communication networks, and the SP.Figure 3
Our system model.In order to simplify the problem, our system model assumes that if any user needs the LBS, he can easily form a group with nearby neighbors by the way of self-organized P2P network. In the group, users can communicate with each other and get their own location through the positioning system in real time. The privacy protection for each user is completed by the cooperation of the users in the group.Compared with the existing models, in our model, the SP is semitrusted and the trusted center server is not necessary any more. It avoids the disadvantage brought by the request of trustworthy SP and the center server. The user who applies for LBS only sends the group center location as the anchor point instead of his own location to get good quality results from the SP. More importantly, our model ensures that each user never leaks their own real locations in the process of LBSs to any third party, including the other group users and the SP. Thus, it is more practical and effective in location privacy-preserving than other system models in the untrusted mobile networks.


## 3.2. Our System Basic Hypothesis

In view of the practical status of the mobile network, the system model is assumed as follows:(1)
The servers of the SP provide LBSs to the mobile users. Mobile users send LBS requests to the servers and receive corresponding location service results from the SP. In an open network environment, the SP will provide service results for users who request services. Moreover, in certain scenarios, the SP might analyze or disclose the user’s real sensitive location information. Namely, the semitrusted SP is employed in this paper.(2)
The communication between mobile users and the SP is forwarded by the communication base station, and any third party can get and record the wireless messages transmitted by the base station.(3)
The mobile users obtain their real position coordinates from the position system or the location satellite anonymously.(4)
The mobile users have fine-granular demand for their location privacy and have the specific quality of service requirements.(5)
The users in the group distrust each other, and they will never expose or send their own real location to others.


## 3.3. Our System Symbols

For convenient describtion, Table1 lists some symbols and parameters used in our system.Table 1
Symbol definitions.
G = { p 1 , p 2 , ⋯ , p k } The groupGformed by the user nodes p1,p2,⋯,pk. t The certain time of the group userp1ask for LBSs. k The group location privacy-preserving request. i = 1,2 , ⋯ , k The subscript to mark symbols. x i , y i The geographic coordinate of the userpi’s location. w i ;  ∑ i = 1 k w i = 1 The weight sequence generated by the userp1. α i , β i ; 1 k  ∑ i = 1 k α i , 1 k ∑ i = 1 k β i = 0,0 The noise sequence to disturb the users’ location coordinate produced by the noise generator. x i ∧ , y i ∧ = x i + α i , y i + β i The new coordinates after the disturbance by the noise. X G , Y G = (  ∑ i = 1 k w i x i ∧ , ∑ i = 1 k w i y i ∧ ) The center location of the user groupG.


## 4. Our Method

### 4.1. Our Location Privacy-Protection Scheme of GNN Query

#### 4.1.1. Initialization Definitions

When the userp1 initiates the LBS at the time t, he will broadcast the message to the other neighbor users to invite them to form a group. If the user wants to form a group consisting of k members, he would confirm the first k-1 messages received from the other users. Thus, the k-1 users who responded to messages and obtained confirmations are selected to form the group together with p1. In special case, if the number of user nodes is not enough, the broadcast range and hops should be increased, and the nodes that were accepted to form the group need to find more other nodes available for the group until k group users are accepted. Theoretically, if the group consists of k users, the scheme can realize k-anonymity for each user in the group. Because, in most cases, the k-1 users selected are the neighbor nodes around the user, the service results, such as GNN query result and best group collection location, are suitable for all the users in the group. In our method, we adopt the BGN cryptosystem as the security policy. BGN [18] is one of the most classical homomorphic cryptosystems. It can support homomorphic addition and one-time homomorphic multiplication simultaneously.Definition 1.
G 1 , G 2 are additive groups, and GT is a multiplicative group. The orders of G1,G2,GT are all primes. P∈G1,Q∈G2 are the respective generators of G1,G2.
Bilinear mapping,e:G1×G2→GT, has the features as follows:(1)
Bilinearity:∀a,b∈Zp∗, ePa,Qb=eP,Qab.(2)
Nondegeneration:eP,Q≠1.(3)
With special condition,e can be computed effectively:
WhenG1=G2=G0 and G0 is a cyclic group, e has the feature of interchangeability:(1)∀P,Q∈G0,eP,Q=eQ,P.Definition 2.
Based on the bilinear mapping, the BGN cipher system is composed of three parts: key generation, encryption, and decryption.For key generation, each user in the system has a pair of keys distributed by the BGN cryptosystem, namely, the public key and the private key.Setλ∈Z+ as a security parameter, and generate a tuple q1,q2,G0,G1′,e, in which q1,q2 are two different large prime numbers. G0 is a cyclic group of order q1q2; the bilinear mapping e is G0×G0→G1′. Set N=q1q2. Two generators g,u are chosen from G0. Assuming that h=uq2, h is the generator with the order q1 of the subgroup of G0. PK=N,G,G1′,e,g,h, and SK=q1. If the parameters are selected by the user p1, then p1’s public key is PK and the private key is SK.For encryption, suppose that the space of the plaintext messages is made up by the integers of the set0,1,⋯,T, where T<q2. Using the public key PK to encrypt the message m, selecting a random number r, r∈1,2,⋯,N, then calculate:C = g m h r ∈ G 0, where C is the ciphertext.For decryption, use the private keySK=q1 to decrypt the ciphertext:(2)Cq1=gmhrq1=gmurq2q1=gq1m,m=loggq1Cq1.So the userp1 can compute out m by his private key. Moreover, here 0≤m≤T; the time complexity of the solution would be oT [19].Definition 3.
The BGN cryptosystem can support homomorphic addition and one-time homomorphic multiplication simultaneously.Our method adopts the secure policy of BGN cryptosystem, and our solutions validity depends on its homomorphic property. Here, we prove the homomorphic property of BGN cryptosystem. For convenient explanation, the encryption algorithm of BGN cryptosystem is denoted byE∗(·), and its decryption algorithm is D∗(·).(1) Additive Homomorphism. Set EPKm1=C1=gm1hr1∈G0,EPK(m2)=C2=gm2hr2∈G0 as the respective corresponding ciphertext of the plaintext m1,m2∈0,1,⋯,T.IfC=C1C2hr, thenD S K ( C ) = D S K ( C 1 C 2 h r ) = D S K g m 1 h r 1 g m 2 h r 2 h r = D S K g m 1 + m 2 h r 1 + r 2 + r = m 1 + m 2 is established, where r∈1,2,⋯,N-1 is randomly chosen.(2) One-Time Multiplicative Homomorphism. Set g1=eg,g,h1=e(g,h); and the order of g1 is N and the order of h1 is q1. Moreover, there is μ∈Z, meeting h=gμq2 and C=eC1,C2h1r. So the following equation is correct:(3)DSKC=DSKeC1,C2h1r=DSKegm1hr1,gm2hr2h1r=DSKegm1+μq2r1,gm2+μq2r2h1r=DSKeg,gm1+μq2r1m2+μq2r2h1r=DSKeg,gm1m2+μq2m1r2+m2r1+μr1r2q2h1r=DSKeg,gm1m2h1r+m1r2+m2r1+μr1r2q2=m1m2modN.Thus, the result of the operation on the plaintexts can be also got by decrypting the corresponding operation result of the ciphertexts [20]. For example, in our method, the group center can be obtained only depending on the computation of the ciphertexts from the users’ real sensitive locations. It can be directly decrypted from the processed result of the encrypted users’ locations. This theory will be elaborated in the next section.


#### 4.1.2. Scenario Description

An important type of LBSs is the point of interest query, also known as location searching services (LSSs) [14]. User can find nearby interest point location and get corresponding distances to the desired location through LSSs. Actually, LSSs include many classic applications of LBSs, such as finding nearby interest locations or friends and determining the optimal collection location. In this section, the scheme is designed in the scenario of GNN query. For the premise of location privacy-preserving, the users in the group need to cooperate with one another to complete the query task without exposing their real location information.


#### 4.1.3. Scheme Description

Here, we assume that the userp1 first wants to apply for the GNN query, and he has already formed the group with other k-1 users p2,⋯,pk. Additionally, the digital signature of the user pi is denoted as Sigi·.(1)
p1 sends the message EPK(x1∧),EPKy1∧,wi,t,Sig1 to the SP, and p2,⋯,pk, respectively, send the message EPK(xi∧),EPK(yi∧),t,Sigi to the SP, where (i=2,⋯,k).(2)
After receiving the above messages, SP executes the computation as (4a) to obtain the functions of U1,U2; then the results of the functions are sent to the user p1:(4a)U1=Ex1∧w1×Ex2∧w2×⋯×Exk∧wkhr;U2=Ey1∧w1×Ey2∧w2×⋯×Eyk∧wkhr′.(3)
U1,U2 are received by p1,p1 to decrypt them as (4b) to calculate XG,YG, which is the center location of the group at the time t:(4b)XG=DSKU1=∑i=1kwixi∧;YG=DSKU2=∑i=1kwiyi∧.(4)
XG,YG is used as the anchor point to be sent to the SP by p1 for obtaining the query service. Meanwhile, the message XG,YG,t,sig1 is broadcasted to all the other group user nodes p2,p3,⋯,pk.(5)
The SP sends the result top1 according to the anchor point received. In addition, when the other group users need to issue similar location queries, they also assume XG,YG as the anchor point and send the requests to the SP to obtain the corresponding services.


### 4.2. Our Location Privacy-Protection Scheme of the Group Best Collection Location Query

#### 4.2.1. Scenario Description

Sometimes, there is an important application in LBSs. It is the query for the group collection location. The friends may want to determine some location to gather around. In this case, they can form a temporary group to obtain the optimal collection location. For the users in the group, finding the optimal location is finding the location that meets the sum of distances to everyone in the group is smallest. Moreover, in order to ensure the group privacy, the best collection location should be safely determined without exposing any user’s real location.Definition 4.
If the sum of the distances from some location point to all the group users is minimum, the point is the best assembling location of the user group, which is expressed asO. It means to calculate the coordinate value xo,yo of O, which satisfies the following equation: dmin=min⁡(∑i=1kxo-xi2+yo-yi2).


#### 4.2.2. Scheme Description

Assume that the userp1 applies for the group best collection location query services:(1)
p1,p2,⋯,pk, respectively, send the messages EPK(xi∧),EPK(yi∧),t,Sigi to SP, where (i=2,⋯,k).(2)
The SP calculatesUo1, Uo2 according to (4c) after receiving the above messages and then sends them to the user p1:(4c)Uo1=EPKx1∧×EPKx2∧×⋯×EPKxk∧hrUo2=EPKy1∧×EPKy2∧×⋯×EPKyk∧hr′.(3)
The userp1 computes the values of c1,c2 and the coordinate value xo,yo of the location point O according to (4d):(4d)DSKUo1=x1+x2+⋯+xk=∑i=1kxi=c1DSKUo2=y1+y2+⋯+yk=∑i=1kxi=c2where(xo=c1/k,yo=c2/k).


### 4.3. Our Privacy-Protection Scheme of Group Friends Distance Query

#### 4.3.1. Scenario Description

Sometimes, in LBSs, users want to know their friend’s distance from them. In this case, from the view of location privacy protection, we should ensure that each user in the group could conveniently inquire the friend’s distance without exposing his own location information or knowing his friend’s location. This case is similar to another application in LBSs that the merchants or shops would like to push advertisements to the users based on their locations. The merchants and shops concerned by the group users can safely inquire the distance from the user and decide whether to push advertisements to some user in the group without knowing the specific location of the users.


#### 4.3.2. Scheme Description

Assume that the group userp1 applies for the friend’s distance query services:(1)
The userp1 sends the friend distance query service request to the SP so as to query the friend pi’s distance.(2)
After receiving the query request, the SP calculates the function of the ciphertextsUdis according to (4e) and sends Udis to the user p1:(4e)Udis=eEPKx1+αEPK-xi-αhr,EPKx1+αEPK-xi-αhrh1r′×eEPKy1+βEPK-yi-βhr,EPKy1+βEPK-yi-βhrh1r′hr3.(3)
p1 receives the value of Udis and decrypts it so as to obtain the distance between p1 and pi according to (4f): (4f)DSKUdis=x1-xi2+y1-yi2modN.


## 4.1. Our Location Privacy-Protection Scheme of GNN Query

### 4.1.1. Initialization Definitions

When the userp1 initiates the LBS at the time t, he will broadcast the message to the other neighbor users to invite them to form a group. If the user wants to form a group consisting of k members, he would confirm the first k-1 messages received from the other users. Thus, the k-1 users who responded to messages and obtained confirmations are selected to form the group together with p1. In special case, if the number of user nodes is not enough, the broadcast range and hops should be increased, and the nodes that were accepted to form the group need to find more other nodes available for the group until k group users are accepted. Theoretically, if the group consists of k users, the scheme can realize k-anonymity for each user in the group. Because, in most cases, the k-1 users selected are the neighbor nodes around the user, the service results, such as GNN query result and best group collection location, are suitable for all the users in the group. In our method, we adopt the BGN cryptosystem as the security policy. BGN [18] is one of the most classical homomorphic cryptosystems. It can support homomorphic addition and one-time homomorphic multiplication simultaneously.Definition 1.
G 1 , G 2 are additive groups, and GT is a multiplicative group. The orders of G1,G2,GT are all primes. P∈G1,Q∈G2 are the respective generators of G1,G2.
Bilinear mapping,e:G1×G2→GT, has the features as follows:(1)
Bilinearity:∀a,b∈Zp∗, ePa,Qb=eP,Qab.(2)
Nondegeneration:eP,Q≠1.(3)
With special condition,e can be computed effectively:
WhenG1=G2=G0 and G0 is a cyclic group, e has the feature of interchangeability:(1)∀P,Q∈G0,eP,Q=eQ,P.Definition 2.
Based on the bilinear mapping, the BGN cipher system is composed of three parts: key generation, encryption, and decryption.For key generation, each user in the system has a pair of keys distributed by the BGN cryptosystem, namely, the public key and the private key.Setλ∈Z+ as a security parameter, and generate a tuple q1,q2,G0,G1′,e, in which q1,q2 are two different large prime numbers. G0 is a cyclic group of order q1q2; the bilinear mapping e is G0×G0→G1′. Set N=q1q2. Two generators g,u are chosen from G0. Assuming that h=uq2, h is the generator with the order q1 of the subgroup of G0. PK=N,G,G1′,e,g,h, and SK=q1. If the parameters are selected by the user p1, then p1’s public key is PK and the private key is SK.For encryption, suppose that the space of the plaintext messages is made up by the integers of the set0,1,⋯,T, where T<q2. Using the public key PK to encrypt the message m, selecting a random number r, r∈1,2,⋯,N, then calculate:C = g m h r ∈ G 0, where C is the ciphertext.For decryption, use the private keySK=q1 to decrypt the ciphertext:(2)Cq1=gmhrq1=gmurq2q1=gq1m,m=loggq1Cq1.So the userp1 can compute out m by his private key. Moreover, here 0≤m≤T; the time complexity of the solution would be oT [19].Definition 3.
The BGN cryptosystem can support homomorphic addition and one-time homomorphic multiplication simultaneously.Our method adopts the secure policy of BGN cryptosystem, and our solutions validity depends on its homomorphic property. Here, we prove the homomorphic property of BGN cryptosystem. For convenient explanation, the encryption algorithm of BGN cryptosystem is denoted byE∗(·), and its decryption algorithm is D∗(·).(1) Additive Homomorphism. Set EPKm1=C1=gm1hr1∈G0,EPK(m2)=C2=gm2hr2∈G0 as the respective corresponding ciphertext of the plaintext m1,m2∈0,1,⋯,T.IfC=C1C2hr, thenD S K ( C ) = D S K ( C 1 C 2 h r ) = D S K g m 1 h r 1 g m 2 h r 2 h r = D S K g m 1 + m 2 h r 1 + r 2 + r = m 1 + m 2 is established, where r∈1,2,⋯,N-1 is randomly chosen.(2) One-Time Multiplicative Homomorphism. Set g1=eg,g,h1=e(g,h); and the order of g1 is N and the order of h1 is q1. Moreover, there is μ∈Z, meeting h=gμq2 and C=eC1,C2h1r. So the following equation is correct:(3)DSKC=DSKeC1,C2h1r=DSKegm1hr1,gm2hr2h1r=DSKegm1+μq2r1,gm2+μq2r2h1r=DSKeg,gm1+μq2r1m2+μq2r2h1r=DSKeg,gm1m2+μq2m1r2+m2r1+μr1r2q2h1r=DSKeg,gm1m2h1r+m1r2+m2r1+μr1r2q2=m1m2modN.Thus, the result of the operation on the plaintexts can be also got by decrypting the corresponding operation result of the ciphertexts [20]. For example, in our method, the group center can be obtained only depending on the computation of the ciphertexts from the users’ real sensitive locations. It can be directly decrypted from the processed result of the encrypted users’ locations. This theory will be elaborated in the next section.


### 4.1.2. Scenario Description

An important type of LBSs is the point of interest query, also known as location searching services (LSSs) [14]. User can find nearby interest point location and get corresponding distances to the desired location through LSSs. Actually, LSSs include many classic applications of LBSs, such as finding nearby interest locations or friends and determining the optimal collection location. In this section, the scheme is designed in the scenario of GNN query. For the premise of location privacy-preserving, the users in the group need to cooperate with one another to complete the query task without exposing their real location information.


### 4.1.3. Scheme Description

Here, we assume that the userp1 first wants to apply for the GNN query, and he has already formed the group with other k-1 users p2,⋯,pk. Additionally, the digital signature of the user pi is denoted as Sigi·.(1)
p1 sends the message EPK(x1∧),EPKy1∧,wi,t,Sig1 to the SP, and p2,⋯,pk, respectively, send the message EPK(xi∧),EPK(yi∧),t,Sigi to the SP, where (i=2,⋯,k).(2)
After receiving the above messages, SP executes the computation as (4a) to obtain the functions of U1,U2; then the results of the functions are sent to the user p1:(4a)U1=Ex1∧w1×Ex2∧w2×⋯×Exk∧wkhr;U2=Ey1∧w1×Ey2∧w2×⋯×Eyk∧wkhr′.(3)
U1,U2 are received by p1,p1 to decrypt them as (4b) to calculate XG,YG, which is the center location of the group at the time t:(4b)XG=DSKU1=∑i=1kwixi∧;YG=DSKU2=∑i=1kwiyi∧.(4)
XG,YG is used as the anchor point to be sent to the SP by p1 for obtaining the query service. Meanwhile, the message XG,YG,t,sig1 is broadcasted to all the other group user nodes p2,p3,⋯,pk.(5)
The SP sends the result top1 according to the anchor point received. In addition, when the other group users need to issue similar location queries, they also assume XG,YG as the anchor point and send the requests to the SP to obtain the corresponding services.


## 4.1.1. Initialization Definitions

When the userp1 initiates the LBS at the time t, he will broadcast the message to the other neighbor users to invite them to form a group. If the user wants to form a group consisting of k members, he would confirm the first k-1 messages received from the other users. Thus, the k-1 users who responded to messages and obtained confirmations are selected to form the group together with p1. In special case, if the number of user nodes is not enough, the broadcast range and hops should be increased, and the nodes that were accepted to form the group need to find more other nodes available for the group until k group users are accepted. Theoretically, if the group consists of k users, the scheme can realize k-anonymity for each user in the group. Because, in most cases, the k-1 users selected are the neighbor nodes around the user, the service results, such as GNN query result and best group collection location, are suitable for all the users in the group. In our method, we adopt the BGN cryptosystem as the security policy. BGN [18] is one of the most classical homomorphic cryptosystems. It can support homomorphic addition and one-time homomorphic multiplication simultaneously.Definition 1.
G 1 , G 2 are additive groups, and GT is a multiplicative group. The orders of G1,G2,GT are all primes. P∈G1,Q∈G2 are the respective generators of G1,G2.
Bilinear mapping,e:G1×G2→GT, has the features as follows:(1)
Bilinearity:∀a,b∈Zp∗, ePa,Qb=eP,Qab.(2)
Nondegeneration:eP,Q≠1.(3)
With special condition,e can be computed effectively:
WhenG1=G2=G0 and G0 is a cyclic group, e has the feature of interchangeability:(1)∀P,Q∈G0,eP,Q=eQ,P.Definition 2.
Based on the bilinear mapping, the BGN cipher system is composed of three parts: key generation, encryption, and decryption.For key generation, each user in the system has a pair of keys distributed by the BGN cryptosystem, namely, the public key and the private key.Setλ∈Z+ as a security parameter, and generate a tuple q1,q2,G0,G1′,e, in which q1,q2 are two different large prime numbers. G0 is a cyclic group of order q1q2; the bilinear mapping e is G0×G0→G1′. Set N=q1q2. Two generators g,u are chosen from G0. Assuming that h=uq2, h is the generator with the order q1 of the subgroup of G0. PK=N,G,G1′,e,g,h, and SK=q1. If the parameters are selected by the user p1, then p1’s public key is PK and the private key is SK.For encryption, suppose that the space of the plaintext messages is made up by the integers of the set0,1,⋯,T, where T<q2. Using the public key PK to encrypt the message m, selecting a random number r, r∈1,2,⋯,N, then calculate:C = g m h r ∈ G 0, where C is the ciphertext.For decryption, use the private keySK=q1 to decrypt the ciphertext:(2)Cq1=gmhrq1=gmurq2q1=gq1m,m=loggq1Cq1.So the userp1 can compute out m by his private key. Moreover, here 0≤m≤T; the time complexity of the solution would be oT [19].Definition 3.
The BGN cryptosystem can support homomorphic addition and one-time homomorphic multiplication simultaneously.Our method adopts the secure policy of BGN cryptosystem, and our solutions validity depends on its homomorphic property. Here, we prove the homomorphic property of BGN cryptosystem. For convenient explanation, the encryption algorithm of BGN cryptosystem is denoted byE∗(·), and its decryption algorithm is D∗(·).(1) Additive Homomorphism. Set EPKm1=C1=gm1hr1∈G0,EPK(m2)=C2=gm2hr2∈G0 as the respective corresponding ciphertext of the plaintext m1,m2∈0,1,⋯,T.IfC=C1C2hr, thenD S K ( C ) = D S K ( C 1 C 2 h r ) = D S K g m 1 h r 1 g m 2 h r 2 h r = D S K g m 1 + m 2 h r 1 + r 2 + r = m 1 + m 2 is established, where r∈1,2,⋯,N-1 is randomly chosen.(2) One-Time Multiplicative Homomorphism. Set g1=eg,g,h1=e(g,h); and the order of g1 is N and the order of h1 is q1. Moreover, there is μ∈Z, meeting h=gμq2 and C=eC1,C2h1r. So the following equation is correct:(3)DSKC=DSKeC1,C2h1r=DSKegm1hr1,gm2hr2h1r=DSKegm1+μq2r1,gm2+μq2r2h1r=DSKeg,gm1+μq2r1m2+μq2r2h1r=DSKeg,gm1m2+μq2m1r2+m2r1+μr1r2q2h1r=DSKeg,gm1m2h1r+m1r2+m2r1+μr1r2q2=m1m2modN.Thus, the result of the operation on the plaintexts can be also got by decrypting the corresponding operation result of the ciphertexts [20]. For example, in our method, the group center can be obtained only depending on the computation of the ciphertexts from the users’ real sensitive locations. It can be directly decrypted from the processed result of the encrypted users’ locations. This theory will be elaborated in the next section.


## 4.1.2. Scenario Description

An important type of LBSs is the point of interest query, also known as location searching services (LSSs) [14]. User can find nearby interest point location and get corresponding distances to the desired location through LSSs. Actually, LSSs include many classic applications of LBSs, such as finding nearby interest locations or friends and determining the optimal collection location. In this section, the scheme is designed in the scenario of GNN query. For the premise of location privacy-preserving, the users in the group need to cooperate with one another to complete the query task without exposing their real location information.


## 4.1.3. Scheme Description

Here, we assume that the userp1 first wants to apply for the GNN query, and he has already formed the group with other k-1 users p2,⋯,pk. Additionally, the digital signature of the user pi is denoted as Sigi·.(1)
p1 sends the message EPK(x1∧),EPKy1∧,wi,t,Sig1 to the SP, and p2,⋯,pk, respectively, send the message EPK(xi∧),EPK(yi∧),t,Sigi to the SP, where (i=2,⋯,k).(2)
After receiving the above messages, SP executes the computation as (4a) to obtain the functions of U1,U2; then the results of the functions are sent to the user p1:(4a)U1=Ex1∧w1×Ex2∧w2×⋯×Exk∧wkhr;U2=Ey1∧w1×Ey2∧w2×⋯×Eyk∧wkhr′.(3)
U1,U2 are received by p1,p1 to decrypt them as (4b) to calculate XG,YG, which is the center location of the group at the time t:(4b)XG=DSKU1=∑i=1kwixi∧;YG=DSKU2=∑i=1kwiyi∧.(4)
XG,YG is used as the anchor point to be sent to the SP by p1 for obtaining the query service. Meanwhile, the message XG,YG,t,sig1 is broadcasted to all the other group user nodes p2,p3,⋯,pk.(5)
The SP sends the result top1 according to the anchor point received. In addition, when the other group users need to issue similar location queries, they also assume XG,YG as the anchor point and send the requests to the SP to obtain the corresponding services.


## 4.2. Our Location Privacy-Protection Scheme of the Group Best Collection Location Query

### 4.2.1. Scenario Description

Sometimes, there is an important application in LBSs. It is the query for the group collection location. The friends may want to determine some location to gather around. In this case, they can form a temporary group to obtain the optimal collection location. For the users in the group, finding the optimal location is finding the location that meets the sum of distances to everyone in the group is smallest. Moreover, in order to ensure the group privacy, the best collection location should be safely determined without exposing any user’s real location.Definition 4.
If the sum of the distances from some location point to all the group users is minimum, the point is the best assembling location of the user group, which is expressed asO. It means to calculate the coordinate value xo,yo of O, which satisfies the following equation: dmin=min⁡(∑i=1kxo-xi2+yo-yi2).


### 4.2.2. Scheme Description

Assume that the userp1 applies for the group best collection location query services:(1)
p1,p2,⋯,pk, respectively, send the messages EPK(xi∧),EPK(yi∧),t,Sigi to SP, where (i=2,⋯,k).(2)
The SP calculatesUo1, Uo2 according to (4c) after receiving the above messages and then sends them to the user p1:(4c)Uo1=EPKx1∧×EPKx2∧×⋯×EPKxk∧hrUo2=EPKy1∧×EPKy2∧×⋯×EPKyk∧hr′.(3)
The userp1 computes the values of c1,c2 and the coordinate value xo,yo of the location point O according to (4d):(4d)DSKUo1=x1+x2+⋯+xk=∑i=1kxi=c1DSKUo2=y1+y2+⋯+yk=∑i=1kxi=c2where(xo=c1/k,yo=c2/k).


## 4.2.1. Scenario Description

Sometimes, there is an important application in LBSs. It is the query for the group collection location. The friends may want to determine some location to gather around. In this case, they can form a temporary group to obtain the optimal collection location. For the users in the group, finding the optimal location is finding the location that meets the sum of distances to everyone in the group is smallest. Moreover, in order to ensure the group privacy, the best collection location should be safely determined without exposing any user’s real location.Definition 4.
If the sum of the distances from some location point to all the group users is minimum, the point is the best assembling location of the user group, which is expressed asO. It means to calculate the coordinate value xo,yo of O, which satisfies the following equation: dmin=min⁡(∑i=1kxo-xi2+yo-yi2).


## 4.2.2. Scheme Description

Assume that the userp1 applies for the group best collection location query services:(1)
p1,p2,⋯,pk, respectively, send the messages EPK(xi∧),EPK(yi∧),t,Sigi to SP, where (i=2,⋯,k).(2)
The SP calculatesUo1, Uo2 according to (4c) after receiving the above messages and then sends them to the user p1:(4c)Uo1=EPKx1∧×EPKx2∧×⋯×EPKxk∧hrUo2=EPKy1∧×EPKy2∧×⋯×EPKyk∧hr′.(3)
The userp1 computes the values of c1,c2 and the coordinate value xo,yo of the location point O according to (4d):(4d)DSKUo1=x1+x2+⋯+xk=∑i=1kxi=c1DSKUo2=y1+y2+⋯+yk=∑i=1kxi=c2where(xo=c1/k,yo=c2/k).


## 4.3. Our Privacy-Protection Scheme of Group Friends Distance Query

### 4.3.1. Scenario Description

Sometimes, in LBSs, users want to know their friend’s distance from them. In this case, from the view of location privacy protection, we should ensure that each user in the group could conveniently inquire the friend’s distance without exposing his own location information or knowing his friend’s location. This case is similar to another application in LBSs that the merchants or shops would like to push advertisements to the users based on their locations. The merchants and shops concerned by the group users can safely inquire the distance from the user and decide whether to push advertisements to some user in the group without knowing the specific location of the users.


### 4.3.2. Scheme Description

Assume that the group userp1 applies for the friend’s distance query services:(1)
The userp1 sends the friend distance query service request to the SP so as to query the friend pi’s distance.(2)
After receiving the query request, the SP calculates the function of the ciphertextsUdis according to (4e) and sends Udis to the user p1:(4e)Udis=eEPKx1+αEPK-xi-αhr,EPKx1+αEPK-xi-αhrh1r′×eEPKy1+βEPK-yi-βhr,EPKy1+βEPK-yi-βhrh1r′hr3.(3)
p1 receives the value of Udis and decrypts it so as to obtain the distance between p1 and pi according to (4f): (4f)DSKUdis=x1-xi2+y1-yi2modN.


## 4.3.1. Scenario Description

Sometimes, in LBSs, users want to know their friend’s distance from them. In this case, from the view of location privacy protection, we should ensure that each user in the group could conveniently inquire the friend’s distance without exposing his own location information or knowing his friend’s location. This case is similar to another application in LBSs that the merchants or shops would like to push advertisements to the users based on their locations. The merchants and shops concerned by the group users can safely inquire the distance from the user and decide whether to push advertisements to some user in the group without knowing the specific location of the users.


## 4.3.2. Scheme Description

Assume that the group userp1 applies for the friend’s distance query services:(1)
The userp1 sends the friend distance query service request to the SP so as to query the friend pi’s distance.(2)
After receiving the query request, the SP calculates the function of the ciphertextsUdis according to (4e) and sends Udis to the user p1:(4e)Udis=eEPKx1+αEPK-xi-αhr,EPKx1+αEPK-xi-αhrh1r′×eEPKy1+βEPK-yi-βhr,EPKy1+βEPK-yi-βhrh1r′hr3.(3)
p1 receives the value of Udis and decrypts it so as to obtain the distance between p1 and pi according to (4f): (4f)DSKUdis=x1-xi2+y1-yi2modN.


## 5. Safety and Performance Analysis

### 5.1. Validity Analysis

Theorem 5.
In the scheme proposed in Section4.1 of this paper, the group users can convert the group POI location query to the query of the corresponding centroid of the group.Proof.
Based on the homomorphism property of BGN cryptosystem, the correctness of our method to get the center location can be further proven:(5)DSKEPKx1∧w1×EPKx2∧w2×⋯×EPKxk∧wkhr=DSKEPKx1+α1w1×EPKx2+α2w2×⋯×EPKxk+αkwkhr=DSKgx1gα1hr1w1×gx2gα2hr2w2×⋯×gxkgαkhrkwk×hr=DSKgx1w1gw1α1hr1w1×gx2w2gw2α2hr2w2×⋯×gxkwkgwkαkhrkwk×hr=DSKgx1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαkhr1w1+r2w2+⋯+rkwk+r1w1+r2w2+⋯+rkwkhr=DSKgx1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαkhr1w1+r2w2+⋯+rkwk+r1w1+r2w2+⋯+rkwk+r=x1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαk=∑i=1kwixi∧=XG.Similarly, we can prove:(6)DSKEPKy1∧w1×EPKy2∧w2×⋯×EPKyk∧wkhr=∑i=1kwiyi∧=YG.In addition, according to the analysis and conclusion in [5], it can be further proven that the scheme in Section 4.1 is valid. The centroid coordinate XG,YG of the user group can be obtained so as to achieve POI query of the group centroid and obtain the applicable LBS results.Theorem 6.
In the scheme proposed in Section4.2 of this paper, the group users can obtain the best collection location coordinates.Proof.
First, we can calculate the best collection location by solving mathematical minimization problem. Compute the value of coordinate of pointOxo,yo which satisfies the condition dmin=min⁡(∑i=1kxo-xi2+yo-yi2).
Solve the following problem:(7)dmin=min⁡kxo2+yo2-2xox1+x2+⋯+xk-2yoy1+y2+⋯+yk+x12+x22+⋯+xk2+y12+y22+⋯+yk2=min⁡kxo2+yo2-2xoc1-2yoc2+c3.
Here,k,c1,c2,c3 are all constants:(8)c1=∑i=1kxi;c2=∑i=1kyi;c3=∑i=1kxi2+yi2.
SetZ=k(xo2+yo2)-2xoc1-2yoc2+c3, and take the partial derivative of Z: (9)∂Z∂xo=2kxo-2c1;∂Z∂yo=2kyo-2c2;∂2Z∂xo2=2k>0∂2Z∂yo2=2k>0
Therefore the minimum value ofZ=k(xo2+yo2)-2xoc1-2yoc2+c3 is obtained at the point (xo=c1/k,yo=c2/k), which is also the best gathering location for the group G.
Furthermore, we can prove the equation as follows by the homomorphism property of BGN cryptosystem:(10)DSKEPKx1∧×EPKx2∧×⋯×EPKxk∧hr=DSKEPKx1+α1×EPKx2+α2×⋯×EPKxk+αkhr=DSKgx1gα1hr1×gx2gα2hr2×⋯×gxkgαkhrk×hr=DSKgx1+x2+⋯+xk+α1+α2+⋯+αkhr1+r2+⋯+rk+r1+r2+⋯+rkhr=DSKgx1+x2+⋯+xkhr1+r2+⋯+rk+r1+r2+⋯+rk+r=x1+x2+⋯+xk=∑i=1kxi=c1and(11)DSKEPKy1∧×EPKy2∧×⋯×EPKyk∧hr′=DSKEPKy1+β1×EPKx2+β2×⋯×EPKxk+βkhr′=c2.
Additionally, we must notice that the best collection location point here is decided by the minimum sum of distances. In reality, we should also consider that the time interval between the first user with the shortest distancedoi and the last user with the longest distance doj is too long beyond the group users’ tolerance levels. Assuming that the acceptable max time interval is Δt, and when under the condition of the same velocity vi=vj=v, it is equal to solve the minimum value problem with an added constraint: doi-doj/v≤Δt. Moreover, if the users’ velocities are different, the added constraint is doi/vi-doj/vj≤Δt.Theorem 7.
In the scheme proposed in Section4.3 of this paper, the group users can obtain the friend’s distance value.Proof.
(12) D S K e E P K x 1 + α E P K - x i - α h r , E P K x 1 + α E P K - x i - α h r h 1 r ′ × e E P K y 1 + β E P K - y i - β h r , E P K y 1 + β E P K - y i - β h r h 1 r ′ h 2 r 3 = D S K e g x 1 g α h r 1 g - x i g - α h r 2 h r , g x 1 g α h r 1 g - x i g - α h r 2 h r h 1 r ′ × e g y 1 g β h r 1 ′ g - y i g - β h r 2 ′ h r , g y 1 g β h r 1 ′ g - y i g - β h r 2 ′ h r h 1 r ′ h 2 r 3 = D S K e g x 1 - x i h r 1 + r 2 + r , g x 1 - x i h r 1 + r 2 + r h 1 r ′ × e g y 1 - y i h r 1 ′ + r 2 ′ + r , g y 1 - y i h r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g x 1 - x i + μ q 2 r 1 + r 2 + r , g x 1 - x i + μ q 2 r 1 + r 2 + r h 1 r ′ × e g y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r , g y 1 - y i + + μ q 2 r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g , g x 1 - x i + μ q 2 r 1 + r 2 + r x 1 - x i + μ q 2 r 1 + r 2 + r h 1 r ′ × e g , g y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g , g x 1 - x i x 1 - x i h 1 r ′ + μ q 2 r 1 + r 2 + r r 1 + r 2 + r + x 1 r 1 + r 2 + r - x i r 1 + r 2 + r × e g , g y 1 - y i y 1 - y i h 1 r ′ + μ q 2 r 1 ′ + r 2 ′ + r r 1 ′ + r 2 ′ + r + y 1 r 1 ′ + r 2 ′ + r - y i r 1 ′ + r 2 ′ + r h 2 r 3 = x 1 - x i x 1 - x i + y 1 - y i y 1 - y i  m o d  N = x 1 - x i 2 + y 1 - y i 2   m o d  Nwhere h∈G0,h1∈G1.
Therefore, Theorem7 is proven.


### 5.2. Privacy Security Analysis

#### 5.2.1. The Quantitative Measurements of the Privacy Security and the Quality of LBSs

In this section, some quantitative measurements of privacy security and quality of services are given according to our method. In our privacy model, the quantitative measurements can be obtained easily by the relationships between the group center location and each user’s real location.( 1 ) The geometric measures of the group location privacy-preserving(a) The location privacy protection distance: it is the Euclidean distance between the userpi and the determined centroid, which is defined as(13)DisLPi2=XG-xi2+YG-yi2.(b) The maximum distance of the group privacy protection: assuming that the maximum distance is obtained between the group userpi and the center location, it can be defined as(14)DisLPmax2=max⁡XG-xi2+YG-yi2.(c) The minimum distance of the group privacy protection: assuming that the minimum distance is obtained between the group userpi and the centroid, it can be defined as(15)DisLPmin2=min⁡XG-xi2+YG-yi2.(d) The location privacy protection angle: it refers to the declination angle between the userpi and the group center, which is defined as (16)θLPi=arctan⁡YG-yiXG-xi;YG≠yi,XG≠xi.Thus, the measurements proposed are very suitable for our privacy model. It is possible for the user to easily judge and control the privacy protection degree by the measurements.Theorem 8.
The users in the group can adjust the weight sequencew1,w2,⋯,wk to adjust the values of DisLPi and θLPi so as to freely control the degree of the location privacy-protection according to their own privacy request.Proof.
From the perspective of LBSs, the user gets the query results according to his own position. In our method, all the users in the group get the query results from the SP according to the group center instead of their own positions. Especially, because the users in the group have different geographic locations, the distance of the group center location to different users in the group may be different, which can be seen in Figure4. p1,⋯,p4 are the users who formed the group to get LBSs. Their geolocation coordinates are x1,y1,⋯,x4,y4. They can calculate the group center oxG,yG and send o to the SP to get query results. Therefore, they can get the good quality of services without exposing their own locations. However, in this case, there is a distance from each user to the group center. The distance is changeable according to the value of DisLPi. For instance, in the GNN query, because the query is converted to the NN query, the group center is the anchor point to the SP. Thus, with the increase of DisLPi, the effect of location privacy-protection for the user pi improves. Conversely, because the group center is farther away from pi, the quality of the GNN query service might be worse. Furthermore, in Figure 4, if DisLP1>DisLP2, the effect of location privacy protection for p1is better than the effect for p2.Figure 4
The geometric measures of the group location privacy protection.BecauseXG,YG=(∑j=1kwjxj∧,∑i=1kwjyj∧), we can get the equation as follows:(17)DisLPi2=XG-xi2+YG-yi2=∑j=1kwjxj∧-xi2+∑j=1kwjyj∧-yi2.From the above equation, since(xi,yi) is not changeable in a query, the value of DisLPi mainly depends on the group center XG,YG. XG,YG relies on the weight coefficients and the noise parameters assigned to each user in the group by pi. Generally, the noise sequence is fixed. Ultimately, DisLPi is determined by the weight coefficients w1,w2,⋯,wk. pi can increase or decrease DisLPi by adjusting the weight coefficients assigned to different users in the group in order to get better service quality or better location privacy in LBSs. Meanwhile, by adjusting the values of w1,w2,⋯,wk, pi can weaken or strengthen the contribution brought by each user’s location to the computation of group center according to the characteristics of the users, such as their reliability, online time, intimacy relationship, and the distance.Usually, each user in the group has different requirements for location privacy-protection. The user who has the highest request for location privacy-preserving always should have the largest privacy-protection distanceDisLPmax. However, the user who has the higher request for the quality of services always has smaller privacy-protection distance DisLPmin in order to ensure that the query location of NN is closest to himself. Therefore, users in the group can measure and control the degree of privacy protection and quality of services.Similarly, from the definition ofθLPi, we can also get the following equation:(18)θLPi=arctan⁡YG-yiXG-xi=arctan⁡∑j=1kwjyj∧-yi∑j=1kwjxj∧-xi.θ L P i stands for the protecting extent of the separate longitude and latitude of pi. The value of θLPi can be decided by w1,w2,⋯,wk too. Especially, if XG≠xi;YG=yi, it only realizes the obscuration of the longitude of pi’s real location coordinate. If XG=xi;YG≠yi, the protection only realizes the obscuration of the latitude of pi’s location. Additionally, if YG=yi;XG=xi, the degree of the protection for pi is nearly zero, but the quality of LBSs, such as GNN query, is best. Therefore, pi can also change the values of w1,w2,⋯,wk for adjusting the value of θLPi. Compared with DisLPi, θLPi makes it possible for pi to measure and control the effect of location privacy-protection from a smaller granularity.(2) The geometric measures of the GNN serviceAs shown in Figure5, assume that the service result of the current GNN query returned to the group is the point S. Its angle with o is denoted as θOP. The Euclidean distance between S and pi is denoted as Di, and the Euclidean distance between S and O is DisOP. Then the geometric measure of the quality of the user pi’s NN query service in the group can be defined as the actual distance between the user pi and S.Figure 5
The geometric measures of the quality of GNN query service.In order to simplify the problem description and facilitate quantitative measurement, the Euclidean distanceDi is used to stand for the actual distance between S and pi in the geographical map. So we can have(19)Di2=DisLP2+DisOP2+2DisLP×DisOPcos⁡θOP-θLP.What is more, from the perspective of a single user in the group, when the NN query result isS, the actual traffic distance on the map between the user pi and S can directly measure the quality of the current service obtained by pi. Obviously, from the view of the single user pi, the smaller Di is, the better the quality of NN query service is. However, from the perspective of the whole group, it is necessary to consider the overall quality of services after forming the group. Therefore, calculating the total distances from S to all the users in the group is reasonable. The smaller ∑i=1kDi is, the better the quality of current GNN query services is.


#### 5.2.2. Privacy Security Analysis

In fact, in LBSs, exposing precise user positions raises user privacy concerns, especially if the SP is not fully trusted. To enable the secure applications of private user locations in nontrusted networks, we present three kinds of group location privacy protection schemes in three important application scenarios. In our method, there is no need to provide individual location data of each user to the SP. Only the aggregation result of the group users’ locations is usually required to obtain the corresponding query results [21]. In our schemes, the aggregation results are different aggregated computations of the ciphertexts from the users’ locations in the group.Theorem 9.
The schemes in Sections4.1, 4.2, and 4.3 in this paper can realize the group location privacy-protection, as well as each user’s location privacy-protection in the group. Moreover, they can resist the collusion attack and the dynamic distance interaction attack.Proof.
( 1 ) In the scheme of Section 4.1, the group users p2,⋯,pk encrypt their real location coordinates after noise perturbation and weights adding by using the public key of the user p1 who has applied for the LBSs. Because the users are independent of one another, the encryption of each user’s location can be calculated in parallel. Then the SP completes the intermediate outsourced calculation of the ciphertexts encrypted by the users in the group and sends the aggregated result of the ciphertexts back to p1. At last, p1 decrypts the result by using his own private key to obtain the group center and corresponding query service response from the SP.
In the process of LBSs, the users’ locations are encrypted after noise disturbance and weights adding. What the SP can get are the ciphertexts. On one hand, the SP can verify each user’s signature and the source of each ciphertext. So it can prevent the group users from maliciously forging the fake ciphertexts and wasting the computation and network resources. On the other hand, because the SP does not have the user’s private key, it cannot complete the decryption to get the location of each user. Moreover, each user can get none of the other users’ locations. After obtaining the group center, all the users make service requests with the center location as the anchor point. Therefore, both the location privacy-protection of the group and the location privacy-protection of every individual user in the group can be realized.
In the group, the users usep1’s public key to encrypt their own coordinates after adding noise and weights; it is impossible to decrypt the ciphertexts of p1 to obtain his location. Even p2,⋯,pk collude with the SP; they cannot guess the location of p1, because they do not have the private key of p1.
In another case, ifp1 colludes with other l(l<k-2) users in the group, because k-(l+1)>1 is established, the colluded users can only get the sum of at least two users’ location data. Additionally, the data of noise and weights have been added, respectively. It is impossible to guess either specific location of the rest of users in the group. Therefore, the scheme in Section 4.1 can resist the collusion attack of most users in the group.
Particularly, we have the collusion betweenp1 and the SP. The collusion can only be realized by providing p1’s private key directly to the SP for decryption of all the ciphertexts. In this case, the security of p1’s own location privacy and other encryption related applications will be seriously threatened. So, for his own benefit, p1 would not like to choose this way to collude with the SP. The other case is that p1 still keeps his private key secret. Instead, the SP provides all the other users’ ciphertexts received to p1. p1 decrypts the ciphertexts of other users’ locations and shares the locations with SP. In this case, it cannot be ignored that the SP has the group center, which is computed from all the users’ real locations. It can infer the location of p1 according to all the rest of the users’ locations and the center location, which is also unacceptable for p1. So this collusion case may lead to a paradox of the users’ original intention of location privacy-preserving and the threat of his location privacy security. Hence, combining with the game theory of the collaborative position privacy-protection [22], the probability of collusion between p1 and the SP is negligible. In conclusion, the scheme in Section 4.1 can resist the collusion attacks.
( 2 ) Similarly, in the scheme of Sections 4.2 and 4.3, the processes of calculation for the best set position and the group friend’s distance also need the users in the group to encrypt their disturbed and weighted location data. Then the ciphertexts are sent to the SP to get outsourced and aggregated computation. After receiving and decrypting the processed result from the SP, the user can obtain the best collection location for the group and the friend’s distance, respectively. Their privacy security proofs are similar to that of the scheme in Section 4.1, which realize not only the group’s location privacy protection but also the users’ location privacy protection within the group. They can also resist the collusion attacks. Here it is not necessary to repeat the detailed demonstration.
( 3 ) In the dynamic user group queries, the position of p1 is changing every time as he makes a new query request. Because the position of p1 is always changing, even if the attacker can pretend to be the other users in the group to obtain the distances from p1 through multiple requests, the specific position coordinates of p1 cannot be determined yet. Therefore, this scheme can resist the existing distance interaction attack [3].


### 5.3. Characteristics Analysis

As shown in Table2, we will compare the related schemes with ours. In our schemes, the users in the group conduct the encryption in parallel, which brings the high efficiency. The SP performs the outsourcing calculations on the ciphertexts without knowing the real locations of each user. The SP’s strong computation capability is in full use in our method. Moreover, the user can obtain the query service result by only a simple decryption operation.Table 2
Characteristics comparison.
Scheme [3] [4] [5] [6] Ours  Method Distance sum Center location Center location Center location Center location  Network resources occupied Low Low Low High Low  The size of the service result set o ( n ) o ( 1 ) o ( 1 ) o ( 1 ) o ( 1 )  Resistance against the collusion attack between SP and m users m = 0 m = 1 1 ≤ m < k - 1 or m=1 ( with or without the special proxy user) 1 ≤ m < k - 1 1 ≤ m < k  Controllability of the location privacy protection Fine-granularity Coarse-granularity Coarse-granularity Coarse-granularity Fine-granularity  Communication mode Ring-unicast Ring-unicast Star-unicast Group-broadcast Star-unicast  User state Static Static/dynamic Static/dynamic Static Static/dynamicBoth of the schemes in [3, 15] adopt the method of computing the distance sum to obtain the group center and need to get the candidate target locations and each user’s anonymous region in advance. Taking [3] as an example, the number of the query nodes is the number of the users in the group. The SP returns a set of candidate target locations, which needs a filtering algorithm to get the exact target location from the set. Compared with our privacy-protection scheme of GNN query, they bring additional overhead. Meanwhile, the distance leakage may threaten the privacy of the user’s location in the group. References [3, 15] ignore the collusion attacks in their schemes.Additionally, the schemes in [4, 6] also cannot resist the collusion attack between the SP and the multiple users of the group. Both [5] and our method safely calculate the center position of the user group to carry out the GNN query, converting the GNN query problem to the NN query problem. Thus, the number of the query points is only one, that is, the group center. The result of query is certain. There is no need for any added filtering algorithm for selection.In addition, GLP protocol [6], the schemes in [5], and our paper all use cryptographic algorithms for location privacy-protection. However, the former requires each user in the group to broadcast the messages to other users for precomputation, which occupies much more network resources than the unicast way of communication in our paper. The latter uses Paillier algorithm based on secret sharing to compute the center location. Although the collusion attack is considered in [5], the collusion attack between the proxy user and the SP cannot be resisted at all. The proxy user is essentially the same as the center server we do not want. It is also the performance bottleneck of the protection system. Compared with our scheme, neither of schemes in [5, 6] takes into account the collusion between the SP and all the users of the group. Moreover, their computation cost is larger, and the users in the group cannot measure or control the degree of privacy protection and the quality of query services.In the single group query service, the scheme proposed by us only needs the users to encrypt their respective disturbed locations once. If the complexity of the signature algorithm is ignored, the computation time complexity isoT. It is equal to the complexity of BGN encryption. In the three different application scenarios of LBSs, the users’ mobile terminals only need to separately calculate once for the ciphertexts of their own coordinates, and the encryption of each user can be highly parallel processing. Particularly, because only the user who initiates the query service needs to perform the decryption algorithm to get the group center, his computation complexity is o2T. It is the computation complexity of the encryption and decryption algorithms of BGN cryptosystem.The main computation of the SP is the aggregation of all the ciphertexts fromk users. Because the ciphertexts are integers in BGN cryptosystem, in simple terms, the complexity is equal to the multiplication of k integers. Furthermore, the aggregation can also be carried out efficiently by parallel multiplication so as to reduce the waiting time of response. In addition, the communication cost mainly comes from the k ciphertext messages sent by the individual users in star-unicast mode and the broadcast message for informing the group center. In conclusion, compared with the related classic researches, our method has less computation and communication overheads in general.


## 5.1. Validity Analysis

Theorem 5.
In the scheme proposed in Section4.1 of this paper, the group users can convert the group POI location query to the query of the corresponding centroid of the group.Proof.
Based on the homomorphism property of BGN cryptosystem, the correctness of our method to get the center location can be further proven:(5)DSKEPKx1∧w1×EPKx2∧w2×⋯×EPKxk∧wkhr=DSKEPKx1+α1w1×EPKx2+α2w2×⋯×EPKxk+αkwkhr=DSKgx1gα1hr1w1×gx2gα2hr2w2×⋯×gxkgαkhrkwk×hr=DSKgx1w1gw1α1hr1w1×gx2w2gw2α2hr2w2×⋯×gxkwkgwkαkhrkwk×hr=DSKgx1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαkhr1w1+r2w2+⋯+rkwk+r1w1+r2w2+⋯+rkwkhr=DSKgx1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαkhr1w1+r2w2+⋯+rkwk+r1w1+r2w2+⋯+rkwk+r=x1w1+x2w2+⋯+xkwk+w1α1+w2α2+⋯+wkαk=∑i=1kwixi∧=XG.Similarly, we can prove:(6)DSKEPKy1∧w1×EPKy2∧w2×⋯×EPKyk∧wkhr=∑i=1kwiyi∧=YG.In addition, according to the analysis and conclusion in [5], it can be further proven that the scheme in Section 4.1 is valid. The centroid coordinate XG,YG of the user group can be obtained so as to achieve POI query of the group centroid and obtain the applicable LBS results.Theorem 6.
In the scheme proposed in Section4.2 of this paper, the group users can obtain the best collection location coordinates.Proof.
First, we can calculate the best collection location by solving mathematical minimization problem. Compute the value of coordinate of pointOxo,yo which satisfies the condition dmin=min⁡(∑i=1kxo-xi2+yo-yi2).
Solve the following problem:(7)dmin=min⁡kxo2+yo2-2xox1+x2+⋯+xk-2yoy1+y2+⋯+yk+x12+x22+⋯+xk2+y12+y22+⋯+yk2=min⁡kxo2+yo2-2xoc1-2yoc2+c3.
Here,k,c1,c2,c3 are all constants:(8)c1=∑i=1kxi;c2=∑i=1kyi;c3=∑i=1kxi2+yi2.
SetZ=k(xo2+yo2)-2xoc1-2yoc2+c3, and take the partial derivative of Z: (9)∂Z∂xo=2kxo-2c1;∂Z∂yo=2kyo-2c2;∂2Z∂xo2=2k>0∂2Z∂yo2=2k>0
Therefore the minimum value ofZ=k(xo2+yo2)-2xoc1-2yoc2+c3 is obtained at the point (xo=c1/k,yo=c2/k), which is also the best gathering location for the group G.
Furthermore, we can prove the equation as follows by the homomorphism property of BGN cryptosystem:(10)DSKEPKx1∧×EPKx2∧×⋯×EPKxk∧hr=DSKEPKx1+α1×EPKx2+α2×⋯×EPKxk+αkhr=DSKgx1gα1hr1×gx2gα2hr2×⋯×gxkgαkhrk×hr=DSKgx1+x2+⋯+xk+α1+α2+⋯+αkhr1+r2+⋯+rk+r1+r2+⋯+rkhr=DSKgx1+x2+⋯+xkhr1+r2+⋯+rk+r1+r2+⋯+rk+r=x1+x2+⋯+xk=∑i=1kxi=c1and(11)DSKEPKy1∧×EPKy2∧×⋯×EPKyk∧hr′=DSKEPKy1+β1×EPKx2+β2×⋯×EPKxk+βkhr′=c2.
Additionally, we must notice that the best collection location point here is decided by the minimum sum of distances. In reality, we should also consider that the time interval between the first user with the shortest distancedoi and the last user with the longest distance doj is too long beyond the group users’ tolerance levels. Assuming that the acceptable max time interval is Δt, and when under the condition of the same velocity vi=vj=v, it is equal to solve the minimum value problem with an added constraint: doi-doj/v≤Δt. Moreover, if the users’ velocities are different, the added constraint is doi/vi-doj/vj≤Δt.Theorem 7.
In the scheme proposed in Section4.3 of this paper, the group users can obtain the friend’s distance value.Proof.
(12) D S K e E P K x 1 + α E P K - x i - α h r , E P K x 1 + α E P K - x i - α h r h 1 r ′ × e E P K y 1 + β E P K - y i - β h r , E P K y 1 + β E P K - y i - β h r h 1 r ′ h 2 r 3 = D S K e g x 1 g α h r 1 g - x i g - α h r 2 h r , g x 1 g α h r 1 g - x i g - α h r 2 h r h 1 r ′ × e g y 1 g β h r 1 ′ g - y i g - β h r 2 ′ h r , g y 1 g β h r 1 ′ g - y i g - β h r 2 ′ h r h 1 r ′ h 2 r 3 = D S K e g x 1 - x i h r 1 + r 2 + r , g x 1 - x i h r 1 + r 2 + r h 1 r ′ × e g y 1 - y i h r 1 ′ + r 2 ′ + r , g y 1 - y i h r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g x 1 - x i + μ q 2 r 1 + r 2 + r , g x 1 - x i + μ q 2 r 1 + r 2 + r h 1 r ′ × e g y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r , g y 1 - y i + + μ q 2 r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g , g x 1 - x i + μ q 2 r 1 + r 2 + r x 1 - x i + μ q 2 r 1 + r 2 + r h 1 r ′ × e g , g y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r y 1 - y i + μ q 2 r 1 ′ + r 2 ′ + r h 1 r ′ h 2 r 3 = D S K e g , g x 1 - x i x 1 - x i h 1 r ′ + μ q 2 r 1 + r 2 + r r 1 + r 2 + r + x 1 r 1 + r 2 + r - x i r 1 + r 2 + r × e g , g y 1 - y i y 1 - y i h 1 r ′ + μ q 2 r 1 ′ + r 2 ′ + r r 1 ′ + r 2 ′ + r + y 1 r 1 ′ + r 2 ′ + r - y i r 1 ′ + r 2 ′ + r h 2 r 3 = x 1 - x i x 1 - x i + y 1 - y i y 1 - y i  m o d  N = x 1 - x i 2 + y 1 - y i 2   m o d  Nwhere h∈G0,h1∈G1.
Therefore, Theorem7 is proven.


## 5.2. Privacy Security Analysis

### 5.2.1. The Quantitative Measurements of the Privacy Security and the Quality of LBSs

In this section, some quantitative measurements of privacy security and quality of services are given according to our method. In our privacy model, the quantitative measurements can be obtained easily by the relationships between the group center location and each user’s real location.( 1 ) The geometric measures of the group location privacy-preserving(a) The location privacy protection distance: it is the Euclidean distance between the userpi and the determined centroid, which is defined as(13)DisLPi2=XG-xi2+YG-yi2.(b) The maximum distance of the group privacy protection: assuming that the maximum distance is obtained between the group userpi and the center location, it can be defined as(14)DisLPmax2=max⁡XG-xi2+YG-yi2.(c) The minimum distance of the group privacy protection: assuming that the minimum distance is obtained between the group userpi and the centroid, it can be defined as(15)DisLPmin2=min⁡XG-xi2+YG-yi2.(d) The location privacy protection angle: it refers to the declination angle between the userpi and the group center, which is defined as (16)θLPi=arctan⁡YG-yiXG-xi;YG≠yi,XG≠xi.Thus, the measurements proposed are very suitable for our privacy model. It is possible for the user to easily judge and control the privacy protection degree by the measurements.Theorem 8.
The users in the group can adjust the weight sequencew1,w2,⋯,wk to adjust the values of DisLPi and θLPi so as to freely control the degree of the location privacy-protection according to their own privacy request.Proof.
From the perspective of LBSs, the user gets the query results according to his own position. In our method, all the users in the group get the query results from the SP according to the group center instead of their own positions. Especially, because the users in the group have different geographic locations, the distance of the group center location to different users in the group may be different, which can be seen in Figure4. p1,⋯,p4 are the users who formed the group to get LBSs. Their geolocation coordinates are x1,y1,⋯,x4,y4. They can calculate the group center oxG,yG and send o to the SP to get query results. Therefore, they can get the good quality of services without exposing their own locations. However, in this case, there is a distance from each user to the group center. The distance is changeable according to the value of DisLPi. For instance, in the GNN query, because the query is converted to the NN query, the group center is the anchor point to the SP. Thus, with the increase of DisLPi, the effect of location privacy-protection for the user pi improves. Conversely, because the group center is farther away from pi, the quality of the GNN query service might be worse. Furthermore, in Figure 4, if DisLP1>DisLP2, the effect of location privacy protection for p1is better than the effect for p2.Figure 4
The geometric measures of the group location privacy protection.BecauseXG,YG=(∑j=1kwjxj∧,∑i=1kwjyj∧), we can get the equation as follows:(17)DisLPi2=XG-xi2+YG-yi2=∑j=1kwjxj∧-xi2+∑j=1kwjyj∧-yi2.From the above equation, since(xi,yi) is not changeable in a query, the value of DisLPi mainly depends on the group center XG,YG. XG,YG relies on the weight coefficients and the noise parameters assigned to each user in the group by pi. Generally, the noise sequence is fixed. Ultimately, DisLPi is determined by the weight coefficients w1,w2,⋯,wk. pi can increase or decrease DisLPi by adjusting the weight coefficients assigned to different users in the group in order to get better service quality or better location privacy in LBSs. Meanwhile, by adjusting the values of w1,w2,⋯,wk, pi can weaken or strengthen the contribution brought by each user’s location to the computation of group center according to the characteristics of the users, such as their reliability, online time, intimacy relationship, and the distance.Usually, each user in the group has different requirements for location privacy-protection. The user who has the highest request for location privacy-preserving always should have the largest privacy-protection distanceDisLPmax. However, the user who has the higher request for the quality of services always has smaller privacy-protection distance DisLPmin in order to ensure that the query location of NN is closest to himself. Therefore, users in the group can measure and control the degree of privacy protection and quality of services.Similarly, from the definition ofθLPi, we can also get the following equation:(18)θLPi=arctan⁡YG-yiXG-xi=arctan⁡∑j=1kwjyj∧-yi∑j=1kwjxj∧-xi.θ L P i stands for the protecting extent of the separate longitude and latitude of pi. The value of θLPi can be decided by w1,w2,⋯,wk too. Especially, if XG≠xi;YG=yi, it only realizes the obscuration of the longitude of pi’s real location coordinate. If XG=xi;YG≠yi, the protection only realizes the obscuration of the latitude of pi’s location. Additionally, if YG=yi;XG=xi, the degree of the protection for pi is nearly zero, but the quality of LBSs, such as GNN query, is best. Therefore, pi can also change the values of w1,w2,⋯,wk for adjusting the value of θLPi. Compared with DisLPi, θLPi makes it possible for pi to measure and control the effect of location privacy-protection from a smaller granularity.(2) The geometric measures of the GNN serviceAs shown in Figure5, assume that the service result of the current GNN query returned to the group is the point S. Its angle with o is denoted as θOP. The Euclidean distance between S and pi is denoted as Di, and the Euclidean distance between S and O is DisOP. Then the geometric measure of the quality of the user pi’s NN query service in the group can be defined as the actual distance between the user pi and S.Figure 5
The geometric measures of the quality of GNN query service.In order to simplify the problem description and facilitate quantitative measurement, the Euclidean distanceDi is used to stand for the actual distance between S and pi in the geographical map. So we can have(19)Di2=DisLP2+DisOP2+2DisLP×DisOPcos⁡θOP-θLP.What is more, from the perspective of a single user in the group, when the NN query result isS, the actual traffic distance on the map between the user pi and S can directly measure the quality of the current service obtained by pi. Obviously, from the view of the single user pi, the smaller Di is, the better the quality of NN query service is. However, from the perspective of the whole group, it is necessary to consider the overall quality of services after forming the group. Therefore, calculating the total distances from S to all the users in the group is reasonable. The smaller ∑i=1kDi is, the better the quality of current GNN query services is.


### 5.2.2. Privacy Security Analysis

In fact, in LBSs, exposing precise user positions raises user privacy concerns, especially if the SP is not fully trusted. To enable the secure applications of private user locations in nontrusted networks, we present three kinds of group location privacy protection schemes in three important application scenarios. In our method, there is no need to provide individual location data of each user to the SP. Only the aggregation result of the group users’ locations is usually required to obtain the corresponding query results [21]. In our schemes, the aggregation results are different aggregated computations of the ciphertexts from the users’ locations in the group.Theorem 9.
The schemes in Sections4.1, 4.2, and 4.3 in this paper can realize the group location privacy-protection, as well as each user’s location privacy-protection in the group. Moreover, they can resist the collusion attack and the dynamic distance interaction attack.Proof.
( 1 ) In the scheme of Section 4.1, the group users p2,⋯,pk encrypt their real location coordinates after noise perturbation and weights adding by using the public key of the user p1 who has applied for the LBSs. Because the users are independent of one another, the encryption of each user’s location can be calculated in parallel. Then the SP completes the intermediate outsourced calculation of the ciphertexts encrypted by the users in the group and sends the aggregated result of the ciphertexts back to p1. At last, p1 decrypts the result by using his own private key to obtain the group center and corresponding query service response from the SP.
In the process of LBSs, the users’ locations are encrypted after noise disturbance and weights adding. What the SP can get are the ciphertexts. On one hand, the SP can verify each user’s signature and the source of each ciphertext. So it can prevent the group users from maliciously forging the fake ciphertexts and wasting the computation and network resources. On the other hand, because the SP does not have the user’s private key, it cannot complete the decryption to get the location of each user. Moreover, each user can get none of the other users’ locations. After obtaining the group center, all the users make service requests with the center location as the anchor point. Therefore, both the location privacy-protection of the group and the location privacy-protection of every individual user in the group can be realized.
In the group, the users usep1’s public key to encrypt their own coordinates after adding noise and weights; it is impossible to decrypt the ciphertexts of p1 to obtain his location. Even p2,⋯,pk collude with the SP; they cannot guess the location of p1, because they do not have the private key of p1.
In another case, ifp1 colludes with other l(l<k-2) users in the group, because k-(l+1)>1 is established, the colluded users can only get the sum of at least two users’ location data. Additionally, the data of noise and weights have been added, respectively. It is impossible to guess either specific location of the rest of users in the group. Therefore, the scheme in Section 4.1 can resist the collusion attack of most users in the group.
Particularly, we have the collusion betweenp1 and the SP. The collusion can only be realized by providing p1’s private key directly to the SP for decryption of all the ciphertexts. In this case, the security of p1’s own location privacy and other encryption related applications will be seriously threatened. So, for his own benefit, p1 would not like to choose this way to collude with the SP. The other case is that p1 still keeps his private key secret. Instead, the SP provides all the other users’ ciphertexts received to p1. p1 decrypts the ciphertexts of other users’ locations and shares the locations with SP. In this case, it cannot be ignored that the SP has the group center, which is computed from all the users’ real locations. It can infer the location of p1 according to all the rest of the users’ locations and the center location, which is also unacceptable for p1. So this collusion case may lead to a paradox of the users’ original intention of location privacy-preserving and the threat of his location privacy security. Hence, combining with the game theory of the collaborative position privacy-protection [22], the probability of collusion between p1 and the SP is negligible. In conclusion, the scheme in Section 4.1 can resist the collusion attacks.
( 2 ) Similarly, in the scheme of Sections 4.2 and 4.3, the processes of calculation for the best set position and the group friend’s distance also need the users in the group to encrypt their disturbed and weighted location data. Then the ciphertexts are sent to the SP to get outsourced and aggregated computation. After receiving and decrypting the processed result from the SP, the user can obtain the best collection location for the group and the friend’s distance, respectively. Their privacy security proofs are similar to that of the scheme in Section 4.1, which realize not only the group’s location privacy protection but also the users’ location privacy protection within the group. They can also resist the collusion attacks. Here it is not necessary to repeat the detailed demonstration.
( 3 ) In the dynamic user group queries, the position of p1 is changing every time as he makes a new query request. Because the position of p1 is always changing, even if the attacker can pretend to be the other users in the group to obtain the distances from p1 through multiple requests, the specific position coordinates of p1 cannot be determined yet. Therefore, this scheme can resist the existing distance interaction attack [3].


## 5.2.1. The Quantitative Measurements of the Privacy Security and the Quality of LBSs

In this section, some quantitative measurements of privacy security and quality of services are given according to our method. In our privacy model, the quantitative measurements can be obtained easily by the relationships between the group center location and each user’s real location.( 1 ) The geometric measures of the group location privacy-preserving(a) The location privacy protection distance: it is the Euclidean distance between the userpi and the determined centroid, which is defined as(13)DisLPi2=XG-xi2+YG-yi2.(b) The maximum distance of the group privacy protection: assuming that the maximum distance is obtained between the group userpi and the center location, it can be defined as(14)DisLPmax2=max⁡XG-xi2+YG-yi2.(c) The minimum distance of the group privacy protection: assuming that the minimum distance is obtained between the group userpi and the centroid, it can be defined as(15)DisLPmin2=min⁡XG-xi2+YG-yi2.(d) The location privacy protection angle: it refers to the declination angle between the userpi and the group center, which is defined as (16)θLPi=arctan⁡YG-yiXG-xi;YG≠yi,XG≠xi.Thus, the measurements proposed are very suitable for our privacy model. It is possible for the user to easily judge and control the privacy protection degree by the measurements.Theorem 8.
The users in the group can adjust the weight sequencew1,w2,⋯,wk to adjust the values of DisLPi and θLPi so as to freely control the degree of the location privacy-protection according to their own privacy request.Proof.
From the perspective of LBSs, the user gets the query results according to his own position. In our method, all the users in the group get the query results from the SP according to the group center instead of their own positions. Especially, because the users in the group have different geographic locations, the distance of the group center location to different users in the group may be different, which can be seen in Figure4. p1,⋯,p4 are the users who formed the group to get LBSs. Their geolocation coordinates are x1,y1,⋯,x4,y4. They can calculate the group center oxG,yG and send o to the SP to get query results. Therefore, they can get the good quality of services without exposing their own locations. However, in this case, there is a distance from each user to the group center. The distance is changeable according to the value of DisLPi. For instance, in the GNN query, because the query is converted to the NN query, the group center is the anchor point to the SP. Thus, with the increase of DisLPi, the effect of location privacy-protection for the user pi improves. Conversely, because the group center is farther away from pi, the quality of the GNN query service might be worse. Furthermore, in Figure 4, if DisLP1>DisLP2, the effect of location privacy protection for p1is better than the effect for p2.Figure 4
The geometric measures of the group location privacy protection.BecauseXG,YG=(∑j=1kwjxj∧,∑i=1kwjyj∧), we can get the equation as follows:(17)DisLPi2=XG-xi2+YG-yi2=∑j=1kwjxj∧-xi2+∑j=1kwjyj∧-yi2.From the above equation, since(xi,yi) is not changeable in a query, the value of DisLPi mainly depends on the group center XG,YG. XG,YG relies on the weight coefficients and the noise parameters assigned to each user in the group by pi. Generally, the noise sequence is fixed. Ultimately, DisLPi is determined by the weight coefficients w1,w2,⋯,wk. pi can increase or decrease DisLPi by adjusting the weight coefficients assigned to different users in the group in order to get better service quality or better location privacy in LBSs. Meanwhile, by adjusting the values of w1,w2,⋯,wk, pi can weaken or strengthen the contribution brought by each user’s location to the computation of group center according to the characteristics of the users, such as their reliability, online time, intimacy relationship, and the distance.Usually, each user in the group has different requirements for location privacy-protection. The user who has the highest request for location privacy-preserving always should have the largest privacy-protection distanceDisLPmax. However, the user who has the higher request for the quality of services always has smaller privacy-protection distance DisLPmin in order to ensure that the query location of NN is closest to himself. Therefore, users in the group can measure and control the degree of privacy protection and quality of services.Similarly, from the definition ofθLPi, we can also get the following equation:(18)θLPi=arctan⁡YG-yiXG-xi=arctan⁡∑j=1kwjyj∧-yi∑j=1kwjxj∧-xi.θ L P i stands for the protecting extent of the separate longitude and latitude of pi. The value of θLPi can be decided by w1,w2,⋯,wk too. Especially, if XG≠xi;YG=yi, it only realizes the obscuration of the longitude of pi’s real location coordinate. If XG=xi;YG≠yi, the protection only realizes the obscuration of the latitude of pi’s location. Additionally, if YG=yi;XG=xi, the degree of the protection for pi is nearly zero, but the quality of LBSs, such as GNN query, is best. Therefore, pi can also change the values of w1,w2,⋯,wk for adjusting the value of θLPi. Compared with DisLPi, θLPi makes it possible for pi to measure and control the effect of location privacy-protection from a smaller granularity.(2) The geometric measures of the GNN serviceAs shown in Figure5, assume that the service result of the current GNN query returned to the group is the point S. Its angle with o is denoted as θOP. The Euclidean distance between S and pi is denoted as Di, and the Euclidean distance between S and O is DisOP. Then the geometric measure of the quality of the user pi’s NN query service in the group can be defined as the actual distance between the user pi and S.Figure 5
The geometric measures of the quality of GNN query service.In order to simplify the problem description and facilitate quantitative measurement, the Euclidean distanceDi is used to stand for the actual distance between S and pi in the geographical map. So we can have(19)Di2=DisLP2+DisOP2+2DisLP×DisOPcos⁡θOP-θLP.What is more, from the perspective of a single user in the group, when the NN query result isS, the actual traffic distance on the map between the user pi and S can directly measure the quality of the current service obtained by pi. Obviously, from the view of the single user pi, the smaller Di is, the better the quality of NN query service is. However, from the perspective of the whole group, it is necessary to consider the overall quality of services after forming the group. Therefore, calculating the total distances from S to all the users in the group is reasonable. The smaller ∑i=1kDi is, the better the quality of current GNN query services is.


## 5.2.2. Privacy Security Analysis

In fact, in LBSs, exposing precise user positions raises user privacy concerns, especially if the SP is not fully trusted. To enable the secure applications of private user locations in nontrusted networks, we present three kinds of group location privacy protection schemes in three important application scenarios. In our method, there is no need to provide individual location data of each user to the SP. Only the aggregation result of the group users’ locations is usually required to obtain the corresponding query results [21]. In our schemes, the aggregation results are different aggregated computations of the ciphertexts from the users’ locations in the group.Theorem 9.
The schemes in Sections4.1, 4.2, and 4.3 in this paper can realize the group location privacy-protection, as well as each user’s location privacy-protection in the group. Moreover, they can resist the collusion attack and the dynamic distance interaction attack.Proof.
( 1 ) In the scheme of Section 4.1, the group users p2,⋯,pk encrypt their real location coordinates after noise perturbation and weights adding by using the public key of the user p1 who has applied for the LBSs. Because the users are independent of one another, the encryption of each user’s location can be calculated in parallel. Then the SP completes the intermediate outsourced calculation of the ciphertexts encrypted by the users in the group and sends the aggregated result of the ciphertexts back to p1. At last, p1 decrypts the result by using his own private key to obtain the group center and corresponding query service response from the SP.
In the process of LBSs, the users’ locations are encrypted after noise disturbance and weights adding. What the SP can get are the ciphertexts. On one hand, the SP can verify each user’s signature and the source of each ciphertext. So it can prevent the group users from maliciously forging the fake ciphertexts and wasting the computation and network resources. On the other hand, because the SP does not have the user’s private key, it cannot complete the decryption to get the location of each user. Moreover, each user can get none of the other users’ locations. After obtaining the group center, all the users make service requests with the center location as the anchor point. Therefore, both the location privacy-protection of the group and the location privacy-protection of every individual user in the group can be realized.
In the group, the users usep1’s public key to encrypt their own coordinates after adding noise and weights; it is impossible to decrypt the ciphertexts of p1 to obtain his location. Even p2,⋯,pk collude with the SP; they cannot guess the location of p1, because they do not have the private key of p1.
In another case, ifp1 colludes with other l(l<k-2) users in the group, because k-(l+1)>1 is established, the colluded users can only get the sum of at least two users’ location data. Additionally, the data of noise and weights have been added, respectively. It is impossible to guess either specific location of the rest of users in the group. Therefore, the scheme in Section 4.1 can resist the collusion attack of most users in the group.
Particularly, we have the collusion betweenp1 and the SP. The collusion can only be realized by providing p1’s private key directly to the SP for decryption of all the ciphertexts. In this case, the security of p1’s own location privacy and other encryption related applications will be seriously threatened. So, for his own benefit, p1 would not like to choose this way to collude with the SP. The other case is that p1 still keeps his private key secret. Instead, the SP provides all the other users’ ciphertexts received to p1. p1 decrypts the ciphertexts of other users’ locations and shares the locations with SP. In this case, it cannot be ignored that the SP has the group center, which is computed from all the users’ real locations. It can infer the location of p1 according to all the rest of the users’ locations and the center location, which is also unacceptable for p1. So this collusion case may lead to a paradox of the users’ original intention of location privacy-preserving and the threat of his location privacy security. Hence, combining with the game theory of the collaborative position privacy-protection [22], the probability of collusion between p1 and the SP is negligible. In conclusion, the scheme in Section 4.1 can resist the collusion attacks.
( 2 ) Similarly, in the scheme of Sections 4.2 and 4.3, the processes of calculation for the best set position and the group friend’s distance also need the users in the group to encrypt their disturbed and weighted location data. Then the ciphertexts are sent to the SP to get outsourced and aggregated computation. After receiving and decrypting the processed result from the SP, the user can obtain the best collection location for the group and the friend’s distance, respectively. Their privacy security proofs are similar to that of the scheme in Section 4.1, which realize not only the group’s location privacy protection but also the users’ location privacy protection within the group. They can also resist the collusion attacks. Here it is not necessary to repeat the detailed demonstration.
( 3 ) In the dynamic user group queries, the position of p1 is changing every time as he makes a new query request. Because the position of p1 is always changing, even if the attacker can pretend to be the other users in the group to obtain the distances from p1 through multiple requests, the specific position coordinates of p1 cannot be determined yet. Therefore, this scheme can resist the existing distance interaction attack [3].


## 5.3. Characteristics Analysis

As shown in Table2, we will compare the related schemes with ours. In our schemes, the users in the group conduct the encryption in parallel, which brings the high efficiency. The SP performs the outsourcing calculations on the ciphertexts without knowing the real locations of each user. The SP’s strong computation capability is in full use in our method. Moreover, the user can obtain the query service result by only a simple decryption operation.Table 2
Characteristics comparison.
Scheme [3] [4] [5] [6] Ours  Method Distance sum Center location Center location Center location Center location  Network resources occupied Low Low Low High Low  The size of the service result set o ( n ) o ( 1 ) o ( 1 ) o ( 1 ) o ( 1 )  Resistance against the collusion attack between SP and m users m = 0 m = 1 1 ≤ m < k - 1 or m=1 ( with or without the special proxy user) 1 ≤ m < k - 1 1 ≤ m < k  Controllability of the location privacy protection Fine-granularity Coarse-granularity Coarse-granularity Coarse-granularity Fine-granularity  Communication mode Ring-unicast Ring-unicast Star-unicast Group-broadcast Star-unicast  User state Static Static/dynamic Static/dynamic Static Static/dynamicBoth of the schemes in [3, 15] adopt the method of computing the distance sum to obtain the group center and need to get the candidate target locations and each user’s anonymous region in advance. Taking [3] as an example, the number of the query nodes is the number of the users in the group. The SP returns a set of candidate target locations, which needs a filtering algorithm to get the exact target location from the set. Compared with our privacy-protection scheme of GNN query, they bring additional overhead. Meanwhile, the distance leakage may threaten the privacy of the user’s location in the group. References [3, 15] ignore the collusion attacks in their schemes.Additionally, the schemes in [4, 6] also cannot resist the collusion attack between the SP and the multiple users of the group. Both [5] and our method safely calculate the center position of the user group to carry out the GNN query, converting the GNN query problem to the NN query problem. Thus, the number of the query points is only one, that is, the group center. The result of query is certain. There is no need for any added filtering algorithm for selection.In addition, GLP protocol [6], the schemes in [5], and our paper all use cryptographic algorithms for location privacy-protection. However, the former requires each user in the group to broadcast the messages to other users for precomputation, which occupies much more network resources than the unicast way of communication in our paper. The latter uses Paillier algorithm based on secret sharing to compute the center location. Although the collusion attack is considered in [5], the collusion attack between the proxy user and the SP cannot be resisted at all. The proxy user is essentially the same as the center server we do not want. It is also the performance bottleneck of the protection system. Compared with our scheme, neither of schemes in [5, 6] takes into account the collusion between the SP and all the users of the group. Moreover, their computation cost is larger, and the users in the group cannot measure or control the degree of privacy protection and the quality of query services.In the single group query service, the scheme proposed by us only needs the users to encrypt their respective disturbed locations once. If the complexity of the signature algorithm is ignored, the computation time complexity isoT. It is equal to the complexity of BGN encryption. In the three different application scenarios of LBSs, the users’ mobile terminals only need to separately calculate once for the ciphertexts of their own coordinates, and the encryption of each user can be highly parallel processing. Particularly, because only the user who initiates the query service needs to perform the decryption algorithm to get the group center, his computation complexity is o2T. It is the computation complexity of the encryption and decryption algorithms of BGN cryptosystem.The main computation of the SP is the aggregation of all the ciphertexts fromk users. Because the ciphertexts are integers in BGN cryptosystem, in simple terms, the complexity is equal to the multiplication of k integers. Furthermore, the aggregation can also be carried out efficiently by parallel multiplication so as to reduce the waiting time of response. In addition, the communication cost mainly comes from the k ciphertext messages sent by the individual users in star-unicast mode and the broadcast message for informing the group center. In conclusion, compared with the related classic researches, our method has less computation and communication overheads in general.


## 6. Conclusion

Combined with the research status of the location privacy-protection schemes in LBSs, there are still some problems to be solved urgently. Fortunately, these problems have been mainly solved in our paper.( 1 ) Centralized structure depends on the central anonymous server. As it is doubted for reliability, performance bottleneck, weak antiattacking capability, and other problems, it is easy to cause the leakage of user’s location privacy and influence the quality of location service.( 2 ) Privacy protection is mainly applied to the individual user, and less consideration is given to the group location privacy-protection of multiple users that are also practical in the reality.( 3 )Users not only want to share other users’ net resources to obtain better LBSs and achieve privacy protection but also do not want to reveal their own location information to others.( 4 )The degree of privacy protection cannot be quantified or measured, which means that the effects of privacy protection are transparent to the users, and they cannot realize flexible setting and fine-grained control.Our contributions are as follows: based on BGN cryptographic algorithm, three group location privacy-protection schemes of distributed structure are, respectively, proposed according to the classic application scenarios in LBSs, which are GNN query, the best group gathering location query, and the group friend’s distance query services, achievingk-anonymity without anonymous regions. Based on the special privacy homomorphism of BGN cryptosystem, the users encrypt the disturbed and weighted location data for only one time; then the ciphertexts are outsourced and calculated by the SP to obtain a corresponding aggregated result to the three different application scenarios mentioned above. So only one security policy is used; namely, the BGN algorithm is performed only once. It can solve the group location privacy-protection problem in three typical applications in LBSs simultaneously without exposing any group user’s location. Compared with the existing related research results, the analysis proves that the proposed method has a wider range of applications and is more flexible. Users can change the weighting parameters to affect the group center according to the quantitative indicators. The weight sequence is introduced to make it possible to dynamically adjust the influence and contribution of each user’s real location to the group center for realizing fine-granularity control of the effects of the group location privacy-protection. At the same time, it has better performance and can ensure secure and efficient group location privacy-protection in LBSs with lower communication and computation complexity. Furthermore, our schemes can also resist the distance interaction attacks and collusion attacks.



---

*Source: 2414687-2019-02-14.xml*