# Secure and Practical Group Nearest Neighbor Query for Location-Based Services in Cloud Computing

Authors: Jingjing Guo; Jiacong Sun
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Group nearest neighbor (GNN) query enables a group of location-based service (LBS) users to retrieve a point from point of interests (POIs) with the minimum aggregate distance to them. For resource constraints and privacy concerns, LBS provider outsources the encrypted POIs to a powerful cloud server. The encryption-and-outsourcing mechanism brings a challenge for the data utilization. However, as previous work fromk−anonymity technique leaks all contents of POIs and returns an answer set with redundant communication cost, the LBS system cannot work properly with those privacy-preserving schemes. In this paper, we illustrate a secure group nearest neighbor query scheme, which is referred to as SecGNN. It supports the GNN query with nn≥3 LBS users and assures the data privacy and query privacy. Since SecGNN only achieves linear search complexity, an efficiency enhanced scheme (named SecGNN+) is introduced by taking advantage of the KD-tree data structure. Specifically, we convert the GNN problem to the nearest neighbor problem for their centroid, which can be computed by anonymous veto network and Burmester–Desmedt conference key agreement protocols. Furthermore, the SecGNN+ scheme is introduced from the KD-tree data structure and a designed tool, which supports the computation of inner products over ciphertexts. Finally, we run experiments on a real-database and a random database to evaluate the performance of our SecGNN and SecGNN+ schemes. The experimental results show the high efficiency of our proposed schemes.


---

## Body

## 1. Introduction

With the prevalence of mobile phones and the rapid development of wireless, location-based service (LBS) provides the possibility for LBS users to proceed location queries according to their interests [1–3]. For instance, when locating in an unfamiliar place, LBS users can find the nearest restaurant through sending LBS queries to the Google map. A new employee also can find the shortest path to the company by sending a LBS query. Group nearest neighbor (GNN) query, a normal operation in the LBS system, requires LBS users to retrieve a meeting place from POIs with the minimum sum of distances to them.Under the conditions of limited resources and frequent queries, the LBS provider always outsources heavy database of POIs to a powerful cloud server [4]. The LBS provider thus can enjoy the rich storage and computation resources, but database outsourcing raises privacy problems for the private sensitive information. In such a case, the LBS provider chooses the encryption-before-outsourcing mechanism, which avoids the potential leakage of private sensitive information. However, database encryption brings a challenging task for data utilization in the LBS system.Hashem et al. [5] proposed the first privacy-preserving group nearest neighbor query scheme from k−anonymity technique. Users compute and send location regions instead of actual locations to the cloud server to assure the privacy of actual locations. Then, the cloud server searches the POIs over plaintexts and returns an answer set that contains the group nearest neighbor (namely, the meeting place) for actual locations. To evaluate the real GNN from the answer set, the authors proposed a private filter technique to avoid the leakage of actual locations and the meeting place. With spatial technique, users in scheme [6] obfuscate actual locations in cloak regions and construct a single centroid region for the nearest neighbor query. In the second phase, users compute the meeting place from the received answer set by using a special secure multiparty computation. In above schemes, the cloud server returns a superset instead of the real answer, which increases the communication cost.As an improvement, Wu et al. [7, 8] introduced another scheme by hybridizing actual locations with other k−1 dummy locations. Users put their actual locations in a specific position, which is shared among them, and send location sets to the cloud server. The cloud server searches and generates candidate results for locations on the same index in their location sets. Furthermore, it retrieves and returns the real GNN on ciphertext by leveraging generalized pallier encryption [9]. Finally, users decrypt the ciphertext and obtain the meeting place. Unfortunately, all solutions [5–8] adapt k−anonymity technique to assure the privacy of sensitive locations. It is noteworthy that k−anonymity only assures that an attacker can identify the actual location with an advantage at most 1/k, but the content may be leaked. For instance, all candidate results in scheme [8] remain visible and an attacker can identify actual locations with advantage 1/32. The privacy-preserving method cannot satisfy the security requirements in practice.Huang and Vishwanathan [13] proposed two GNN schemes, the centralized and distributed model, from cryptographic theory. The authors leverage garble circuit (GC) and oblivious transfer (OT) to construct a secure multiparty computation protocol. Then, users can jointly compute a meeting place from the secure multiparty computation framework. But the scheme [13] suffers a heavy computation and communication burden. Therefore, we aim to seek for a privacy-preserving GNN scheme based on cryptographic tools with whole security protection and high efficiency.


### 1.1. Our Contributions

In this paper, we design two privacy assurance group nearest neighbor query schemes, SecGNN scheme and SecGNN+ scheme, for the LBS system in cloud computing. The designed SecGNN scheme preserves the data privacy and query privacy, while achieving linear complexity. To enhance query efficiency, we introduce the SecGNN+ scheme based on the tree structure. The main contributions are demonstrated as follows.(1)
We convert the problem of finding group nearest neighbor to the problem of finding a point in POIs with minimum aggregate inner products. Thus, the construction of the secure GNN scheme is modeled as designing an inner product-preserving scheme with privacy preserving. Based on the asymmetric scalar-product-preserving encryption (ASPE) technique [15], we design a basic tool to compute a special inner product and then introduce a secure group nearest neighbor query (n≥3) scheme, which is referred to as the SecGNN scheme.(2)
Furthermore, we prove that finding group nearest neighbor for LBS users is equivalent to finding the nearest neighbor for their centroid, which can be secretly computed by using anonymous veto network protocol and Burmester–Desmedt conference key agreement protocol. Thus, the SecGNN+ scheme is designed from the construction of nearest neighbor for the centroid and further improves the search efficiency of the SecGNN scheme. The proposed SecGNN+ scheme achieves On1−1/k+m search complexity, where n is the number of data items in database, k is the dimension of data items, and m is the size of answers.(3)
Moreover, we demonstrate the correctness analysis and security proof of both schemes. The security proof illustrates that our SecGNN and SecGNN+ schemes achieve data privacy and query privacy.(4)
Finally, we evaluate the performance of SecGNN and SecGNN+ schemes through experimental simulation on a real-database with 62,556 data items and a random database with 1,000,000 data items. The experimental results show that the SecGNN+ scheme achieves practical search efficiency, about 0.2 s on millions’ database.


### 1.2. Related Work

Group nearest neighbor query enables a group of LBS users to retrieve a point with the minimum aggregate distance. The authors [16] demonstrated multiple query method (MQM), single-point method (SPM), and minimum bounding method (MBM) for processing GNN queries. Moving a step forward, Papadias et al. [17] generalized the GNN query to minimize the maximum or minimum distance. Because of heavy storage and computation burden, the resource-constrained LBS provider always outsources the database to the cloud server possessing the powerful storage and computation resources. Since the cloud server is dishonest and may steal sensitive information, privacy-preserving methods always be chosen to assure data security. As shown in Table 1, numerous studies [5, 6, 13, 18, 19] have been done to protect the privacy of private sensitive location information from the dishonest cloud server and outside attackers.Table 1
Comparison with existing works.
Group sizeSchemesTechniquesLeakage databaseResult redundancyn=1Bamba et al.’08 [10]Cloak regionYesYesWang et al.’16 [11]OPE + R-treeNoNoGuo et al.’20 [12]Bloom filterNoNo+prefix encodingn>1Hashem et al.’10 [5]k-anonymityYesYesHuang et al.’10 [13]MPCNoYesAshouri et al.’15 [14]Cloak regionYesYesWu et al.’21 [8]Dummy + PaillierYesNoOur solutionASPE + kd-treeNoNoHashem et al. [5] introduced the first privacy-preserving GNN scheme by leveraging k-anonymity technique. They described the privacy assurance solution from three steps, sending the query request, searching the GNN, and finding the actual meeting place. That is, users u1,u2,…,un first send cloaked rectangles R1,R2,…,Rn (including locations l1, l2, …, ln) to the cloud server, respectively. After receiving the query rectangles R1,R2,…,Rn, the cloud server proceeds the group nearest neighbor query for query rectangles over plaintexts and returns an answer set A=p1,p2,…,ps that contains the GNN for users u1,u2,…,un with respect to the actual locations l1,l2,…,ln. The cloud server also returns the sum of maximum distance to query rectangles (namely, dmaxp=∑i=1nMax DistRi,p) for each point p in the answer set A. Finally, LBS user uj updates uj by using the distance to his actual location lj instead of Max DistRj,p. Specifically, LBS user uj computes dmaxp=∑i=1nMax DistRi,p−Max DistRj,p+Distlj,p. This process continues until all LBS users u1,u2,…,un have updated. The point p is the desired GNN if it has the minimum dmax in the answer set. However, the scheme [5] is expensive in communication cost and fails to assure the query privacy.Subsequently, Ashouri-Talouki et al. [18] demonstrated an efficiency-enhanced group nearest neighbor query scheme. Users compute the minimum bounding rectangle (MBR) that contains all of them or the centroid from the anonymous veto network (AV-net) and Paillier encryption scheme [20]. Then, the cloud server searches the nearest neighbor (NN) over plaintexts for the MBR or centroid. Furthermore, it is worth that the authors take the NN for the centroid as an approximate GNN, and the scheme [18] fails to protect the location privacy of the meeting place. The authors design another privacy-preserving group nearest neighbor query scheme from cloaked-centroid protocols [6]. LBS users hide their precise locations in cloaked regions by generating rectangles that contain the exact locations, respectively. The cloaked region can be adjusted with the time and privacy requirements. LBS users publish their cloaked regions to the public bulletin board. After publishing, LBS users can compute the cloaked-centroid region and submit to the cloud server for a NN query. In the next phase, the cloud server searches the POIs and returns an answer set to them. LBS users compute the approximate meeting place by using AV-net protocol. But the cloud server returns a superset replacing the real answer, which increases the communication cost.Wu et al. [7, 8] presented a privacy-preserving GNN scheme based on the k-anonymity method. LBS users use k−1 dummy locations to blur their actual locations and store the exact location in a specific position which is shared among them. A chosen LBS user proceeds the generalized Paillier encryption to generate the ciphertext for the indicator vector. The cloud server searches the group nearest neighbor over plaintexts and computes the encrypted answer by a private selection. Finally, LBS users decrypt the ciphertext and obtain the real meeting place. Unfortunately, all these solutions only protect the query privacy with an advantage at most 1/k, where k is the size of dummy locations. Furthermore, it fails to protect the privacy of POIs since the cloud server searches the GNN or NN over plaintexts.Some privacy-preserving GNN schemes [13, 21] based on cryptographic have been introduced. Huang and Vishwanathan [13] proposed a secure GNN scheme from secure garble circuit and oblivious transfer. In solution [13], LBS user Charlie constructs a garble circuit for the GNN and user David executes the computation task. Other users obtain ciphertexts from Charlie through oblivious transfer and send ciphertexts to David. Finally, David obtains the GNN by computing the garble circuit. LBS users in [21] jointly compute the aggregate distance for all POIs by using anonymous veto network and Burmester–Desmedt key establishment protocols. Thus, users can obtain the precise meeting place. However, both schemes [13, 21] bring high computation and communication costs for LBS users and are impractical in the real world.


### 1.3. Organization

The rest of this work is organized as follows. Some preliminaries and their definitions will be demonstrated in Section2. In Section 3, we present the system model and privacy requirements of the proposed schemes. The introduced SecGNN scheme and its security analysis are illustrated in Section 4. We further describe the efficiency-enhanced SecGNN+ scheme and its security analysis in Section 5. Finally, the performance evaluation and conclusion will be discussed in Sections 6 and 7.


## 1.1. Our Contributions

In this paper, we design two privacy assurance group nearest neighbor query schemes, SecGNN scheme and SecGNN+ scheme, for the LBS system in cloud computing. The designed SecGNN scheme preserves the data privacy and query privacy, while achieving linear complexity. To enhance query efficiency, we introduce the SecGNN+ scheme based on the tree structure. The main contributions are demonstrated as follows.(1)
We convert the problem of finding group nearest neighbor to the problem of finding a point in POIs with minimum aggregate inner products. Thus, the construction of the secure GNN scheme is modeled as designing an inner product-preserving scheme with privacy preserving. Based on the asymmetric scalar-product-preserving encryption (ASPE) technique [15], we design a basic tool to compute a special inner product and then introduce a secure group nearest neighbor query (n≥3) scheme, which is referred to as the SecGNN scheme.(2)
Furthermore, we prove that finding group nearest neighbor for LBS users is equivalent to finding the nearest neighbor for their centroid, which can be secretly computed by using anonymous veto network protocol and Burmester–Desmedt conference key agreement protocol. Thus, the SecGNN+ scheme is designed from the construction of nearest neighbor for the centroid and further improves the search efficiency of the SecGNN scheme. The proposed SecGNN+ scheme achieves On1−1/k+m search complexity, where n is the number of data items in database, k is the dimension of data items, and m is the size of answers.(3)
Moreover, we demonstrate the correctness analysis and security proof of both schemes. The security proof illustrates that our SecGNN and SecGNN+ schemes achieve data privacy and query privacy.(4)
Finally, we evaluate the performance of SecGNN and SecGNN+ schemes through experimental simulation on a real-database with 62,556 data items and a random database with 1,000,000 data items. The experimental results show that the SecGNN+ scheme achieves practical search efficiency, about 0.2 s on millions’ database.


## 1.2. Related Work

Group nearest neighbor query enables a group of LBS users to retrieve a point with the minimum aggregate distance. The authors [16] demonstrated multiple query method (MQM), single-point method (SPM), and minimum bounding method (MBM) for processing GNN queries. Moving a step forward, Papadias et al. [17] generalized the GNN query to minimize the maximum or minimum distance. Because of heavy storage and computation burden, the resource-constrained LBS provider always outsources the database to the cloud server possessing the powerful storage and computation resources. Since the cloud server is dishonest and may steal sensitive information, privacy-preserving methods always be chosen to assure data security. As shown in Table 1, numerous studies [5, 6, 13, 18, 19] have been done to protect the privacy of private sensitive location information from the dishonest cloud server and outside attackers.Table 1
Comparison with existing works.
Group sizeSchemesTechniquesLeakage databaseResult redundancyn=1Bamba et al.’08 [10]Cloak regionYesYesWang et al.’16 [11]OPE + R-treeNoNoGuo et al.’20 [12]Bloom filterNoNo+prefix encodingn>1Hashem et al.’10 [5]k-anonymityYesYesHuang et al.’10 [13]MPCNoYesAshouri et al.’15 [14]Cloak regionYesYesWu et al.’21 [8]Dummy + PaillierYesNoOur solutionASPE + kd-treeNoNoHashem et al. [5] introduced the first privacy-preserving GNN scheme by leveraging k-anonymity technique. They described the privacy assurance solution from three steps, sending the query request, searching the GNN, and finding the actual meeting place. That is, users u1,u2,…,un first send cloaked rectangles R1,R2,…,Rn (including locations l1, l2, …, ln) to the cloud server, respectively. After receiving the query rectangles R1,R2,…,Rn, the cloud server proceeds the group nearest neighbor query for query rectangles over plaintexts and returns an answer set A=p1,p2,…,ps that contains the GNN for users u1,u2,…,un with respect to the actual locations l1,l2,…,ln. The cloud server also returns the sum of maximum distance to query rectangles (namely, dmaxp=∑i=1nMax DistRi,p) for each point p in the answer set A. Finally, LBS user uj updates uj by using the distance to his actual location lj instead of Max DistRj,p. Specifically, LBS user uj computes dmaxp=∑i=1nMax DistRi,p−Max DistRj,p+Distlj,p. This process continues until all LBS users u1,u2,…,un have updated. The point p is the desired GNN if it has the minimum dmax in the answer set. However, the scheme [5] is expensive in communication cost and fails to assure the query privacy.Subsequently, Ashouri-Talouki et al. [18] demonstrated an efficiency-enhanced group nearest neighbor query scheme. Users compute the minimum bounding rectangle (MBR) that contains all of them or the centroid from the anonymous veto network (AV-net) and Paillier encryption scheme [20]. Then, the cloud server searches the nearest neighbor (NN) over plaintexts for the MBR or centroid. Furthermore, it is worth that the authors take the NN for the centroid as an approximate GNN, and the scheme [18] fails to protect the location privacy of the meeting place. The authors design another privacy-preserving group nearest neighbor query scheme from cloaked-centroid protocols [6]. LBS users hide their precise locations in cloaked regions by generating rectangles that contain the exact locations, respectively. The cloaked region can be adjusted with the time and privacy requirements. LBS users publish their cloaked regions to the public bulletin board. After publishing, LBS users can compute the cloaked-centroid region and submit to the cloud server for a NN query. In the next phase, the cloud server searches the POIs and returns an answer set to them. LBS users compute the approximate meeting place by using AV-net protocol. But the cloud server returns a superset replacing the real answer, which increases the communication cost.Wu et al. [7, 8] presented a privacy-preserving GNN scheme based on the k-anonymity method. LBS users use k−1 dummy locations to blur their actual locations and store the exact location in a specific position which is shared among them. A chosen LBS user proceeds the generalized Paillier encryption to generate the ciphertext for the indicator vector. The cloud server searches the group nearest neighbor over plaintexts and computes the encrypted answer by a private selection. Finally, LBS users decrypt the ciphertext and obtain the real meeting place. Unfortunately, all these solutions only protect the query privacy with an advantage at most 1/k, where k is the size of dummy locations. Furthermore, it fails to protect the privacy of POIs since the cloud server searches the GNN or NN over plaintexts.Some privacy-preserving GNN schemes [13, 21] based on cryptographic have been introduced. Huang and Vishwanathan [13] proposed a secure GNN scheme from secure garble circuit and oblivious transfer. In solution [13], LBS user Charlie constructs a garble circuit for the GNN and user David executes the computation task. Other users obtain ciphertexts from Charlie through oblivious transfer and send ciphertexts to David. Finally, David obtains the GNN by computing the garble circuit. LBS users in [21] jointly compute the aggregate distance for all POIs by using anonymous veto network and Burmester–Desmedt key establishment protocols. Thus, users can obtain the precise meeting place. However, both schemes [13, 21] bring high computation and communication costs for LBS users and are impractical in the real world.


## 1.3. Organization

The rest of this work is organized as follows. Some preliminaries and their definitions will be demonstrated in Section2. In Section 3, we present the system model and privacy requirements of the proposed schemes. The introduced SecGNN scheme and its security analysis are illustrated in Section 4. We further describe the efficiency-enhanced SecGNN+ scheme and its security analysis in Section 5. Finally, the performance evaluation and conclusion will be discussed in Sections 6 and 7.


## 2. Preliminaries

In this section, we introduce some preliminaries of KD-tree, anonymous veto network protocol, and Burmester–Desmedt conference key agreement protocol.


### 2.1. KD-Tree

KD-tree is a hierarchical data structure which is always used to improve the efficiency of the range query and nearest neighbor query. It has aOn storage cost, Onlogn construction time cost, and On1−1/k+m query time cost, where n is the size of the database, k is the dimension of data record in the database, and m is the size of the answer set.KD-tree is a binary tree structure in which every nonleaf node has two children. The children are split based on thex−coordinate or y−coordinate of their father node. From root to leaf node, the splitting is done on x−coordinate, on y−coordinate for the children, and next on x−coordinate for the grandchildren, and so on. In the following, we describe the solution for KD-tree to solve the problem of the nearest neighbor query:(1)
The search process is done based on the splitting line (e.g.,x−coordinate or y−coordinate of the farther node) and can quickly arrive at the leaf node. We return the leaf node value as a temporary nearest neighbor and mark down the road from root to this leaf node.(2)
We check whether the distance of its father node to query node is closer than the temporary nearest neighbor. If it is, we update the father node as a temporary nearest neighbor. Furthermore, we do the checking whether the distance from the query point to the splitting line is smaller than that to the temporary nearest neighbor. If it holds, we search the other child. The checking algorithm continues until backing at the root.For instance, we illustrate an example of KD-tree in Figure1. Given a query point 2.1,3.1, the search process is done to obtain the leaf node value 3,5 as the temporary nearest neighbor. When backing to the father node 2,3, it is easily seen that the father node is closer than the temporary nearest neighbor 3,5. We update father node 2,3 as the temporary nearest neighbor. Furthermore, we check whether the circle with center 2.1,3.1 and radius 0.14 (the distance from query point to temporary nearest neighbor 2,3) intersects y=3 (the splitting line). Since it intersects with y=3, we check whether point 1,1 is closer than temporary nearest neighbor 2,3. If it fails, we are back to check the father node 4,7 and obtain 2,3 as the nearest neighbor for query point 2.1,3.1.Figure 1
An example of KD-tree for the nearest neighbor query.


### 2.2. Anonymous Veto Network Protocol

In anonymous veto network protocol and the following Burmester–Desmedt protocol, it is assumed thatG is a finite cyclic group of prime order q in which the decisional Diffie–Hellman (DDH) problem is intractable. The generator in G is g, and all computations take place in G. There are n members in the group as u1, u2, …, un, and they agree on G,g.Anonymous veto network protocol (AV-net) was introduced by Feng et al. [22, 23] to solve the problem of anonymous veto. The AV-net protocol contains two phases. In the first phase, users u1,u2,…,un choose random numbers a1,a2,…,an and publish the random ephemeral public keys ga1,ga2,…,gan, respectively. Then, each user ui computes gbi by multiplying all the random ephemeral public keys before i and dividing all the random ephemeral public keys after i:(1)gbi=∏j=1i−1gaj∏j=i+1ngaj.In the next phase, usersu1,u2,…,un compute and broadcast gb1c1, gb2c2, …, gbncn, where ci=ai if user ui does not veto; otherwise, ci is a random number (i=1,2,…,n). In such situation, if no one vetoes, we have Πi=1ngbici=Πi=1ngaibi=1 because of the vanishing property of AV-net exponents, ∑i=1naibi=0. Otherwise, ∏i=1ngbici≠1. Meanwhile, vetoing users remain anonymous.


### 2.3. Burmester–Desmedt Conference Key Agreement Protocol

Burmester–Desmedt (BD) protocol was developed by Burmester and Desmedt to establish a conference key [24, 25]. That is, users u1, u2, …, un aim to establish a conference key. The indices are taken in a cycle, namely, un+1=u1 and un+2=u2. As shown in Figure 2, BD-protocol includes two processes. In the first process, users u1, u1, …, un choose random numbers e1,e2,…,en and broadcast ge1,ge2,…,gen. In the second process, each user ui publishes ri=gei+1/gei−1ei and later computes the conference key by the following equation:(2)ki=gei−1nei⋅rin−1⋅ri+1n−2⋯ri−2modq,i=1,2,…,n.Figure 2
An instance of Burmester–Desmedt conference key agreement protocol.Thus, usersu1, u1, …, un have the same conference key:(3)k1=k2=⋯=kn=k=ge1e2+e2e3+⋯+en−1en+ene1modq.Considering the intractability of the Diffie–Hellman problem inG, the conference k is only computable by group users and adversaries can find no information about it.


## 2.1. KD-Tree

KD-tree is a hierarchical data structure which is always used to improve the efficiency of the range query and nearest neighbor query. It has aOn storage cost, Onlogn construction time cost, and On1−1/k+m query time cost, where n is the size of the database, k is the dimension of data record in the database, and m is the size of the answer set.KD-tree is a binary tree structure in which every nonleaf node has two children. The children are split based on thex−coordinate or y−coordinate of their father node. From root to leaf node, the splitting is done on x−coordinate, on y−coordinate for the children, and next on x−coordinate for the grandchildren, and so on. In the following, we describe the solution for KD-tree to solve the problem of the nearest neighbor query:(1)
The search process is done based on the splitting line (e.g.,x−coordinate or y−coordinate of the farther node) and can quickly arrive at the leaf node. We return the leaf node value as a temporary nearest neighbor and mark down the road from root to this leaf node.(2)
We check whether the distance of its father node to query node is closer than the temporary nearest neighbor. If it is, we update the father node as a temporary nearest neighbor. Furthermore, we do the checking whether the distance from the query point to the splitting line is smaller than that to the temporary nearest neighbor. If it holds, we search the other child. The checking algorithm continues until backing at the root.For instance, we illustrate an example of KD-tree in Figure1. Given a query point 2.1,3.1, the search process is done to obtain the leaf node value 3,5 as the temporary nearest neighbor. When backing to the father node 2,3, it is easily seen that the father node is closer than the temporary nearest neighbor 3,5. We update father node 2,3 as the temporary nearest neighbor. Furthermore, we check whether the circle with center 2.1,3.1 and radius 0.14 (the distance from query point to temporary nearest neighbor 2,3) intersects y=3 (the splitting line). Since it intersects with y=3, we check whether point 1,1 is closer than temporary nearest neighbor 2,3. If it fails, we are back to check the father node 4,7 and obtain 2,3 as the nearest neighbor for query point 2.1,3.1.Figure 1
An example of KD-tree for the nearest neighbor query.


## 2.2. Anonymous Veto Network Protocol

In anonymous veto network protocol and the following Burmester–Desmedt protocol, it is assumed thatG is a finite cyclic group of prime order q in which the decisional Diffie–Hellman (DDH) problem is intractable. The generator in G is g, and all computations take place in G. There are n members in the group as u1, u2, …, un, and they agree on G,g.Anonymous veto network protocol (AV-net) was introduced by Feng et al. [22, 23] to solve the problem of anonymous veto. The AV-net protocol contains two phases. In the first phase, users u1,u2,…,un choose random numbers a1,a2,…,an and publish the random ephemeral public keys ga1,ga2,…,gan, respectively. Then, each user ui computes gbi by multiplying all the random ephemeral public keys before i and dividing all the random ephemeral public keys after i:(1)gbi=∏j=1i−1gaj∏j=i+1ngaj.In the next phase, usersu1,u2,…,un compute and broadcast gb1c1, gb2c2, …, gbncn, where ci=ai if user ui does not veto; otherwise, ci is a random number (i=1,2,…,n). In such situation, if no one vetoes, we have Πi=1ngbici=Πi=1ngaibi=1 because of the vanishing property of AV-net exponents, ∑i=1naibi=0. Otherwise, ∏i=1ngbici≠1. Meanwhile, vetoing users remain anonymous.


## 2.3. Burmester–Desmedt Conference Key Agreement Protocol

Burmester–Desmedt (BD) protocol was developed by Burmester and Desmedt to establish a conference key [24, 25]. That is, users u1, u2, …, un aim to establish a conference key. The indices are taken in a cycle, namely, un+1=u1 and un+2=u2. As shown in Figure 2, BD-protocol includes two processes. In the first process, users u1, u1, …, un choose random numbers e1,e2,…,en and broadcast ge1,ge2,…,gen. In the second process, each user ui publishes ri=gei+1/gei−1ei and later computes the conference key by the following equation:(2)ki=gei−1nei⋅rin−1⋅ri+1n−2⋯ri−2modq,i=1,2,…,n.Figure 2
An instance of Burmester–Desmedt conference key agreement protocol.Thus, usersu1, u1, …, un have the same conference key:(3)k1=k2=⋯=kn=k=ge1e2+e2e3+⋯+en−1en+ene1modq.Considering the intractability of the Diffie–Hellman problem inG, the conference k is only computable by group users and adversaries can find no information about it.


## 3. Problem Formulation

In this section, we first illustrate the system model and then describe the privacy requirements of the group nearest neighbor query schemes.


### 3.1. System Model

In this paper, we aim to design a secure and efficient group nearest neighbor query scheme. As shown in Figure3, the system model of our scheme consists of three entities, cloud server, LBS provider, and LBS users. The cloud server has powerful storage and computation resources. It provides storage and computation services for LBS provider and further searches the encrypted database after receiving search tokens from LBS users. Since constrained resources and privacy concerns, the LBS provider (e.g., a company) owns the database and chooses the encryption-and-outsourcing mechanism to enjoy the powerful resources provided by the cloud server. According to their requirements, LBS users (e.g., employees) generate and submit search tokens to the cloud server. Subsequently, they obtain the encrypted results and decrypt them to have the final results. In this paper, we suppose that LBS users always submit a query request for a meeting place. That is, LBS users want to find a meeting place that has the minimum aggregate distance.Figure 3
The system model of the group nearest neighbor query scheme.Furthermore, we assume that the cloud server is honest-but-curious. That means, the cloud server follows the protocol faithfully but intends to steal the information about the private sensitive database. We also assume that the LBS provider is honest and LBS users want to steal other actual locations but do not collude with others. The assumption is common in other papers [26, 27].Based on the assumption, we consider two threat models, known ciphertext model and known background model. In the known ciphertext model, only ciphertexts and encrypted index are known to the cloud server. In the known background model, the cloud server holds more information, such as the distribution of data records and queries. Both models are considered in some existing works [28, 29].


### 3.2. Privacy Requirements

Under above assumptions, the proposed scheme should protect the confidentiality of outsourced database and query data. The privacy requirements are illustrated in the following.(1)
Data privacy: the LBS provider owns the original database and builds an index to improve the search efficiency. Both data and index contains private sensitive information. Thus, a secure group nearest neighbor query scheme should ensure that outside attackers (i.e., cloud server) cannot infer the exact information from the encrypted database and index.(2)
Query privacy: the authorized LBS users submit GNN queries to the cloud server, and the latter executes search operations. However, the cloud server cannot infer specific contents of query requests from the search token and encrypted results.


### 3.3. Notations

For the convenience of describing SecGNN and SecGNN+ schemes, we illustrate some notations in Table 2.Table 2
Key notations.
NotationsDescriptionSad-bit stringnThe number of users in the groupDBThe set of point-of-interestsDB∗The encryptedDBmThe size of databaseDBp=s,tThe coordinate of a pointp in DBl=x,yThe coordinate of an LBS userxi,yii=1nThe set of coordinates for LBS usersM1,M2Invertible matricesw1,w2,…,wdRandom numbers


## 3.1. System Model

In this paper, we aim to design a secure and efficient group nearest neighbor query scheme. As shown in Figure3, the system model of our scheme consists of three entities, cloud server, LBS provider, and LBS users. The cloud server has powerful storage and computation resources. It provides storage and computation services for LBS provider and further searches the encrypted database after receiving search tokens from LBS users. Since constrained resources and privacy concerns, the LBS provider (e.g., a company) owns the database and chooses the encryption-and-outsourcing mechanism to enjoy the powerful resources provided by the cloud server. According to their requirements, LBS users (e.g., employees) generate and submit search tokens to the cloud server. Subsequently, they obtain the encrypted results and decrypt them to have the final results. In this paper, we suppose that LBS users always submit a query request for a meeting place. That is, LBS users want to find a meeting place that has the minimum aggregate distance.Figure 3
The system model of the group nearest neighbor query scheme.Furthermore, we assume that the cloud server is honest-but-curious. That means, the cloud server follows the protocol faithfully but intends to steal the information about the private sensitive database. We also assume that the LBS provider is honest and LBS users want to steal other actual locations but do not collude with others. The assumption is common in other papers [26, 27].Based on the assumption, we consider two threat models, known ciphertext model and known background model. In the known ciphertext model, only ciphertexts and encrypted index are known to the cloud server. In the known background model, the cloud server holds more information, such as the distribution of data records and queries. Both models are considered in some existing works [28, 29].


## 3.2. Privacy Requirements

Under above assumptions, the proposed scheme should protect the confidentiality of outsourced database and query data. The privacy requirements are illustrated in the following.(1)
Data privacy: the LBS provider owns the original database and builds an index to improve the search efficiency. Both data and index contains private sensitive information. Thus, a secure group nearest neighbor query scheme should ensure that outside attackers (i.e., cloud server) cannot infer the exact information from the encrypted database and index.(2)
Query privacy: the authorized LBS users submit GNN queries to the cloud server, and the latter executes search operations. However, the cloud server cannot infer specific contents of query requests from the search token and encrypted results.


## 3.3. Notations

For the convenience of describing SecGNN and SecGNN+ schemes, we illustrate some notations in Table 2.Table 2
Key notations.
NotationsDescriptionSad-bit stringnThe number of users in the groupDBThe set of point-of-interestsDB∗The encryptedDBmThe size of databaseDBp=s,tThe coordinate of a pointp in DBl=x,yThe coordinate of an LBS userxi,yii=1nThe set of coordinates for LBS usersM1,M2Invertible matricesw1,w2,…,wdRandom numbers


## 4. Secure Group Nearest Neighbor Query

In this section, we illustrate a secure group nearest neighbor query scheme called SecGNN in the LBS system. SecGNN enables LBS users to retrieve a meeting place from POIs that have the minimum aggregate distance. For a pointp=s,t in POIs, the sum of distances to LBS users is computed as follows:(4)d2p=x1−s2+y1−t2+x2−s2+y2−t2+⋯+xn−s2+yn−t2,=x12−2sx1+s2+y12−2ty1+t2+x22−2sx2+s2+y22−2ty2+t2+⋯+xn2−2sxn+s2+yn2−2tyn+t2,=x12+y12+x22+y22+⋯+xn2+yn2+s2+t2,−2s,−2t,1,x1,y1+s2+t2,−2s,−2t,1,x2,y2+⋯+s2+t2,−2s,−2t,1,xn,yn,where x1,y1, x2,y2, …, xn,yn are the coordinates of LBS users u1,u2,…,un. Assume that p¯=s2+t2,−2s,−2t, tk¯1=1, x1, y1, tk¯2=1, x2, y2, …, and tk¯n=1, xn, yn. Since x12+y12+x22+y22+⋯+xn2+yn2 is a fixed number, dp achieves the minimum value if the sum of inner products p¯,tk¯1, p¯,tk¯2, …, and p¯,tk¯n achieves the minimum value.In the following, we adapt a privacy-preserving method to evaluate a pointp that has the minimum aggregate inner products. Specifically, we design a basic tool, named CompInner, supporting the computation of inner products over ciphertexts and then introduce the BD-conference key agreement to generate a common random. Finally, we construct the SecGNN scheme from above protocols.CompInner tool consists of five polynomial-time algorithms, Setup, Encrypt, GenToken, GenInner, and Decrypt. Firstly, the user runs the system setup algorithm (Setup) to generate the secret key and then encrypts data items in the encryption algorithm (Encrypt). Next, the token generation algorithm (GenToken) is run by the user to output a computation token for the query point, and inner products can be computed in the inner generation algorithm (GenInner). Finally, the user runs the decryption algorithm (Decrypt) to decrypt the encrypted results.(1)
Setup (λ): the user runs the system setup algorithm to generate two d′×d′ invertible matrices M1andM2, a d′-bit string S, and random values w1,w2,…,wdd=d′−3. Thus, the secret key is(5)sk=M1,M2,S,w1,w2,…,wd.(2)
Encrypt (sk,p): suppose that p=s,t, and the data encryption algorithm is run to do the following steps:(1)
Adding random numbers: for a pointp=s,t, the user first computes p¯=s2+t2,−2s,−2t and then extends it as p^=s2+t2,−2s,−2t,w1,w2,…,wd.(2)
Random splitting: splitp^ into two parts p^a and p^b. For i=1,2,…,d′,IfSi=0, p^ai=p^bi=p^i.IfSi=1, p^ai and p^bi are random numbers such that p^ai+p^bi=p^i.(3)
Data encryption: Compute the ciphertexts aspa′=M1T×p^aT,pb′=M1T×p^bT.(3)
GenToken(sk,l): suppose that l=x,y, and the token is generated as follows:(1)
Adding random numbers: for a query pointl=x,y, the user first computes l¯=r,rx,ry and then extends it as l^=r,rx,ry,r1,r2,…,rd, where r>0 and r1, r2, …, rd are random numbers satisfying rd=−∑i=1d−1riwi/wd.(2)
Random splitting: splitl^ into two parts l^a and l^b. For i=1,2,…,d′,IfSi=0, l^ai and l^bi are random numbers such that l^ai+l^bi=l^i.IfSi=1, l^ai=l^bi=l^i.(3)
Data encryption: compute the ciphertexts asla′=M1−1×l^aT, la′=M1−1×l^aT.(4)
GenInner(pa′,pb′,la′,lb′): the inner generation algorithm computes and outputs ind=pa′,la′+pb′,lb′.(5)
Decrypt (sk,pa′,pb′): this decryption algorithm first computes p^a=M1T−1×pa′ and p^b=M1T−1×pb′. For i=1,2,…,n,IfSi=0, p^ai=p^bi=p^i.IfSi=1, p^i=p^ai+p^bi.Finally, the user obtainss=−p^2/2 and t=−p^3/2.Correctness: the correctness of CompInner tool is illustrated as follows. We have(6)pa′T×la′+pb′T×lb′,=p^a×M1×M1−1×l^aT+p^b×M2×M2−1×l^bT=p^a,l^a+p^b,l^b=p^,l^=rs2+t2−2sx−2ty=rs2+t2,−2s,−2t,1,x,y.


### 4.1. The Main Scheme

The secure GNN scheme, named SecGNN, consists of six polynomial-time algorithms, Setup, EncDB, CompCen, GenToken, Query, and Decrypt. The details of these algorithms are described as follows.(1)
Setup (λ): on inputting a security parameter λ, it outputs a cyclic group G with order q and generator g. Furthermore, the LBS provider runs CompInner.Setup(λ) to output the secret key:(7)sk=M1,M2,S,w1,w2,…,wd.(2)
EncDB (sk, p): suppose p=s,t is a point in POIs’ database DB. The algorithm EncDB is run by the LBS provider to encrypt the point as(8)c=pa′,pb′=CompInnerEncryptsk,p.(3)
ShareRan (G,g): LBS users proceed this algorithm to compute a random value that keeps secreted from outside attackers. In the first phase, LBS users u1,u2,…,un choose random numbers e1,e2,…,en∈Zq and publish ge1,ge2,…,gen to other LBS users. In the second phase, users u1,u2,…,un compute and broadcast r1=ge2/gene1, r2=ge3/ge1e2, …, ri=gej+1/gej−1ej, …, and rn=ge1/gen−1en. Finally, LBS users compute and obtain(9)k1=genne1⋅r1n−1⋅r2n−2⋅⋯⋅rn−1modq,k2=ge1ne2⋅r2n−1⋅r3n−2⋅⋯⋅rnmodq,⋯ki=gei−1nei⋅rin−1⋅ri+1n−2⋅⋯⋅ri−2modq,⋯kn=gen−1nen⋅rnn−1⋅r1n−2⋅rn−2modq.It is easy to see that the valuesk1,k2,…,kn satisfy k1=k2=⋯=kn=ge1e2+e2e3+⋯+ene1=k. The value k is shared by all group users.(4)
GenToken (sk,k,x1,y1,…,xn,yn: after obtaining the secret value k, LBS users u1, u2, …, un compute tk1=la1,lb1=CompInner.GenTokensk,x1,y1, tk1=la2,lb2=CompInner.GenTokensk,x2,y2, ⋯, tk1=lan,lbn=CompInner.GenTokensk,xn,yn, respectively. Note that the random number r in above algorithms is chosen as the shared value k.(5)
Query (DB∗,tk1,tk2,…,tkn): let p1∗=p1a′,p1b′ and p1∗=p2a′,p2b′ are two encrypted points in DB∗. To determine whether the sum of inner products for query token to p1∗ is smaller than that to p2∗, the cloud server first computes tka=la1+la2+⋯+lan and tkb=lb1+lb2+⋯+lbn and then checks whether(10)p1a′T×tka+p1b′T×tkb−p2a′T×tka+p2b′T×tkb<0.If it holds, the aggregate inner products withp1∗ is smaller than those with p2∗. Otherwise, the inner products with p2∗ is smaller. The cloud server can linearly search all points in encrypted database and obtains point p∗ with the minimum aggregate inner products.(6)
Decrypt (sk,p∗): in the query phase, the cloud server finds with the minimum aggregate inner products. The LBS users run(11)p=s,t=CompInner.Decryptsk,pa,pb.Finally, LBS users obtain the GNN location, namely, the meeting place.Correctness: assume thatp1∗ and p2∗ are two encrypted POIs in DB∗. Note that(12)p1∗−p2∗⋅tk1+tk2+⋯+tkn=MTp¯1−MTp¯2⋅kM−1tk¯1+kM−1tk¯2+⋯+kM−1tk¯n,=MTp¯1−MTp¯2TkM−1tk¯1+kM−1tk¯2+⋯+kM−1tk¯n,=kp¯1−p¯2Ttk¯1+tk¯2+⋯+tk¯n,=kp¯1,tk¯1+p¯1,tk¯2+⋯+p¯1,tk¯n.−p¯2,tk¯1+p¯2,tk¯2+⋯+p¯2,tk¯n.Thus, ifp1∗−p2∗⋅tk1+tk2+⋯+tkn<0, then the aggregate inner products for p¯1 is smaller than those for p¯2. That is, the aggregate distances for p1 are smaller than those for p2. In such a case, the cloud server can find the group nearest neighbor (GNN) through linearly searching the encrypted database.


### 4.2. Security Analysis

In this section, we first illustrate the security analysis of our CompInner tool and our SecGNN scheme. The security proofs are described in the following.Theorem 1.
The proposed CompInner tool preserves data privacy and query privacy under the background model. Specifically, outside attackers could not learn the data items from the encrypted database and could not obtain the query point from the query token.Proof 1.
Without the loss of generality, we will prove the theorem from data privacy and query privacy two parts. The proof for data privacy will be introduced in the following.
Suppose that outside attackers have the knowledgeH=DB∗,Q∗ and its trace TrH, where DB∗ is the encrypted database and Q∗ is the encrypted queries submitted by group users, and the trace contains access pattern αH, search pattern σH, path pattern δH, and identifiers IDQ. Based on an encrypted data tuple c=pa′=M1T×p^aT,pb′=M2T×p^bT, an adversary should recover two invertible matrices M1 and M2 from pa′andpb′ and further guess the bit string that are involved in the key if she wants to recover the original data from the ciphertexts. In such scenarios, an outside attacker A has to model p^a and p^b as two d′-dimensional random vectors. The equations for solving the unknowns are(13)pa′=M1T×p^aT,pa′=M1T×p^bT.
As we known, stringS is a bits string with length d′; thus, the number of possible ways to split p^ is 2d′, which is large enough to prevent an adversary from correctly guessing s. On the contrary, the advantage of an adversary correctly guesses s is negligible, and there are 2d′ unknowns in pa′ and pb′ and 2d2 unknowns in invertible matrices M1 and M2. Since the number of equations 2d′ are less than the number of unknowns 2d′+2d2, an outside attacker A could not solve the equations for the unknowns.
For the query privacy, we padd+1 random numbers for the query point in the encrypt algorithm, which leads to the fact that a same point generates different p^. Furthermore, we split n−dimensional p^ into two random vectors q^a and q^b, whose technique is same as in the encryption phase. Thus, query privacy is semantically secure.
In this case, we prove that our CompInner tool achieves data privacy and query privacy.Theorem 2.
The proposed SecGNN scheme preserves the data privacy and query privacy from outside attackers.Proof 2.
In the SecGNN scheme, an outside attacker obtains the plaintext from the encrypted database. The encryption algorithm in SecGNN is the same with that in CompInner tool. Therefore, the data privacy can be assured in Theorem1.
In the following, we proof the query privacy in two parts. First, we prove an outside attacker fails to learn the shared number keyk (note that the leaks of random number k could not help an outside attacker to obtain actual locations. The shared number k only helps the LBS users to hide the query frequency). Learning k requires an outside attacker can disclose the AV-net mask. Specifically, an outside attacker computes geiej from gei and gej in AV-net protocol. Under the assumption of decisional Diffie–Hellman (DDH) problem, an outside attacker fails to learn knowledge of shared key k.
Furthermore, query tokens are produced in the CompInner.GenToken algorithm. Since CompInner achieves query privacy in Theorem1, it is easy to see that actual locations can be protected from outside attackers.
Note that LBS users can obtain actual locations of other users in the SecGNN scheme. We will further improve the query privacy in the enhanced scheme SecGNN+, namely, the actual location of a LBS user could not obtained by other LBS users until the rest of LBS users colluded.


## 4.1. The Main Scheme

The secure GNN scheme, named SecGNN, consists of six polynomial-time algorithms, Setup, EncDB, CompCen, GenToken, Query, and Decrypt. The details of these algorithms are described as follows.(1)
Setup (λ): on inputting a security parameter λ, it outputs a cyclic group G with order q and generator g. Furthermore, the LBS provider runs CompInner.Setup(λ) to output the secret key:(7)sk=M1,M2,S,w1,w2,…,wd.(2)
EncDB (sk, p): suppose p=s,t is a point in POIs’ database DB. The algorithm EncDB is run by the LBS provider to encrypt the point as(8)c=pa′,pb′=CompInnerEncryptsk,p.(3)
ShareRan (G,g): LBS users proceed this algorithm to compute a random value that keeps secreted from outside attackers. In the first phase, LBS users u1,u2,…,un choose random numbers e1,e2,…,en∈Zq and publish ge1,ge2,…,gen to other LBS users. In the second phase, users u1,u2,…,un compute and broadcast r1=ge2/gene1, r2=ge3/ge1e2, …, ri=gej+1/gej−1ej, …, and rn=ge1/gen−1en. Finally, LBS users compute and obtain(9)k1=genne1⋅r1n−1⋅r2n−2⋅⋯⋅rn−1modq,k2=ge1ne2⋅r2n−1⋅r3n−2⋅⋯⋅rnmodq,⋯ki=gei−1nei⋅rin−1⋅ri+1n−2⋅⋯⋅ri−2modq,⋯kn=gen−1nen⋅rnn−1⋅r1n−2⋅rn−2modq.It is easy to see that the valuesk1,k2,…,kn satisfy k1=k2=⋯=kn=ge1e2+e2e3+⋯+ene1=k. The value k is shared by all group users.(4)
GenToken (sk,k,x1,y1,…,xn,yn: after obtaining the secret value k, LBS users u1, u2, …, un compute tk1=la1,lb1=CompInner.GenTokensk,x1,y1, tk1=la2,lb2=CompInner.GenTokensk,x2,y2, ⋯, tk1=lan,lbn=CompInner.GenTokensk,xn,yn, respectively. Note that the random number r in above algorithms is chosen as the shared value k.(5)
Query (DB∗,tk1,tk2,…,tkn): let p1∗=p1a′,p1b′ and p1∗=p2a′,p2b′ are two encrypted points in DB∗. To determine whether the sum of inner products for query token to p1∗ is smaller than that to p2∗, the cloud server first computes tka=la1+la2+⋯+lan and tkb=lb1+lb2+⋯+lbn and then checks whether(10)p1a′T×tka+p1b′T×tkb−p2a′T×tka+p2b′T×tkb<0.If it holds, the aggregate inner products withp1∗ is smaller than those with p2∗. Otherwise, the inner products with p2∗ is smaller. The cloud server can linearly search all points in encrypted database and obtains point p∗ with the minimum aggregate inner products.(6)
Decrypt (sk,p∗): in the query phase, the cloud server finds with the minimum aggregate inner products. The LBS users run(11)p=s,t=CompInner.Decryptsk,pa,pb.Finally, LBS users obtain the GNN location, namely, the meeting place.Correctness: assume thatp1∗ and p2∗ are two encrypted POIs in DB∗. Note that(12)p1∗−p2∗⋅tk1+tk2+⋯+tkn=MTp¯1−MTp¯2⋅kM−1tk¯1+kM−1tk¯2+⋯+kM−1tk¯n,=MTp¯1−MTp¯2TkM−1tk¯1+kM−1tk¯2+⋯+kM−1tk¯n,=kp¯1−p¯2Ttk¯1+tk¯2+⋯+tk¯n,=kp¯1,tk¯1+p¯1,tk¯2+⋯+p¯1,tk¯n.−p¯2,tk¯1+p¯2,tk¯2+⋯+p¯2,tk¯n.Thus, ifp1∗−p2∗⋅tk1+tk2+⋯+tkn<0, then the aggregate inner products for p¯1 is smaller than those for p¯2. That is, the aggregate distances for p1 are smaller than those for p2. In such a case, the cloud server can find the group nearest neighbor (GNN) through linearly searching the encrypted database.


## 4.2. Security Analysis

In this section, we first illustrate the security analysis of our CompInner tool and our SecGNN scheme. The security proofs are described in the following.Theorem 1.
The proposed CompInner tool preserves data privacy and query privacy under the background model. Specifically, outside attackers could not learn the data items from the encrypted database and could not obtain the query point from the query token.Proof 1.
Without the loss of generality, we will prove the theorem from data privacy and query privacy two parts. The proof for data privacy will be introduced in the following.
Suppose that outside attackers have the knowledgeH=DB∗,Q∗ and its trace TrH, where DB∗ is the encrypted database and Q∗ is the encrypted queries submitted by group users, and the trace contains access pattern αH, search pattern σH, path pattern δH, and identifiers IDQ. Based on an encrypted data tuple c=pa′=M1T×p^aT,pb′=M2T×p^bT, an adversary should recover two invertible matrices M1 and M2 from pa′andpb′ and further guess the bit string that are involved in the key if she wants to recover the original data from the ciphertexts. In such scenarios, an outside attacker A has to model p^a and p^b as two d′-dimensional random vectors. The equations for solving the unknowns are(13)pa′=M1T×p^aT,pa′=M1T×p^bT.
As we known, stringS is a bits string with length d′; thus, the number of possible ways to split p^ is 2d′, which is large enough to prevent an adversary from correctly guessing s. On the contrary, the advantage of an adversary correctly guesses s is negligible, and there are 2d′ unknowns in pa′ and pb′ and 2d2 unknowns in invertible matrices M1 and M2. Since the number of equations 2d′ are less than the number of unknowns 2d′+2d2, an outside attacker A could not solve the equations for the unknowns.
For the query privacy, we padd+1 random numbers for the query point in the encrypt algorithm, which leads to the fact that a same point generates different p^. Furthermore, we split n−dimensional p^ into two random vectors q^a and q^b, whose technique is same as in the encryption phase. Thus, query privacy is semantically secure.
In this case, we prove that our CompInner tool achieves data privacy and query privacy.Theorem 2.
The proposed SecGNN scheme preserves the data privacy and query privacy from outside attackers.Proof 2.
In the SecGNN scheme, an outside attacker obtains the plaintext from the encrypted database. The encryption algorithm in SecGNN is the same with that in CompInner tool. Therefore, the data privacy can be assured in Theorem1.
In the following, we proof the query privacy in two parts. First, we prove an outside attacker fails to learn the shared number keyk (note that the leaks of random number k could not help an outside attacker to obtain actual locations. The shared number k only helps the LBS users to hide the query frequency). Learning k requires an outside attacker can disclose the AV-net mask. Specifically, an outside attacker computes geiej from gei and gej in AV-net protocol. Under the assumption of decisional Diffie–Hellman (DDH) problem, an outside attacker fails to learn knowledge of shared key k.
Furthermore, query tokens are produced in the CompInner.GenToken algorithm. Since CompInner achieves query privacy in Theorem1, it is easy to see that actual locations can be protected from outside attackers.
Note that LBS users can obtain actual locations of other users in the SecGNN scheme. We will further improve the query privacy in the enhanced scheme SecGNN+, namely, the actual location of a LBS user could not obtained by other LBS users until the rest of LBS users colluded.


## 5. Efficiency-Enhanced Group Nearest Neighbor Query

In this section, we aim to construct an efficiency-enhanced group nearest neighbor query scheme (called SecGNN+) that protects actual locations privacy from other LBS users and achieves faster than linear search complexity. The SecGNN+ scheme is designed by the leveraging tree structure, such as KD-tree, R-tree, and quad-tree. In this work, we take KD-tree to describe the details of the proposed SecGNN+ scheme.Assume thatxc,yc is the centroid of LBS users u1,u2,…,un and s,t is the coordinate of a point p in POIs. Therefore, the distance from the centroid to point p is(14)dp2=xc−s2+yc−t2,=xc2+yc2−2sxc−2tyc+s2+t2=xc2+yc2+s2+t2,−2s,−2t,1,xc,yc.Sincexc2+yc2 is a fixed number, the NN for centroid xc,yc is to find a point p that has the minimum inner product s2+t2,−2s,−2t,1,xc,yc. Considering GNN in Section 4, it requires to find a point p with the minimum aggregate inner products:(15)s2+t2,−2s,−2t,1,x1,y1+s2+t2,−2s,−2t,1,x2,y2+⋯+s2+t2,−2s,−2t,1,xn,yn,=ns2+t2,−2s,−2t,1,x1+x2+⋯+xn/n,y1+y2+⋯+yn/n,=ns2+t2,−2s,−2t,1,xc,yc,where xc=x1+x2+⋯+xn/n and xc=y1+y2+⋯+yn/n.Therefore, the GNN problem requires to find a pointp in POIs with the minimum inner product s2+t2,−2s,−2t,1,xc,yc. That is, the GNN problem can be converted as the NN problem for their centroid:In the following, we describe the problem on how to use KD-tree to enhance the efficiency and support privacy preserving. The KD-tree for solving the NN problem requires comparison and computation operations, namely, the order comparison between query points and tree nodes should be proceeded, and distances from query points to tree nodes and splitting lines should also be computed.From the root to leaf nodes, the search algorithm is done to check whetherx>s or y>t, where x,y is the coordinate of the query point q and s,t is the coordinate of the current tree node. The checking is done in each dimension. A function f on x−coordinate is proposed as(16)f=s−xs+δ,=s2+δ−xs−xδ=s2,s,1,1,δ−x,−xδ,where δ is much bigger than s, and thus, s+δ is a positive number.The square of distance from the query point to tree node is defined as(17)d2=x−s2+y−t2,=x2−2sx+s2+y2−2ty+t2=s2,s,1,1,−2x,x2+t2,t,1,1,−2y,y2.The distance from query point to splitting line (e.g.,x−coordinate) is defined as(18)d12=x−s2,=x2−2sx+s2=s2,s,1,1,−2x,x2.Thus, the order comparison and distance computation are converted to the inner products computation. As described in CompInner tool in the SecGNN scheme, we first introduce a tool called CompInner+ to compute the above inner products. The basic idea of CompInner+ is similar to CompInner. The differences occur at data encryption and token generation.


### 5.1. Basic Tool

The proposed CompInner+ contains five polynomial-time algorithms, Setup, Encrypt, GenToken, GenInner, and Decrypt. The details are described as follows.(1)
Setup (λ): it is the same with the system setup algorithm in CompInner. Thus, the secret key is sk=M1,M2,S,w1,w2,…,wd.(2)
Encrypt (sk,p): suppose that p=s,t is a data record, and this algorithm does the following steps.(1)
Adding random numbers: for a datap=s,t, the user computes s¯=s2,s,1,t¯=t2,t,1 and then extends them as s^=s2,s,1,w1,w2,…,wd and t^=t2,t,1,w1,w2,…,wd.(2)
Random splitting: splits^,t^ into two parts, s^a,s^b and t^a,t^b. For i=1,2,…,d′,IfSi=0, s^ai=s^bi=s^i and t^ai=t^bi=t^i.IfSi=1, s^ai, s^bi and t^ai, t^bi are random numbers such that s^ai+s^bi=s^i and t^ai+t^bi=t^i.(3)
Data encryption: compute the ciphertexts as(19)c1=sa′=M1T×s^aT,sb′=M2T×s^bT,c2=a′t=M1T×t^aT,tb′=M2T×t^bT.Thus, the ciphertext for data pointp is c=c1,c2.(3)
GenToken (sk,l): suppose that l=x,y, the token is generated as follows.(1)
Adding random numbers: for a datal=x,y, the user extends it as(20)x^1=1,δ1−x,−δ1x,rx11,rx12,…,rx1d,x^2=1,−2x,x2,rx21,rx22,…,rx2d,y^1=1,δ2−y,−δ2y,ry11,ry12,…,ry1d,y^2=1,−2y,y2,ry21,ry22,…,ry2d,whereδ1,δ2, rx11,…,rx1d, rx21,…,rx2d, ry11, …, ry1d, and ry21, …,ry2d are random numbers such that(21)rx1d=−∑i=1d−1rx1iwiwd,rx2d=−∑i=1d−1rx2iwiwd,ry1d=−∑i=1d−1ry1iwiwd,ry2d=−∑i=1d−1ry1iwiwd.(2)
Random splitting: splitx^1,x^2,y^1,andy^2 into two parts x^1a,x^1b, x^2a,x^2b, y^1a,y^1b, and y^2a,y^2b. For i=1,2,…,d′,IfSi=0, x^1ai, x^1bi, x^2ai, x^2bi, y^1ai, y^1bi, and y^2ai, y^2bi are random numbers such that(22)x^1ai+x^1bi=x^1i,x^2ai+x^2bi=x^2i,y^1ai+y^1bi=y^1i,y^2ai+y^2bi=y^2i.IfSi=1,(23)x^1ai=x^1bi=x^1i,x^2ai=x^2bi=x^2i,y^1ai=y^1bi=y^1i,y^2ai=y^2bi=y^2i.(3)
Data encryption: compute the ciphertexts as(24)tk11a=M1−1×x^1a,tk11b=M1−1×x^1b,tk12a=M1−1×x^2a,tk12b=M1−1×x^2b,tk21a=M1−1×y^1a,tk21b=M1−1×y^1b,tk22a=M1−1×y^2a,tk22b=M1−1×y^2b.Thus, the token generation algorithm outputs token astk=tk11,tk12,tk21,tk22, where tk11=tk11a,tk11b, tk12=tk12a,tk12b, tk21=tk21a,tk21b, and tk22=tk22a,tk22b.(4)
GenInner(pa′,pb′,la′,lb′: the inner generation algorithm computes and outputs(25)ind=pb′,lb′+la′,lb′(5)
Decrypt(sk,c=c1,c2): suppose that c1=sa′,sb′ and c2=ta′,tb′. The decryption algorithm first computes(26)s^a=M1T−1×sa′,s^b=M1T−1×sb′,t^a=M1T−1×ta′,t^b=M1T−1×tb′.Fori=1,2,…,d′,IfSi=0, s^i=s^ai=s^ai and t^i=t^ai=t^biIfSi=1, s^i=s^ai+s^bi and t^i=t^ai+t^biFinally, the user obtainss=s^2 and t=t^2.


### 5.2. The Detailed Description

From above, we convert the problem of finding GNN for a group of users to the problem of finding NN for their centroid. In the following, we illustrate an efficiency-enhanced group nearest neighbor query scheme calledSecGNN+ based on KD-tree and CompInner+ tool. The introduced SecGNN+ scheme consists of seven polynomial-time algorithms, Setup, BuildTree, EncDB, CompCen, GenToken, Query, and Decrypt. The detailed description is illustrated as follows:(1)
Setup (1λ): on inputting a security parameter λ, it outputs a cyclic group G with order q and generator g. Furthermore, this algorithm runs CompInner+ tool and outputs a secret key:(27)sk=M1,M2,S,w1,w2,…,wd.(2)
BuildTree (DB): on inputting the database DB of POIs, this algorithm proceeds the KD-tree algorithm and stores the data items in a KD-tree T.(3)
EncDB (sk,p): suppose that p=s,t is a data record stored in KD-tree T. The LBS provider runs CompInner+.Encrypt(sk,p) to compute the ciphertext as(28)c=c1,c2=sa′,sb′,ta′,ta′.(4)
CompCen (l1,l2,…,ln): suppose that l1=x1,y1, l1=x2,y2, ⋯, ln=xn,yn are coordinates of LBS users u1, u2, …, un. LBS users evaluate the centroid as follows.(1)
Each LBS userui chooses two random numbers aiandei∈Zq and publishes gai,gei to other LBS users. Then, ui computes and further broadcasts ri=gei+1/gei−1ei.(2)
The userui computes(29)gbi=Πj=1i−1gajΠj=i+1ngaj,ki=gei−1nei⋅rin−1⋅ri+1n−2⋅⋯⋅ri−2modq.(3)
Userui computes and publishes Xi=gaibigei−1eigxi. Multiplying all Xi,(30)Πi=1nXi=Πi=1ngaibigei−1eigxi,=Πi=1ngaibiΠi=1ngei−1eiΠi=1ngxi=kig∑i=1nxi=kg∑i=1nxi.Userui can get the value g∑i=1nxi through dividing by the secret key k. Since ∑i=1nxi is a small number, LBS users can compute the discrete logarithm by using the Pohlig–Hellman algorithm [30]. Considering the coordinates are six- or seven-decimal digits, they can be represented as a 32 bit data. Therefore, ∑i=1nxi is a small number and can be efficiently computed from g∑i=1nxi.(4)
Finally, userui can compute the centroid as xc=∑i=1nxi/n and yc=∑i=1nyi/n.(5)
GenToken (sk,xc,yc): after receiving the centroid xc,yc, LBS user runs CompInner+.GenToken(sk,p) to compute the token as tk=tk11,tk12,tk21,tk22, where tk11=tk11a,tk11b, tk12=tk12a,tk12b, tk21=tk21a,tk21b, and tk22=tk22a,tk22b.(6)
Query (T∗,tk): the query algorithm consists of two phases. In the first phase, the cloud server searches over the encrypted KD-tree T∗ to find a leaf node whose corresponding region includes the query point. The cloud server computes ind = CompInner+.GenInner(c1,tk11) (or ind = CompInner+.GenInner(c2,tk21)) and checks whether ind>0. If it holds, the cloud server searches the left child; otherwise, it searches the right child. The cloud server writes down the route from root to the leaf node in a list L.After arriving at the leaf node, the cloud server takes this leaf node as the temporary NN and proceeds the second phase to check whether the temporary NN is the NN. In the second phase, the cloud server checks the listL from leaf nodes back to the root. For each node, he computes(31)ind1=CompInner+.GenInnerc1,tk12,indtemp1=CompInner+.GenInnerctemp1,tk12,ind2=CompInner+.GenInnerc2,tk22,indtemp2=CompInner+.GenInnerctemp2,tk22,and checks whether ind1−indtemp1+ind2−indtemp2>0, where ptemp is the temporary NN and p is the current node in the list L. If it holds, the cloud server searches the father node; otherwise, the cloud server updates the current node as the temporary NN and further checks whether ind1>0 (or ind2>0). If it holds, the cloud server searches the other child of temporary NN. Otherwise, it backs to search the father node until to the root.(1)
Decrypt(p∗): the NN for the centroid is computed as p∗ in the query algorithm. LBS users run CompInner+.Decrypt(sk,c) to compute the plaintext. Finally, the LBS users can obtain the location, namely, the NN for the centroid and the GNN for the group of LBS users.Correctness: during theSecGNN+.Query phase, the cloud server evaluates ind = CompInner+.GenInner(c1,tk11) (or ind = CompInner+.GenInner(c2,tk21)) and checks whether ind>0:(32)ind=CompInner+.GenInnerc1,tk11,=CompInner+.GenInnersa′,sb′,tk11a,tk11b,=sa′⋅tk11a+sb′⋅tk11b,=M1T×s^aTT×M1−1×x^1a+M2T×s^bTT×M2−1×x^1b,=s^a×x^1a+s^b×x^1b,=s2+sδ1−x−δ1x,=s−xs+δ1.Ifind>0, then we have s−xs+δ1>0, namely, s>x. In such a case, the cloud server searches the left child. For y−coordinate, we have the same conclusion. Therefore, the cloud server can arrive at the leaf node correctly:(33)ind1=CompInner+.GenInnerc1,tk12,=s2−2sx+x2,=s−x2.We also computeindtemp1=s−xtemp2, ind2=y−t2, and indtemp2=t−ytemp2. Thus, we have(34)flag=ind1−indtemp1+ind2−indtemp2,=s−x2+t−y2−s−xtemp2−t−ytemp2.Ifflag>0, it is easily known that the current node is closer than the temporary NN. Thus, we update the current node as the new temporary NN. Furthermore, the cloud server checks whether to search the other child through checking ind1>0 or ind2>0. Therefore, the cloud server can search the NN for the query point over ciphertexts from the core idea of KD-tree.


### 5.3. Security Analysis

In this section, we illustrate the security analysis of the proposed CompInner+ tool and SecGNN+ scheme from data privacy and query privacy (e.g., actual location privacy of LBS users and centroid privacy).Theorem 3.
The introduced CompInner+ tool achieves data privacy and query privacy from outside attackers.Proof 3.
The security analysis of the introduced tool is similar to CompInner, which is presented in Theorem1. Thus, we skip the details of proof for the sake of clarity.Theorem 4.
The proposed SecGNN+ scheme preserves the data privacy and the query privacy.Proof 4.
In the following, we present the proof from data privacy against outside attackers and query privacy (actual locations and the centroid) against outside attackers and other LBS users.
First, we will introduce the data privacy of the proposed SecGNN+ scheme. Data items are encrypted by using CompInner+.Encrypt(sk,p). Since the data privacy can be assured in Theorem 3, the SecGNN+ scheme preserves data privacy. We skip the details for the sake of clarity.
Furthermore, the centroid privacy from outside attackers will be presented as follows. In the CompCen algorithm, an outside attacker learns the knowledge about the secret keyk from solving the DDH problem (as described in the proof of Theorem 2). Thus, the centroid privacy can be assured from outside attackers in the CompCen algorithm. In the GenToken algorithm, the centroid is encrypted as(35)tk=CompInner+.GenTokensk,l,where l=xc,yc is the centroid of group of users. Since CompInner+ tool achieves query privacy, the centroid privacy can be assured in the GenToken algorithm.
Moreover, the introduced SecGNN+ scheme preserves the privacy of actual locations from outside attackers and other LBS users. The centroid computation (CompCen) algorithm consists of AV-net and BD conference key agreement protocols. That is, the centroid privacy is based on these two schemes. An outside attacker fails to obtain the centroid because learning the location requires the attacker can disclose the AV-net mask and learn the knowledge of BD conference key. Specifically, an outside attacker needs to compute gaibi from gai and gbi in AV-net protocol and compute gei−1ei from gei−1 and gei in BD conference key agreement, respectively. Under the assumption of decisional Diffie–Hellman (DDH) problem, an outside attacker fails to obtain the centroid. A LBS user ui takes part in the attack game and wants to learn the knowledge of ui+1’s actual location. Since LBS user ui knows ei and gei+1, then he can compute geiei+1. Based on the difficulty of the DDH problem, LBS user ui fails to compute gai+1bi+1 from gai+1 and gbi+1. Thus, LBS user ui could not learn the knowledge about the actual location of LBS user ui+1.


## 5.1. Basic Tool

The proposed CompInner+ contains five polynomial-time algorithms, Setup, Encrypt, GenToken, GenInner, and Decrypt. The details are described as follows.(1)
Setup (λ): it is the same with the system setup algorithm in CompInner. Thus, the secret key is sk=M1,M2,S,w1,w2,…,wd.(2)
Encrypt (sk,p): suppose that p=s,t is a data record, and this algorithm does the following steps.(1)
Adding random numbers: for a datap=s,t, the user computes s¯=s2,s,1,t¯=t2,t,1 and then extends them as s^=s2,s,1,w1,w2,…,wd and t^=t2,t,1,w1,w2,…,wd.(2)
Random splitting: splits^,t^ into two parts, s^a,s^b and t^a,t^b. For i=1,2,…,d′,IfSi=0, s^ai=s^bi=s^i and t^ai=t^bi=t^i.IfSi=1, s^ai, s^bi and t^ai, t^bi are random numbers such that s^ai+s^bi=s^i and t^ai+t^bi=t^i.(3)
Data encryption: compute the ciphertexts as(19)c1=sa′=M1T×s^aT,sb′=M2T×s^bT,c2=a′t=M1T×t^aT,tb′=M2T×t^bT.Thus, the ciphertext for data pointp is c=c1,c2.(3)
GenToken (sk,l): suppose that l=x,y, the token is generated as follows.(1)
Adding random numbers: for a datal=x,y, the user extends it as(20)x^1=1,δ1−x,−δ1x,rx11,rx12,…,rx1d,x^2=1,−2x,x2,rx21,rx22,…,rx2d,y^1=1,δ2−y,−δ2y,ry11,ry12,…,ry1d,y^2=1,−2y,y2,ry21,ry22,…,ry2d,whereδ1,δ2, rx11,…,rx1d, rx21,…,rx2d, ry11, …, ry1d, and ry21, …,ry2d are random numbers such that(21)rx1d=−∑i=1d−1rx1iwiwd,rx2d=−∑i=1d−1rx2iwiwd,ry1d=−∑i=1d−1ry1iwiwd,ry2d=−∑i=1d−1ry1iwiwd.(2)
Random splitting: splitx^1,x^2,y^1,andy^2 into two parts x^1a,x^1b, x^2a,x^2b, y^1a,y^1b, and y^2a,y^2b. For i=1,2,…,d′,IfSi=0, x^1ai, x^1bi, x^2ai, x^2bi, y^1ai, y^1bi, and y^2ai, y^2bi are random numbers such that(22)x^1ai+x^1bi=x^1i,x^2ai+x^2bi=x^2i,y^1ai+y^1bi=y^1i,y^2ai+y^2bi=y^2i.IfSi=1,(23)x^1ai=x^1bi=x^1i,x^2ai=x^2bi=x^2i,y^1ai=y^1bi=y^1i,y^2ai=y^2bi=y^2i.(3)
Data encryption: compute the ciphertexts as(24)tk11a=M1−1×x^1a,tk11b=M1−1×x^1b,tk12a=M1−1×x^2a,tk12b=M1−1×x^2b,tk21a=M1−1×y^1a,tk21b=M1−1×y^1b,tk22a=M1−1×y^2a,tk22b=M1−1×y^2b.Thus, the token generation algorithm outputs token astk=tk11,tk12,tk21,tk22, where tk11=tk11a,tk11b, tk12=tk12a,tk12b, tk21=tk21a,tk21b, and tk22=tk22a,tk22b.(4)
GenInner(pa′,pb′,la′,lb′: the inner generation algorithm computes and outputs(25)ind=pb′,lb′+la′,lb′(5)
Decrypt(sk,c=c1,c2): suppose that c1=sa′,sb′ and c2=ta′,tb′. The decryption algorithm first computes(26)s^a=M1T−1×sa′,s^b=M1T−1×sb′,t^a=M1T−1×ta′,t^b=M1T−1×tb′.Fori=1,2,…,d′,IfSi=0, s^i=s^ai=s^ai and t^i=t^ai=t^biIfSi=1, s^i=s^ai+s^bi and t^i=t^ai+t^biFinally, the user obtainss=s^2 and t=t^2.


## 5.2. The Detailed Description

From above, we convert the problem of finding GNN for a group of users to the problem of finding NN for their centroid. In the following, we illustrate an efficiency-enhanced group nearest neighbor query scheme calledSecGNN+ based on KD-tree and CompInner+ tool. The introduced SecGNN+ scheme consists of seven polynomial-time algorithms, Setup, BuildTree, EncDB, CompCen, GenToken, Query, and Decrypt. The detailed description is illustrated as follows:(1)
Setup (1λ): on inputting a security parameter λ, it outputs a cyclic group G with order q and generator g. Furthermore, this algorithm runs CompInner+ tool and outputs a secret key:(27)sk=M1,M2,S,w1,w2,…,wd.(2)
BuildTree (DB): on inputting the database DB of POIs, this algorithm proceeds the KD-tree algorithm and stores the data items in a KD-tree T.(3)
EncDB (sk,p): suppose that p=s,t is a data record stored in KD-tree T. The LBS provider runs CompInner+.Encrypt(sk,p) to compute the ciphertext as(28)c=c1,c2=sa′,sb′,ta′,ta′.(4)
CompCen (l1,l2,…,ln): suppose that l1=x1,y1, l1=x2,y2, ⋯, ln=xn,yn are coordinates of LBS users u1, u2, …, un. LBS users evaluate the centroid as follows.(1)
Each LBS userui chooses two random numbers aiandei∈Zq and publishes gai,gei to other LBS users. Then, ui computes and further broadcasts ri=gei+1/gei−1ei.(2)
The userui computes(29)gbi=Πj=1i−1gajΠj=i+1ngaj,ki=gei−1nei⋅rin−1⋅ri+1n−2⋅⋯⋅ri−2modq.(3)
Userui computes and publishes Xi=gaibigei−1eigxi. Multiplying all Xi,(30)Πi=1nXi=Πi=1ngaibigei−1eigxi,=Πi=1ngaibiΠi=1ngei−1eiΠi=1ngxi=kig∑i=1nxi=kg∑i=1nxi.Userui can get the value g∑i=1nxi through dividing by the secret key k. Since ∑i=1nxi is a small number, LBS users can compute the discrete logarithm by using the Pohlig–Hellman algorithm [30]. Considering the coordinates are six- or seven-decimal digits, they can be represented as a 32 bit data. Therefore, ∑i=1nxi is a small number and can be efficiently computed from g∑i=1nxi.(4)
Finally, userui can compute the centroid as xc=∑i=1nxi/n and yc=∑i=1nyi/n.(5)
GenToken (sk,xc,yc): after receiving the centroid xc,yc, LBS user runs CompInner+.GenToken(sk,p) to compute the token as tk=tk11,tk12,tk21,tk22, where tk11=tk11a,tk11b, tk12=tk12a,tk12b, tk21=tk21a,tk21b, and tk22=tk22a,tk22b.(6)
Query (T∗,tk): the query algorithm consists of two phases. In the first phase, the cloud server searches over the encrypted KD-tree T∗ to find a leaf node whose corresponding region includes the query point. The cloud server computes ind = CompInner+.GenInner(c1,tk11) (or ind = CompInner+.GenInner(c2,tk21)) and checks whether ind>0. If it holds, the cloud server searches the left child; otherwise, it searches the right child. The cloud server writes down the route from root to the leaf node in a list L.After arriving at the leaf node, the cloud server takes this leaf node as the temporary NN and proceeds the second phase to check whether the temporary NN is the NN. In the second phase, the cloud server checks the listL from leaf nodes back to the root. For each node, he computes(31)ind1=CompInner+.GenInnerc1,tk12,indtemp1=CompInner+.GenInnerctemp1,tk12,ind2=CompInner+.GenInnerc2,tk22,indtemp2=CompInner+.GenInnerctemp2,tk22,and checks whether ind1−indtemp1+ind2−indtemp2>0, where ptemp is the temporary NN and p is the current node in the list L. If it holds, the cloud server searches the father node; otherwise, the cloud server updates the current node as the temporary NN and further checks whether ind1>0 (or ind2>0). If it holds, the cloud server searches the other child of temporary NN. Otherwise, it backs to search the father node until to the root.(1)
Decrypt(p∗): the NN for the centroid is computed as p∗ in the query algorithm. LBS users run CompInner+.Decrypt(sk,c) to compute the plaintext. Finally, the LBS users can obtain the location, namely, the NN for the centroid and the GNN for the group of LBS users.Correctness: during theSecGNN+.Query phase, the cloud server evaluates ind = CompInner+.GenInner(c1,tk11) (or ind = CompInner+.GenInner(c2,tk21)) and checks whether ind>0:(32)ind=CompInner+.GenInnerc1,tk11,=CompInner+.GenInnersa′,sb′,tk11a,tk11b,=sa′⋅tk11a+sb′⋅tk11b,=M1T×s^aTT×M1−1×x^1a+M2T×s^bTT×M2−1×x^1b,=s^a×x^1a+s^b×x^1b,=s2+sδ1−x−δ1x,=s−xs+δ1.Ifind>0, then we have s−xs+δ1>0, namely, s>x. In such a case, the cloud server searches the left child. For y−coordinate, we have the same conclusion. Therefore, the cloud server can arrive at the leaf node correctly:(33)ind1=CompInner+.GenInnerc1,tk12,=s2−2sx+x2,=s−x2.We also computeindtemp1=s−xtemp2, ind2=y−t2, and indtemp2=t−ytemp2. Thus, we have(34)flag=ind1−indtemp1+ind2−indtemp2,=s−x2+t−y2−s−xtemp2−t−ytemp2.Ifflag>0, it is easily known that the current node is closer than the temporary NN. Thus, we update the current node as the new temporary NN. Furthermore, the cloud server checks whether to search the other child through checking ind1>0 or ind2>0. Therefore, the cloud server can search the NN for the query point over ciphertexts from the core idea of KD-tree.


## 5.3. Security Analysis

In this section, we illustrate the security analysis of the proposed CompInner+ tool and SecGNN+ scheme from data privacy and query privacy (e.g., actual location privacy of LBS users and centroid privacy).Theorem 3.
The introduced CompInner+ tool achieves data privacy and query privacy from outside attackers.Proof 3.
The security analysis of the introduced tool is similar to CompInner, which is presented in Theorem1. Thus, we skip the details of proof for the sake of clarity.Theorem 4.
The proposed SecGNN+ scheme preserves the data privacy and the query privacy.Proof 4.
In the following, we present the proof from data privacy against outside attackers and query privacy (actual locations and the centroid) against outside attackers and other LBS users.
First, we will introduce the data privacy of the proposed SecGNN+ scheme. Data items are encrypted by using CompInner+.Encrypt(sk,p). Since the data privacy can be assured in Theorem 3, the SecGNN+ scheme preserves data privacy. We skip the details for the sake of clarity.
Furthermore, the centroid privacy from outside attackers will be presented as follows. In the CompCen algorithm, an outside attacker learns the knowledge about the secret keyk from solving the DDH problem (as described in the proof of Theorem 2). Thus, the centroid privacy can be assured from outside attackers in the CompCen algorithm. In the GenToken algorithm, the centroid is encrypted as(35)tk=CompInner+.GenTokensk,l,where l=xc,yc is the centroid of group of users. Since CompInner+ tool achieves query privacy, the centroid privacy can be assured in the GenToken algorithm.
Moreover, the introduced SecGNN+ scheme preserves the privacy of actual locations from outside attackers and other LBS users. The centroid computation (CompCen) algorithm consists of AV-net and BD conference key agreement protocols. That is, the centroid privacy is based on these two schemes. An outside attacker fails to obtain the centroid because learning the location requires the attacker can disclose the AV-net mask and learn the knowledge of BD conference key. Specifically, an outside attacker needs to compute gaibi from gai and gbi in AV-net protocol and compute gei−1ei from gei−1 and gei in BD conference key agreement, respectively. Under the assumption of decisional Diffie–Hellman (DDH) problem, an outside attacker fails to obtain the centroid. A LBS user ui takes part in the attack game and wants to learn the knowledge of ui+1’s actual location. Since LBS user ui knows ei and gei+1, then he can compute geiei+1. Based on the difficulty of the DDH problem, LBS user ui fails to compute gai+1bi+1 from gai+1 and gbi+1. Thus, LBS user ui could not learn the knowledge about the actual location of LBS user ui+1.


## 6. Performance Evaluation

In this section, we first illustrate the performance of the basic tools (i.e., CompInner and CompInner+) and then demonstrate that of the introduced SecGNN and SecGNN+ schemes through experimental simulation. Specifically, we evaluate the performance with Python3 language on a machine with Intel(R) Core(TM) i7-9750H CPU processor running at 16 GB and 1 TB memory in Table 3. The matrix is provided by Numpy library, and the discrete logarithm is computed by the Pohlig–Hellman [30] algorithm. Throughout the experiment, we simulate all the LBS provider, LBS users, and the cloud server on the same machine. Furthermore, we set the extended length as d′=80, that is, equivalent the security of 1024 bit RSA keys.Table 3
Experimental simulation platform.
Operating systemWindow 10CPUIntel(R) Xeon(R) i7-9750H, 2.6GHZMemory16 GB RAMProgram languagePython 3.8Database: in the experiment, we evaluate the performance on a real database and a random database, respectively. The real database is the Sequoia database (Sequoia database.http://chorochronos.datastories.org/?q=node/58) that contains 62,556 data items in California. The random database contains 1,000,000 data items which are randomly generated. The descriptions of the Sequoia database and random database are presented in Figure 4.Figure 4
The normalization of the database. (a) Sequoia database. (b) Random database.
(a)(b)


### 6.1. Performance of the Basic Tools

CompInner and CompInner+ include system setup (Setup), data encryption (Encrypt), token generation (GenToken), inner computation (GenInner), and data decryption (Decrypt) algorithms. Figure 5 evaluates the performance of above algorithms with the increasing of expanded number d′ (set n=1000, namely, 1000 Setup, Encrypt, GenInner, GenToken, and Decrypt). Time costs of GenToken and Decrypt algorithms are mainly occupied by the computation of the inverse matrices for secret keys M1 and M2. If the inverse matrices M1−1 and M2−1 are precomputed, time costs of GenToken and Decrypt algorithms will present the similar performance with the encrypt algorithm in both tools. The detailed performance will be presented in the following experiments.Figure 5
The performance of CompInner and CompInner+ with the extended length d′. (a) CompInner tool. (b) CompInner+ tool.
(a)(b)LBS provider runs CompInner.Setup(λ) and CompInner+.Setup(λ) algorithms to produce the secret key sk, which contains two 80×80 invertible matrices M1andM2, a 80 bit string S, and random numbers w1,w2,…,w77. To enhance the efficiency, we precompute the invertible matrices M3andM4 for matrices M1andM2. The system setup algorithm can be finished in 10 ms and thus is very efficient.As illustrated in Figure6, we evaluate the performance of CompInner tool and CompInner+ tool over the Sequoia database and a random database. It is easily seen that all algorithms have a high efficiency in both tools. Since the GenInner in CompInner tool is the same with that in CompInner+, time cost of the GenInner algorithm performs the same performance. Specifically, the GenInner algorithm has the best efficiency, about 0.5 s for 60,000 inner computations and only 7.6 s for 1,000,000 inner computations for CompInner and CompInner+. The GenToken algorithm shows the worst time cost, 8.6 s for 60,000 tokens and 141.2 s for 1,000,000 tokens on CompInner tool and 32 s for 60,000 tokens and 513 s for 1,000,000 tokens on CompInner+ tool. Furthermore, since GenInner is performed once for the data utilization, it is very efficient in the following group nearest neighbor query scheme, only 0.14 ms for one token in CompInner tool and 0.51 ms for one token in CompInner+ tool. The encrypt algorithm is an one-time algorithm for database construction and is acceptable for both tools. In conclusion, both tools are very efficient for the data utilization in practice.Figure 6
The performance of the CompInner tool and CompInner+ tool increasing with the size of data items on the Sequoia database and a random database. (a) CompInner tool. (b) CompInner+ tool.
(a)(b)


### 6.2. Performance of the Introduced Schemes

For the convenience of description, we adapt some notations in this section. We denote by PlainNN the linear search nearest neighbor on plaintexts, by PlainGNN the linear search group nearest neighbor on plaintexts, by KDNN the KD-tree used in the nearest neighbor query on plaintexts, by SecGNN the SecGNN scheme in Section4, and by SecGNN+ the efficiency enhanced scheme in Section 5.The introduced SecGNN scheme contains six algorithms, system setup, database encryption, random share, token generation, database query, and result decryption, and the SecGNN+ scheme consists of seven algorithms, system setup, KD-tree build, database encryption, centroid computation, token generation, database query, and result decryption. In the following, we will describe the performance of above algorithms, respectively.System setup: for the introduced SecGNN and SecGNN+ schemes, the LBS provider runs the setup algorithm to output a cyclic group G with order q and generator g. Furthermore, the setup algorithm outputs a secret key sk, namely, two 80×80 invertible matrices M1andM2, a 80 bit string S, and random numbers w1,w2,…,w77. For the convenience of computation, the invertible matrices of M1andM2 are precomputed in this phase. The experimental simulation shows that the setup algorithm can be done in 5 ms.Tree construction: the BuildTree algorithm is run by the LBS provider to store POIs in a KD-tree data structure. The performance is illustrated in Figure7. Figure 7(a) illustrates the time cost increasing with the size of data items in the Sequoia database and Figure 7(b) presents that in a random database. Moreover, KDNN and SecGNN+ present the same efficiency as the BuildTree algorithm and only requires the LBS provider to store POIs in a KD-tree structure.Figure 7
Time cost of the KD-tree construction. (a) Sequoia database. (b) Random database.
(a)(b)Database encryption: the LBS provider runs the EncDB algorithm to assure the privacy of data items. Figure8 presents the encryption efficiency of SecGNN and SecGNN+ schemes. As illustrated in Figures 8(a) and 8(b), it is easily seen that both schemes achieve high efficiency, about 99.27 s for 1,000,000 data items on the SecGNN scheme and 182.4 s for 1,000,000 data items on the SecGNN+ scheme. Furthermore, SecGNN achieves better encryption efficiency than the SecGNN+ scheme. Because database encryption is one-time operation, it is acceptable for the SecGNN+ scheme.Figure 8
Time cost of the database encryption. (a) Sequoia database. (b) Random database.
(a)(b)Shared random and centroid computation: LBS users run the ShareRan algorithm to share a random number in the SecGNN scheme and run the CompCen algorithm to compute the centroid for the following algorithms. LBS users compute the shared random number through BD-protocol and compute their centroid by using AV-net protocol and BD-protocol. Figure9 presents the time cost increasing with the size of group users. The group size varies from 10 to 100. It costs about 25 ms to share a random number with a group of 100 LBS users in the SecGNN scheme and 180 ms to compute the centroid with 100 LBS users in the SecGNN+ scheme. In the CompCen algorithm and the following algorithms, it is enough for one special LBS user to compute the centroid and proceed the group nearest neighbor query. Finally, the special LBS user broadcasts the meeting place using the conference key. As demonstrated in Figure 9, the centroid computation is very efficient, 18 ms for 10 users and 180 ms for 100 users.Figure 9
Time cost of centroid computation.Token generation: in the SecGNN and SecGNN+ scheme, LBS users compute and generate the query token for the cloud server to search over the encrypted POIs. The cloud server directly searches the group nearest neighbor in PlainNN, PlainGNN, and KDNN, and therefore, they do not need to execute the GenToken algorithm. After receiving the shared random number in the SecGNN scheme, LBS users run the GenToken algorithm to compute the search token, respectively. The SecGNN+ scheme requires a special LBS user to compute the search token and send it to the cloud server. As illustrated in Figure 6, the search token can be computed quickly, about 0.15 ms for SecGNN and 0.5 ms for the SecGNN+ scheme.Group nearest neighbor query: the cloud server proceeds the query algorithm to search the group nearest neighbor over encrypted POIs. In Figure10, we illustrate the time cost for PlainNN, PlainGNN, and KDNN on plaintexts and time cost for SecGNN and SecGNN+ on encrypted POIs. Figure 10 presents that the PlainGNN scheme is a little slower than other introduced schemes in both the Sequoia database and random database. Since LBS users should compute the aggregate distance for each point in POIs to all group users (n=100) and linearly search the entire POIs, time cost on PlainGNN has the worst efficiency. The KDNN scheme has the best efficiency for the group nearest neighbor query over above schemes. Time cost of SecGNN scales linearly with the data items. Thus, SecGNN is impractical with million data items. As illustrated in Figure 10, the SecGNN+ scheme achieves practical search efficiency in data utilization on big data era, about 0.2 s on millions database.Figure 10
Time cost of the group nearest neighbor query. (a) Sequoia database. (b) Random database.
(a)(b)Decryption: after receiving the query result, LBS users decrypt the results and finally receive the meeting place. The decrypt algorithm only contains two matrix multiplications. The multiplication is very fast and can be computed less than 2 ms.


## 6.1. Performance of the Basic Tools

CompInner and CompInner+ include system setup (Setup), data encryption (Encrypt), token generation (GenToken), inner computation (GenInner), and data decryption (Decrypt) algorithms. Figure 5 evaluates the performance of above algorithms with the increasing of expanded number d′ (set n=1000, namely, 1000 Setup, Encrypt, GenInner, GenToken, and Decrypt). Time costs of GenToken and Decrypt algorithms are mainly occupied by the computation of the inverse matrices for secret keys M1 and M2. If the inverse matrices M1−1 and M2−1 are precomputed, time costs of GenToken and Decrypt algorithms will present the similar performance with the encrypt algorithm in both tools. The detailed performance will be presented in the following experiments.Figure 5
The performance of CompInner and CompInner+ with the extended length d′. (a) CompInner tool. (b) CompInner+ tool.
(a)(b)LBS provider runs CompInner.Setup(λ) and CompInner+.Setup(λ) algorithms to produce the secret key sk, which contains two 80×80 invertible matrices M1andM2, a 80 bit string S, and random numbers w1,w2,…,w77. To enhance the efficiency, we precompute the invertible matrices M3andM4 for matrices M1andM2. The system setup algorithm can be finished in 10 ms and thus is very efficient.As illustrated in Figure6, we evaluate the performance of CompInner tool and CompInner+ tool over the Sequoia database and a random database. It is easily seen that all algorithms have a high efficiency in both tools. Since the GenInner in CompInner tool is the same with that in CompInner+, time cost of the GenInner algorithm performs the same performance. Specifically, the GenInner algorithm has the best efficiency, about 0.5 s for 60,000 inner computations and only 7.6 s for 1,000,000 inner computations for CompInner and CompInner+. The GenToken algorithm shows the worst time cost, 8.6 s for 60,000 tokens and 141.2 s for 1,000,000 tokens on CompInner tool and 32 s for 60,000 tokens and 513 s for 1,000,000 tokens on CompInner+ tool. Furthermore, since GenInner is performed once for the data utilization, it is very efficient in the following group nearest neighbor query scheme, only 0.14 ms for one token in CompInner tool and 0.51 ms for one token in CompInner+ tool. The encrypt algorithm is an one-time algorithm for database construction and is acceptable for both tools. In conclusion, both tools are very efficient for the data utilization in practice.Figure 6
The performance of the CompInner tool and CompInner+ tool increasing with the size of data items on the Sequoia database and a random database. (a) CompInner tool. (b) CompInner+ tool.
(a)(b)


## 6.2. Performance of the Introduced Schemes

For the convenience of description, we adapt some notations in this section. We denote by PlainNN the linear search nearest neighbor on plaintexts, by PlainGNN the linear search group nearest neighbor on plaintexts, by KDNN the KD-tree used in the nearest neighbor query on plaintexts, by SecGNN the SecGNN scheme in Section4, and by SecGNN+ the efficiency enhanced scheme in Section 5.The introduced SecGNN scheme contains six algorithms, system setup, database encryption, random share, token generation, database query, and result decryption, and the SecGNN+ scheme consists of seven algorithms, system setup, KD-tree build, database encryption, centroid computation, token generation, database query, and result decryption. In the following, we will describe the performance of above algorithms, respectively.System setup: for the introduced SecGNN and SecGNN+ schemes, the LBS provider runs the setup algorithm to output a cyclic group G with order q and generator g. Furthermore, the setup algorithm outputs a secret key sk, namely, two 80×80 invertible matrices M1andM2, a 80 bit string S, and random numbers w1,w2,…,w77. For the convenience of computation, the invertible matrices of M1andM2 are precomputed in this phase. The experimental simulation shows that the setup algorithm can be done in 5 ms.Tree construction: the BuildTree algorithm is run by the LBS provider to store POIs in a KD-tree data structure. The performance is illustrated in Figure7. Figure 7(a) illustrates the time cost increasing with the size of data items in the Sequoia database and Figure 7(b) presents that in a random database. Moreover, KDNN and SecGNN+ present the same efficiency as the BuildTree algorithm and only requires the LBS provider to store POIs in a KD-tree structure.Figure 7
Time cost of the KD-tree construction. (a) Sequoia database. (b) Random database.
(a)(b)Database encryption: the LBS provider runs the EncDB algorithm to assure the privacy of data items. Figure8 presents the encryption efficiency of SecGNN and SecGNN+ schemes. As illustrated in Figures 8(a) and 8(b), it is easily seen that both schemes achieve high efficiency, about 99.27 s for 1,000,000 data items on the SecGNN scheme and 182.4 s for 1,000,000 data items on the SecGNN+ scheme. Furthermore, SecGNN achieves better encryption efficiency than the SecGNN+ scheme. Because database encryption is one-time operation, it is acceptable for the SecGNN+ scheme.Figure 8
Time cost of the database encryption. (a) Sequoia database. (b) Random database.
(a)(b)Shared random and centroid computation: LBS users run the ShareRan algorithm to share a random number in the SecGNN scheme and run the CompCen algorithm to compute the centroid for the following algorithms. LBS users compute the shared random number through BD-protocol and compute their centroid by using AV-net protocol and BD-protocol. Figure9 presents the time cost increasing with the size of group users. The group size varies from 10 to 100. It costs about 25 ms to share a random number with a group of 100 LBS users in the SecGNN scheme and 180 ms to compute the centroid with 100 LBS users in the SecGNN+ scheme. In the CompCen algorithm and the following algorithms, it is enough for one special LBS user to compute the centroid and proceed the group nearest neighbor query. Finally, the special LBS user broadcasts the meeting place using the conference key. As demonstrated in Figure 9, the centroid computation is very efficient, 18 ms for 10 users and 180 ms for 100 users.Figure 9
Time cost of centroid computation.Token generation: in the SecGNN and SecGNN+ scheme, LBS users compute and generate the query token for the cloud server to search over the encrypted POIs. The cloud server directly searches the group nearest neighbor in PlainNN, PlainGNN, and KDNN, and therefore, they do not need to execute the GenToken algorithm. After receiving the shared random number in the SecGNN scheme, LBS users run the GenToken algorithm to compute the search token, respectively. The SecGNN+ scheme requires a special LBS user to compute the search token and send it to the cloud server. As illustrated in Figure 6, the search token can be computed quickly, about 0.15 ms for SecGNN and 0.5 ms for the SecGNN+ scheme.Group nearest neighbor query: the cloud server proceeds the query algorithm to search the group nearest neighbor over encrypted POIs. In Figure10, we illustrate the time cost for PlainNN, PlainGNN, and KDNN on plaintexts and time cost for SecGNN and SecGNN+ on encrypted POIs. Figure 10 presents that the PlainGNN scheme is a little slower than other introduced schemes in both the Sequoia database and random database. Since LBS users should compute the aggregate distance for each point in POIs to all group users (n=100) and linearly search the entire POIs, time cost on PlainGNN has the worst efficiency. The KDNN scheme has the best efficiency for the group nearest neighbor query over above schemes. Time cost of SecGNN scales linearly with the data items. Thus, SecGNN is impractical with million data items. As illustrated in Figure 10, the SecGNN+ scheme achieves practical search efficiency in data utilization on big data era, about 0.2 s on millions database.Figure 10
Time cost of the group nearest neighbor query. (a) Sequoia database. (b) Random database.
(a)(b)Decryption: after receiving the query result, LBS users decrypt the results and finally receive the meeting place. The decrypt algorithm only contains two matrix multiplications. The multiplication is very fast and can be computed less than 2 ms.


## 7. Conclusions

In this work, we study the problem of the privacy-preserving group nearest neighbor query, namely, finding a meeting place with the minimum aggregate distance to a group of LBS users. The introduced SecGNN scheme supports group nearest neighbor (n≥3), while preserving the data privacy and query privacy from outside attackers. Unfortunately, it only achieves linear search complexity. To achieve high search efficiency, we design an efficiency-enhanced SecGNN+ scheme by leveraging the KD-tree structure. More specifically, we convert the GNN problem to the NN problem for the centroid and then leverage AV-net protocol and BD-conference key agreement to compute the centroid. Furthermore, the KD-tree structure and ASPE algorithm are introduced to construct the efficiency-enhanced SecGNN+ scheme. Note that the solution is compatible with other tree structures (e.g., R-tree and Quad-tree). Finally, we present the performance evaluation to show the high efficiency of our proposed schemes.



---

*Source: 5686506-2021-09-25.xml*