# An Efficient and Privacy-Preserving Multiuser Cloud-Based LBS Query Scheme

Authors: Lu Ou; Hui Yin; Zheng Qin; Sheng Xiao; Guangyi Yang; Yupeng Hu
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Location-based services (LBSs) are increasingly popular in today’s society. People reveal their location information to LBS providers to obtain personalized services such as map directions, restaurant recommendations, and taxi reservations. Usually, LBS providers offer user privacy protection statement to assure users that their private location information would not be given away. However, many LBSs run on third-party cloud infrastructures. It is challenging to guarantee user location privacy against curious cloud operators while still permitting users to query their own location information data. In this paper, we propose an efficient privacy-preserving cloud-based LBS query scheme for the multiuser setting. We encrypt LBS data and LBS queries with a hybrid encryption mechanism, which can efficiently implement privacy-preserving search over encrypted LBS data and is very suitable for the multiuser setting with secure and effective user enrollment and user revocation. This paper contains security analysis and performance experiments to demonstrate the privacy-preserving properties and efficiency of our proposed scheme.


---

## Body

## 1. Introduction

Location-based services (LBSs) are increasingly popular in today’s society. It is reported that up to 150 million people have enjoyed LBSs as early as 2014 [1]. People reveal their location information to LBS providers to obtain personalized services such as map directions, restaurant recommendations, and taxi reservations.The most common and most important service in an LBS system is a location query service. In LBS applications, a user is able to use his powerful smartphone equipped with GPS modules to obtain accurate location information anytime and anywhere by submitting a query keyword of interest (e.g., hotel) to the LBS system. Upon receiving an location query request from the user, an LBS provider rapidly returns back a target location list, in which all locations are ranked in an ascending order based on distances between the query user and these target locations.Every coin has two sides: although the LBS greatly facilitates people’s life nowadays, the user privacy disclosure problems for LBS applications are more and more serious. The LBS providers can mine LBS users’ privacy by analyzing LBS queries or recovering the spatial correlated data [2]. For example, LBS providers can easily obtain user’s mobility trace or even infer user’s real identity, healthy status, hobbies, and so on [3, 4]. To address the privacy challenge in the LBS system, many solutions have been proposed such as the pseudoidentity technique [5], location fuzzy [6–9], and private information retrieval in the trusted third party (TTP) [5, 7]. These schemes significantly promote the further development of LBS applications.With the rapid development of the cloud computing, more and more LBS providers are beginning to consider to outsource their location data and services to the cloud server for enjoying the numerous advantages brought by the cloud computing such as economic savings, great flexibility, quick deployment, excellent computation performance, and abundant bandwidth resources. However, the cloud server is not fully trusted usually by the LBS providers due to being operated by the remote commercial organizations. Once the location data is outsourced to the cloud server in the plaintext form, the data security would not be guaranteed. For example, a corrupted administrator of the cloud server may sell the location data outsourced by the LBS provider to other one for obtaining illegal profit. Presently, the most effective way to protect the confidentiality of outsourced location data is to encrypt data before outsourcing it to the cloud server [10]. On the other hand, the bare user query requests also provide more opportunities for the cloud server to mine user’s privacy just like a traditional LBS system. Therefore, the user requests should also be encrypted before being submitted to the cloud server. However, data encryption makes the available location query service a challenging task, since the ciphertext no longer bears the natures of numerical computation and character match in the plaintext field. Therefore, there are two essential problems that need to be solved in a cloud-based LBS application over the encrypted outsourced location data: (1) how to find out all target locations over the encrypted location data according to the encrypted user request; (2) how to compute or compare distances between these target locations and user current location over the encrypted outsourced location data.A recent work in [11] sets out to explore the challenging issue that how to implement the cloud-based LBS system over encrypted location data and proposes a privacy-preserving cloud-based LBS query scheme, called “EPQ.” The scheme enables the cloud server to perform LBS query over the encrypted LBS data without divulging users’ location information. However, the scheme only can enforce a user location coordinate query according to a user’s current location. In a practical LBS application, a goal-oriented keyword query is necessary for the user to accurately locate locations of interest (e.g., the user may need to accurately search hotels near to him/her). Compared with the existing work, in this paper, we propose an efficient and secure keyword-based query scheme that allows the user to be able to first accurately locate desirable locations according to the encrypted query request and then rank distances between these target locations and the user’s current location, which greatly improves the user’s location server experiences. Moreover, our scheme is very suitable for a multiuser cloud environment by equipping with flexible users enrollment and users revocation mechanisms.In this paper, we make the following three key contributions:(i)
First, we propose an efficient and privacy-preserving cloud-based LBS query scheme. For protecting the security of location data and user requests against the curious cloud server, we adopt a hybrid encryption to encrypt the outsourced location data and user requests while the cloud server can still provide accurately LBS query services for users by performing privacy-preserving and efficient search over the encrypted locations data. In addition, our scheme is very suitable for the multiuser setting by equipping with flexible user enrollment and user revocation mechanisms.(ii)
Second, we provide detailed correction analysis and security analysis. The analyses show that our scheme is correct and can achieve user privacy preservation and confidentiality of LBS data, simultaneously.(iii)
Lastly, we implement our scheme in Java and evaluate the performance on a real data set. Experimental results demonstrate that our proposed scheme is efficient and practical.The rest of our paper is organized as follows. In Section2, we review some related literatures. In Section 3, we recall a bilinear pairing map, secure kNN, and a difficulty assumption of discrete logarithm problem as the preliminaries. Then, we formalize a system model and a threat model and depict problem statements in Section 4. We present our approach in Section 5. What is more, some analyses and performance evaluations are conducted in Sections 6 and 7, respectively. Finally, we draw our conclusions in Section 8.


## 2. Related Work

In this section, we review some related works about privacy protection in traditional LBSs and cloud-based LBSs, respectively.


### 2.1. Traditional LBS Privacy Protection

Privacy leakage problem in traditional LBSs has drawn much attention of researchers, and we review mainly related literatures.Firstly, a locationk-anonymity model is introduced, which guarantees that an individual cannot be identified from k-1 other individuals [12]. What is more, in a distributed environment, an anonymous approach based on homomorphic encryption [13] is proposed to protect location privacy. However, when the anonymous region is sensitive or k individuals are the same place, the sensitive location will still be leaked. Thus the third party (TTP) is proposed to manage the location information centrally [14–16]. To achieve an accurate query, a method is proposed to convert original locations of LBS data and query, maintaining a spatial relationship between the LBS data and query [16]. However, because of many users’ sensitive information in the TTP, attackers would aim at attacking it easily. Then a scheme without the TTP is proposed, which protects the locations through private information retrieval [7]. Recently, considering mobile nodes, a distributed anonymizing protocol based on peer-to-peer architecture is proposed [17]. A specific zone is responded by each mobile node. Besides, an information-theoretic notion was introduced to protect privacy in LBS systems [18]. An approach is proposed to protect both client’s location privacy and the server’s database security by improving the oblivious transfer protocol [19]. For providing privacy-preserving map services, a new multiple mix zones location privacy protection is proposed. By using this method, users are able to query a route between two endpoints on the map, without revealing any confidential location and query information [20].


### 2.2. Cloud-Based LBS Privacy Protection

Considering the low computation and communication cost, the LBS providers outsource the LBS data to the cloud server to compute accurate LBS queries, whereas the cloud server is semitrusted. Hence the privacy problem is still a challenge in the cloud-based LBS. There are some literatures about this problem. Firstly, a spatiotemporal predicate-based encryption is proposed for fine-grained access control [21]. Then an improved homomorphic encryption [11] is proposed to protect users’ privacy and LBS data privacy. A privacy extension in crowdsourced LBS [22] is proposed. To handle the long-term privacy protection and fake path generation for LBS, a dummy-based long-term location privacy protection [23] is proposed. Recently, two-tier lightweight network coding based on pseudonym scheme in a group LBS [24] is proposed to protect privacy. What is more, a query scheme by using Bloom filter and bilinear pairing is proposed [25]. However, the literatures above did not consider the multiusers condition (i.e., joining of registered users and revocation of expired users). But unregistered users and expired users access for cloud-based LBSs is a typical scenario. Therefore, providing an efficient and privacy-preserving cloud-based LBS in multiuser environments is an unnegligible issue.


## 2.1. Traditional LBS Privacy Protection

Privacy leakage problem in traditional LBSs has drawn much attention of researchers, and we review mainly related literatures.Firstly, a locationk-anonymity model is introduced, which guarantees that an individual cannot be identified from k-1 other individuals [12]. What is more, in a distributed environment, an anonymous approach based on homomorphic encryption [13] is proposed to protect location privacy. However, when the anonymous region is sensitive or k individuals are the same place, the sensitive location will still be leaked. Thus the third party (TTP) is proposed to manage the location information centrally [14–16]. To achieve an accurate query, a method is proposed to convert original locations of LBS data and query, maintaining a spatial relationship between the LBS data and query [16]. However, because of many users’ sensitive information in the TTP, attackers would aim at attacking it easily. Then a scheme without the TTP is proposed, which protects the locations through private information retrieval [7]. Recently, considering mobile nodes, a distributed anonymizing protocol based on peer-to-peer architecture is proposed [17]. A specific zone is responded by each mobile node. Besides, an information-theoretic notion was introduced to protect privacy in LBS systems [18]. An approach is proposed to protect both client’s location privacy and the server’s database security by improving the oblivious transfer protocol [19]. For providing privacy-preserving map services, a new multiple mix zones location privacy protection is proposed. By using this method, users are able to query a route between two endpoints on the map, without revealing any confidential location and query information [20].


## 2.2. Cloud-Based LBS Privacy Protection

Considering the low computation and communication cost, the LBS providers outsource the LBS data to the cloud server to compute accurate LBS queries, whereas the cloud server is semitrusted. Hence the privacy problem is still a challenge in the cloud-based LBS. There are some literatures about this problem. Firstly, a spatiotemporal predicate-based encryption is proposed for fine-grained access control [21]. Then an improved homomorphic encryption [11] is proposed to protect users’ privacy and LBS data privacy. A privacy extension in crowdsourced LBS [22] is proposed. To handle the long-term privacy protection and fake path generation for LBS, a dummy-based long-term location privacy protection [23] is proposed. Recently, two-tier lightweight network coding based on pseudonym scheme in a group LBS [24] is proposed to protect privacy. What is more, a query scheme by using Bloom filter and bilinear pairing is proposed [25]. However, the literatures above did not consider the multiusers condition (i.e., joining of registered users and revocation of expired users). But unregistered users and expired users access for cloud-based LBSs is a typical scenario. Therefore, providing an efficient and privacy-preserving cloud-based LBS in multiuser environments is an unnegligible issue.


## 3. Preliminaries

In this section, we introduce several necessary tools used in our scheme, including a bilinear pairing map, secure kNN computation techniques, and the difficulty assumption of discrete logarithm problem.


### 3.1. Bilinear Pairing Map

LetG1 and G2 be two multiplication cyclic groups with large prime order q. A bilinear pairing map [26, 27] e:G1×G1→G2 satisfies the following properties:(i)
Bilinear: for allx,y∈Zq∗ and P,Q∈G1, ePx,Qy=ePy,Qx=eP,Qxy.(ii)
Nondegenerate: ifP,Q∈G1, then eP,G≠1∈G2.(iii)
Computable: for any elementP,Q∈G1, there exists a polynomial time algorithm to compute e(P,Q).


### 3.2. Secure kNN

Secure kNN [28] enables an efficient kNN computation over encrypted data points. It adopts an asymmetric scalar-product-preserving encryption (ASPE) to achieve a distance comparison between two encrypted data vectors. We synoptically introduce the principle of this technique as follows.Definition 1 (asymmetric scalar-product-preserving encryption).
LetE be an encryption function and E(p,K) be an encryption of a point p under a key K. E is an ASPE if and only if E just preserves the scalar product between encrypted data points and an encrypted query points; that is, (1)
pi·q=E(pi,K)·E(q,K), where pi is one encrypted data point and q is one encrypted query point;(2)
pi·pj≠E(pi,K)·E(pj,K), where pi and pj are two encrypted data points.
For ease of understanding, we describe the APSE scheme in Algorithm1. As shown in Algorithm 1, this scheme includes five parts, that is, a key, a tuple encryption function, a query encryption function, a distance comparison operator, and a decryption function.Algorithm 1:APSE scheme.
APSE Scheme Key:a d+1×d+1 invertible matrix M. Tuple Encryption Function E T : Consider an LBS data p which will be stored in a cloud server. (1) Create a d+1-dimensional point p^=pT,-0.5p2T. (2) The encrypted data p′=MTp^. Query Encryption Function  EQ: Consider an LBS query q. (1) Generate a random number r>0. (2) Create a d+1-dimensional point q^=rqT,1T. (3) The encrypted query q′=M-1q^. Distance Comparison Operator  Ae: Letp1′ and p2′ be the encrypted data of p1 and p2 respectively. To determine whether p1 is nearer to a queryq than p2 is, the system checks whether p1′-p2′⋅q′>0, where q′ is the encrypted point of q. Decryption Function  D: Consider an encrypted data p′. The original datap=πdMT-1p′, where πd is a d×d+1 matrix which projects on the first d dimensions andπd=Id,0 where Id is the d×d identity matrix.


### 3.3. Difficulty Assumption of Discrete Logarithm Problem

Given a multiplication groupG with the prime order q, g is its generator. An element x is selected from Zq∗ randomly, computing Q=gx∈G. The definition of the difficulty assumption of discrete logarithm problem (DLP) is as follows.Definition 2 (difficulty assumption of discrete logarithm problem).
GivenG and g, it is difficult to compute the correct value of x. In other words, given a tuple (G,q,gx,g), there is not an efficient polynomial time algorithm to output x.


## 3.1. Bilinear Pairing Map

LetG1 and G2 be two multiplication cyclic groups with large prime order q. A bilinear pairing map [26, 27] e:G1×G1→G2 satisfies the following properties:(i)
Bilinear: for allx,y∈Zq∗ and P,Q∈G1, ePx,Qy=ePy,Qx=eP,Qxy.(ii)
Nondegenerate: ifP,Q∈G1, then eP,G≠1∈G2.(iii)
Computable: for any elementP,Q∈G1, there exists a polynomial time algorithm to compute e(P,Q).


## 3.2. Secure kNN

Secure kNN [28] enables an efficient kNN computation over encrypted data points. It adopts an asymmetric scalar-product-preserving encryption (ASPE) to achieve a distance comparison between two encrypted data vectors. We synoptically introduce the principle of this technique as follows.Definition 1 (asymmetric scalar-product-preserving encryption).
LetE be an encryption function and E(p,K) be an encryption of a point p under a key K. E is an ASPE if and only if E just preserves the scalar product between encrypted data points and an encrypted query points; that is, (1)
pi·q=E(pi,K)·E(q,K), where pi is one encrypted data point and q is one encrypted query point;(2)
pi·pj≠E(pi,K)·E(pj,K), where pi and pj are two encrypted data points.
For ease of understanding, we describe the APSE scheme in Algorithm1. As shown in Algorithm 1, this scheme includes five parts, that is, a key, a tuple encryption function, a query encryption function, a distance comparison operator, and a decryption function.Algorithm 1:APSE scheme.
APSE Scheme Key:a d+1×d+1 invertible matrix M. Tuple Encryption Function E T : Consider an LBS data p which will be stored in a cloud server. (1) Create a d+1-dimensional point p^=pT,-0.5p2T. (2) The encrypted data p′=MTp^. Query Encryption Function  EQ: Consider an LBS query q. (1) Generate a random number r>0. (2) Create a d+1-dimensional point q^=rqT,1T. (3) The encrypted query q′=M-1q^. Distance Comparison Operator  Ae: Letp1′ and p2′ be the encrypted data of p1 and p2 respectively. To determine whether p1 is nearer to a queryq than p2 is, the system checks whether p1′-p2′⋅q′>0, where q′ is the encrypted point of q. Decryption Function  D: Consider an encrypted data p′. The original datap=πdMT-1p′, where πd is a d×d+1 matrix which projects on the first d dimensions andπd=Id,0 where Id is the d×d identity matrix.


## 3.3. Difficulty Assumption of Discrete Logarithm Problem

Given a multiplication groupG with the prime order q, g is its generator. An element x is selected from Zq∗ randomly, computing Q=gx∈G. The definition of the difficulty assumption of discrete logarithm problem (DLP) is as follows.Definition 2 (difficulty assumption of discrete logarithm problem).
GivenG and g, it is difficult to compute the correct value of x. In other words, given a tuple (G,q,gx,g), there is not an efficient polynomial time algorithm to output x.


## 4. Background

In this section, we formally introduce our system model and threat model and then state our proposed problem.


### 4.1. System Model

In our system model, there are three entities: an LBS provider, a cloud server, and a group of LBS users, as shown in Figure1. Next, we introduce each entity of our model as follows.Figure 1
System model.(i) LBS Provider. An LBS provider is a location data owner. It outsources large-scale location data to the cloud server for enjoying the low-cost storage services and powerful computation services. To ensure the confidentiality of location data, all location data is uploaded to the cloud server after being encrypted by the LBS provider. In addition, when an LBS user wants to join the system, the LBS provider provides authentication and registration service for the LBS user. Once the LBS user passes authentication, the LBS provider sends some important security parameters to the user via secure communication channels. Correspondingly, the LBS provider is also able to revoke any expired LBS user, who no longer has the query capabilities for the outsourced location data when being revoked by the LBS provider.(ii) A Group of LBS Users. A group of LBS users are the location data users, who enjoy convenient LBSs by submitting LBS query requests to the LBS provider anywhere and anytime. To hide query requests of LBS users for protecting privacy, LBS users first encrypt their query requests and then submit the encrypted query requests to the cloud server. Note that the LBS users are usually referred to the legal registered users and unregistered users and revoked users from the provider cannot enjoy LBSs.(iii) Cloud Server. Upon receiving the encrypted LBS query request submitted by a legal LBS user, the cloud server is responsible for performing the query over encrypted outsourced location data on behalf of the LBS user and returning the satisfied query results to the LBS user. In the whole query processes, the cloud server does not know any contents about outsourced location data, the user’s query request, and the current location of the LBS user.


### 4.2. Problem Statements

In a conventional LBS system, the LBS data construction usually is organized as the category set and the location data set, as shown in Table1(a). A CATEGORY denotes the general name of location data, which contains multiple concrete location data. Each concrete location data is a four-tuple ID,TITLE,COORDINATE,DESCRIPTION, which describes the detailed information of a certain location. When a registered user searches an interested location, he/she submits the specified CATEGORY and his current location coordinates to the LBS system. The LBS system first searches over the category set according to the submitted CATEGORY to obtain all target locations and then sorts target locations in an ascending order based on the distances between the user’s current location and these target locations, which are easily computed according to the user’s coordinate and each target location’s coordinate, and finally returns the first k nearest locations to the query user, if the query user sends an optional parameter k to the LBS system. It means that the LBS system can analyze what are the LBS user interested in and his/her real-time location, when receiving an LBS query.Table 1
LBS data creation.
(a) { C A T E G O R Y } Location Data Set{ID,TITLE,COORDINATE,DESCRIPTION} School: 1, Hunan University, (x1,y1), 211,985, ⋮ 15, Center South University, (x15,y15), 211,985. Hospital: 16, the Second Xiangya Hospital, (x16,y16), grade III-A hospital, ⋮ 31, the Union Hospital, x31,y31, grade III-A hospital. ⋮ ⋮ Hotel: 450, Huatian Hotel, (x450,y450), 5stars, ⋮ 500, Westin Hotel, (x500,y500), 4stars.  (b) { C A T E G O R Y } Location Data Set{ID,TITLE,COORDINATE,DESCRIPTION} E 1(School): 1, E3(Hunan University), E2((x1,y1)), E3211,985, ⋮ 15, E3(Center South University), E2((x15,y15)), E3211,985. E 1(Hospital): 16, E3(the Xiangya Hospital), E2((x16,y16)), E3(grade III-A hospital), ⋮ 31, E3(the Union Hospital), E2((x31,y31)), E3(grade III-A hospital ⋮ ⋮ E 1(Hotel): 450, E3(Huatian Hotel), E2((x450,y450)), E3(5  stars, ⋮ 500, E3(Westin Hotel), E2(x500,y500), E3(4  stars.To ensure the confidentiality of LBS data and enable registered users to enforce efficient location query in the privacy-preserving manner when the LBS provider outsources LBS data and query services to the cloud server, in this paper, we adopt a hybrid encryption mechanism to encrypt the LBS data; the encryption version of LBS data is shown in Table1(b), where E1, E2, and E3 denote different encryption scheme, respectively, whose constructions will be formally proposed in the next section. By encrypting different fields of LBS data using the different encryptions E1, E2, and E3, our scheme allows the cloud server to provide totally the same query service over encrypted location data as the plaintext environment aforementioned while information about the location data and user’s query request is exposed to the cloud server.From the point of view of LBS users, compared with the LBS system in the plaintext environment, the only difference in our scheme is that an LBS user needs to encrypt the interestedGATEGORY and his/her location coordinates to generate a query trapdoor. The cloud server performs the LBS query over encrypted outsourced location data according to the query trapdoor. Of course, the necessary decryption operations need to be involved for the LBS user once the encrypted LBS query results are received; however, this is not our concerned problem in this paper.In addition, the LBS system is a typical multiuser application, our scheme designs efficient and flexible user registration and user revocation mechanisms to guarantee that only registered users are able to use the LBS system and unregistered users or revoked users have not access to it.


## 4.1. System Model

In our system model, there are three entities: an LBS provider, a cloud server, and a group of LBS users, as shown in Figure1. Next, we introduce each entity of our model as follows.Figure 1
System model.(i) LBS Provider. An LBS provider is a location data owner. It outsources large-scale location data to the cloud server for enjoying the low-cost storage services and powerful computation services. To ensure the confidentiality of location data, all location data is uploaded to the cloud server after being encrypted by the LBS provider. In addition, when an LBS user wants to join the system, the LBS provider provides authentication and registration service for the LBS user. Once the LBS user passes authentication, the LBS provider sends some important security parameters to the user via secure communication channels. Correspondingly, the LBS provider is also able to revoke any expired LBS user, who no longer has the query capabilities for the outsourced location data when being revoked by the LBS provider.(ii) A Group of LBS Users. A group of LBS users are the location data users, who enjoy convenient LBSs by submitting LBS query requests to the LBS provider anywhere and anytime. To hide query requests of LBS users for protecting privacy, LBS users first encrypt their query requests and then submit the encrypted query requests to the cloud server. Note that the LBS users are usually referred to the legal registered users and unregistered users and revoked users from the provider cannot enjoy LBSs.(iii) Cloud Server. Upon receiving the encrypted LBS query request submitted by a legal LBS user, the cloud server is responsible for performing the query over encrypted outsourced location data on behalf of the LBS user and returning the satisfied query results to the LBS user. In the whole query processes, the cloud server does not know any contents about outsourced location data, the user’s query request, and the current location of the LBS user.


## 4.2. Problem Statements

In a conventional LBS system, the LBS data construction usually is organized as the category set and the location data set, as shown in Table1(a). A CATEGORY denotes the general name of location data, which contains multiple concrete location data. Each concrete location data is a four-tuple ID,TITLE,COORDINATE,DESCRIPTION, which describes the detailed information of a certain location. When a registered user searches an interested location, he/she submits the specified CATEGORY and his current location coordinates to the LBS system. The LBS system first searches over the category set according to the submitted CATEGORY to obtain all target locations and then sorts target locations in an ascending order based on the distances between the user’s current location and these target locations, which are easily computed according to the user’s coordinate and each target location’s coordinate, and finally returns the first k nearest locations to the query user, if the query user sends an optional parameter k to the LBS system. It means that the LBS system can analyze what are the LBS user interested in and his/her real-time location, when receiving an LBS query.Table 1
LBS data creation.
(a) { C A T E G O R Y } Location Data Set{ID,TITLE,COORDINATE,DESCRIPTION} School: 1, Hunan University, (x1,y1), 211,985, ⋮ 15, Center South University, (x15,y15), 211,985. Hospital: 16, the Second Xiangya Hospital, (x16,y16), grade III-A hospital, ⋮ 31, the Union Hospital, x31,y31, grade III-A hospital. ⋮ ⋮ Hotel: 450, Huatian Hotel, (x450,y450), 5stars, ⋮ 500, Westin Hotel, (x500,y500), 4stars.  (b) { C A T E G O R Y } Location Data Set{ID,TITLE,COORDINATE,DESCRIPTION} E 1(School): 1, E3(Hunan University), E2((x1,y1)), E3211,985, ⋮ 15, E3(Center South University), E2((x15,y15)), E3211,985. E 1(Hospital): 16, E3(the Xiangya Hospital), E2((x16,y16)), E3(grade III-A hospital), ⋮ 31, E3(the Union Hospital), E2((x31,y31)), E3(grade III-A hospital ⋮ ⋮ E 1(Hotel): 450, E3(Huatian Hotel), E2((x450,y450)), E3(5  stars, ⋮ 500, E3(Westin Hotel), E2(x500,y500), E3(4  stars.To ensure the confidentiality of LBS data and enable registered users to enforce efficient location query in the privacy-preserving manner when the LBS provider outsources LBS data and query services to the cloud server, in this paper, we adopt a hybrid encryption mechanism to encrypt the LBS data; the encryption version of LBS data is shown in Table1(b), where E1, E2, and E3 denote different encryption scheme, respectively, whose constructions will be formally proposed in the next section. By encrypting different fields of LBS data using the different encryptions E1, E2, and E3, our scheme allows the cloud server to provide totally the same query service over encrypted location data as the plaintext environment aforementioned while information about the location data and user’s query request is exposed to the cloud server.From the point of view of LBS users, compared with the LBS system in the plaintext environment, the only difference in our scheme is that an LBS user needs to encrypt the interestedGATEGORY and his/her location coordinates to generate a query trapdoor. The cloud server performs the LBS query over encrypted outsourced location data according to the query trapdoor. Of course, the necessary decryption operations need to be involved for the LBS user once the encrypted LBS query results are received; however, this is not our concerned problem in this paper.In addition, the LBS system is a typical multiuser application, our scheme designs efficient and flexible user registration and user revocation mechanisms to guarantee that only registered users are able to use the LBS system and unregistered users or revoked users have not access to it.


## 5. A Privacy-Preserving Multiuser LBS Query Scheme Based on Hybrid Encryption

In this section, we describe the implementation details of our privacy-preserving multiuser LBS query scheme. From the system-level point of view, our scheme includes six key modules: system initialization, new user grant, location data encryption, query trapdoor generation, search over encrypted location data, and user revocation. Each module is operated by one entity independently or multiple entities interactively and all modules integrally constitute our privacy-preserving multiuser LBS query system.


### 5.1. System Initialization

The system initialization operation is executed by the LBS provider to set up the system running environment. The LBS provider takes a large security parameterl as input and first generates two multiplication cyclic groups G1 and G2 with the large prime order q equipping the bilinear pairing map e:G1×G1→G2. Let g be a generator of G1. Then, the algorithm defines a cryptographical hash function h1:{0,1}∗→G1, which maps a message of arbitrary length to an element in G1. Lastly, the algorithm chooses a random value x∈Zq∗ and generates a 3×3 invertible matrix M that are kept secretly by the LBS provider and opens the public parameter PK={G1,G2,e,q,g,h1}.


### 5.2. New User Grant

When a new LBS useru wants to join the system, the LBS provider registers the new user in this phase. At first, the LBS provider selects a random value xu∈Zq∗ for u and computes gx/xu and the inverse matrix M-1 of M. Then, gx/xu, M-1, and xu are sent to the user u by secure communication channels. When u receives gx/xu, M-1, and xu, he/she randomly selects ru∈Zq∗ and keeps ru, M-1 secretly and then further computes gru.According to the received valuegx/xu, u computes his/her register secret key Enrku: (1)Enrku=gx/xu×gru=gx/xu+ru.At last,(u,Enrku) is sent to the cloud server and the cloud server stores this tuple into a user list U-Enrkey.


### 5.3. Location Data Encryption

To guarantee the security of location data, the LBS provider needs to encrypt all location information before outsourcing them to the cloud server. In this paper, to enable an efficient and privacy-preserving LBS query, we use different encryption mechanisms to encrypt the different attributes of the location data. Without loss of generality, we use{ID:IDd,TITLE:Td;COORDINATE:(xd,yd);DESCRIPTION:Dd} to denote any location data d belongs to CATEGORY  Cd in category set. The LBS provider takes the following three steps to encrypt the location data d.First, the LBS provider uses its secret valuex to code Cd as h1(Cd)x and further employs the bilinear pairing map e to calculate e(h1(Cd)x,g). We use E1 to denote the code operation of CATEGORY attribute of the location data such that (2)E1Cd=eh1Cdx,g.Second, the LBS provider uses the secretly preserved invertible matrixM to encrypt d’s coordinate (xd,yd) as (3)E2xd,yd=MTxd,yd,-0.5xd2+yd2T.Here, correspondingly, we use E2 to denote this encryption operation.Third, for the remaining other attributes TITLE and DESCRIPTION, the LBS provider adopts any semantically secure symmetric encryption such as AES under a given keysk to encrypt them, denoted as E3 in our paper such that (4)E3Td=AESskTd,E3Dd=AESskDd.


### 5.4. Query Trapdoor Generation

To preserve user’s query privacy and enable correct search over encrypted location data, a query useru with the current location coordinate (xu,yu) needs to encrypt his/her query request before it is submitted to the cloud server. In this paper, a query trapdoor generation is conducted in two steps.First, the useru chooses a desired query objective denoted as q (e.g., q=Hotel) and uses the secret value xu granted by the LBS provider and the secret value ru randomly chosen by himself/herself in the user grant phase to encrypt q as h1(q)xu and h1(q)xuru.Second, the useru generates a random number r>0 and uses the matrix M-1 granted by the LBS provider to encrypt the current location coordinate (xu,yu) as M-1(rxu,ryu,r)T. Ultimately, the query trapdoor of q can be denoted as follows: (5)Tuq=h1qxu,h1qxuru,M-1rxu,ryu,rT.


### 5.5. Search over Encrypted Location Data

After the query useru generates a query trapdoor Tu(q), he/she submits Tu(q) and a parameter k to the cloud server. Upon receiving the query trapdoor Tu(q) and k, the powerful cloud server is responsible for searching over encrypted outsourced location data on behalf of the query use, without knowing any plaintext information of the outsourced location data and the user query request. If the user u is a legal user, the cloud server returns back the first k encrypted target locations that satisfy the query and are nearest to the query user. Therefore, in the whole query process, the cloud server must perform two key operations under the encrypted environment: (1) searching the encrypted category set according to the query trapdoor to obtain all target locations; (2) sorting the distances between target locations and user’s current location in an ascending order. To achieve the above goal, the cloud sever processes the search in two steps.First, the cloud server looks up the query useru’s registration information u,Enrku from the user list U-Enrkey. If the user information does not exist, the cloud server rejects the query; otherwise it linearly scans the encrypted category set and obtains all encrypted target location data if it finds out an encrypted CATEGORY  E1(C) in the encrypted category set that satisfies the following equation: (6)E1C=eEnrku,h1qxueg,h1qxuru.Second, upon obtaining all target locations, the cloud server sorts the distances between target locations and user’s query location by evaluating(7)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0,where i and j are any two locations satisfying the query with the encrypted coordinate E2(xi,yi) and E2(xj,yj), respectively.If the above inequality holds, then this indicates that the target locationi is closer to the query user u than the target location j. Hence, i is sorted in the front of j. Finally, the cloud server returns the first k encrypted locations to the query user u.


### 5.6. User Revocation

User revocation is an essential yet challenging task in a practical multiuser application such as an LBS system. In some related literatures supporting user revocation, to prevent revoked users from continuing to access outsourced cloud data, the data provider usually has to rebuild data index or reencrypt large amounts of data and reuploads them to the cloud server and issues new keys to the remaining users. It unavoidably brings heavy computation and communication cost for the data provider because of the high of dynamic of users in the cloud environment. In this paper, we propose an efficient user revocation mechanism without any data reencryption and keys update operations while being able to effectively prevent the revoked user from searching outsourced location data. More concretely, for a useru′ who will be revoked by the LBS provider, the LBS provider first sends the user information about u′ to the cloud server. Then, the cloud server scans user information in the user list U-Enrkey to find out the information of u′ and deletes (u′,Enrku′). Once (u′,Enrku′) is deleted from U-Enrkey, u′ no longer has the capability to search location data stored at the cloud server. Since without Enrku′, the cloud server cannot complete matching between the trapdoor and encrypted CATEGORY according to the query scheme proposed in Section 5.5, u′ can still generate a legal query trapdoor.


## 5.1. System Initialization

The system initialization operation is executed by the LBS provider to set up the system running environment. The LBS provider takes a large security parameterl as input and first generates two multiplication cyclic groups G1 and G2 with the large prime order q equipping the bilinear pairing map e:G1×G1→G2. Let g be a generator of G1. Then, the algorithm defines a cryptographical hash function h1:{0,1}∗→G1, which maps a message of arbitrary length to an element in G1. Lastly, the algorithm chooses a random value x∈Zq∗ and generates a 3×3 invertible matrix M that are kept secretly by the LBS provider and opens the public parameter PK={G1,G2,e,q,g,h1}.


## 5.2. New User Grant

When a new LBS useru wants to join the system, the LBS provider registers the new user in this phase. At first, the LBS provider selects a random value xu∈Zq∗ for u and computes gx/xu and the inverse matrix M-1 of M. Then, gx/xu, M-1, and xu are sent to the user u by secure communication channels. When u receives gx/xu, M-1, and xu, he/she randomly selects ru∈Zq∗ and keeps ru, M-1 secretly and then further computes gru.According to the received valuegx/xu, u computes his/her register secret key Enrku: (1)Enrku=gx/xu×gru=gx/xu+ru.At last,(u,Enrku) is sent to the cloud server and the cloud server stores this tuple into a user list U-Enrkey.


## 5.3. Location Data Encryption

To guarantee the security of location data, the LBS provider needs to encrypt all location information before outsourcing them to the cloud server. In this paper, to enable an efficient and privacy-preserving LBS query, we use different encryption mechanisms to encrypt the different attributes of the location data. Without loss of generality, we use{ID:IDd,TITLE:Td;COORDINATE:(xd,yd);DESCRIPTION:Dd} to denote any location data d belongs to CATEGORY  Cd in category set. The LBS provider takes the following three steps to encrypt the location data d.First, the LBS provider uses its secret valuex to code Cd as h1(Cd)x and further employs the bilinear pairing map e to calculate e(h1(Cd)x,g). We use E1 to denote the code operation of CATEGORY attribute of the location data such that (2)E1Cd=eh1Cdx,g.Second, the LBS provider uses the secretly preserved invertible matrixM to encrypt d’s coordinate (xd,yd) as (3)E2xd,yd=MTxd,yd,-0.5xd2+yd2T.Here, correspondingly, we use E2 to denote this encryption operation.Third, for the remaining other attributes TITLE and DESCRIPTION, the LBS provider adopts any semantically secure symmetric encryption such as AES under a given keysk to encrypt them, denoted as E3 in our paper such that (4)E3Td=AESskTd,E3Dd=AESskDd.


## 5.4. Query Trapdoor Generation

To preserve user’s query privacy and enable correct search over encrypted location data, a query useru with the current location coordinate (xu,yu) needs to encrypt his/her query request before it is submitted to the cloud server. In this paper, a query trapdoor generation is conducted in two steps.First, the useru chooses a desired query objective denoted as q (e.g., q=Hotel) and uses the secret value xu granted by the LBS provider and the secret value ru randomly chosen by himself/herself in the user grant phase to encrypt q as h1(q)xu and h1(q)xuru.Second, the useru generates a random number r>0 and uses the matrix M-1 granted by the LBS provider to encrypt the current location coordinate (xu,yu) as M-1(rxu,ryu,r)T. Ultimately, the query trapdoor of q can be denoted as follows: (5)Tuq=h1qxu,h1qxuru,M-1rxu,ryu,rT.


## 5.5. Search over Encrypted Location Data

After the query useru generates a query trapdoor Tu(q), he/she submits Tu(q) and a parameter k to the cloud server. Upon receiving the query trapdoor Tu(q) and k, the powerful cloud server is responsible for searching over encrypted outsourced location data on behalf of the query use, without knowing any plaintext information of the outsourced location data and the user query request. If the user u is a legal user, the cloud server returns back the first k encrypted target locations that satisfy the query and are nearest to the query user. Therefore, in the whole query process, the cloud server must perform two key operations under the encrypted environment: (1) searching the encrypted category set according to the query trapdoor to obtain all target locations; (2) sorting the distances between target locations and user’s current location in an ascending order. To achieve the above goal, the cloud sever processes the search in two steps.First, the cloud server looks up the query useru’s registration information u,Enrku from the user list U-Enrkey. If the user information does not exist, the cloud server rejects the query; otherwise it linearly scans the encrypted category set and obtains all encrypted target location data if it finds out an encrypted CATEGORY  E1(C) in the encrypted category set that satisfies the following equation: (6)E1C=eEnrku,h1qxueg,h1qxuru.Second, upon obtaining all target locations, the cloud server sorts the distances between target locations and user’s query location by evaluating(7)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0,where i and j are any two locations satisfying the query with the encrypted coordinate E2(xi,yi) and E2(xj,yj), respectively.If the above inequality holds, then this indicates that the target locationi is closer to the query user u than the target location j. Hence, i is sorted in the front of j. Finally, the cloud server returns the first k encrypted locations to the query user u.


## 5.6. User Revocation

User revocation is an essential yet challenging task in a practical multiuser application such as an LBS system. In some related literatures supporting user revocation, to prevent revoked users from continuing to access outsourced cloud data, the data provider usually has to rebuild data index or reencrypt large amounts of data and reuploads them to the cloud server and issues new keys to the remaining users. It unavoidably brings heavy computation and communication cost for the data provider because of the high of dynamic of users in the cloud environment. In this paper, we propose an efficient user revocation mechanism without any data reencryption and keys update operations while being able to effectively prevent the revoked user from searching outsourced location data. More concretely, for a useru′ who will be revoked by the LBS provider, the LBS provider first sends the user information about u′ to the cloud server. Then, the cloud server scans user information in the user list U-Enrkey to find out the information of u′ and deletes (u′,Enrku′). Once (u′,Enrku′) is deleted from U-Enrkey, u′ no longer has the capability to search location data stored at the cloud server. Since without Enrku′, the cloud server cannot complete matching between the trapdoor and encrypted CATEGORY according to the query scheme proposed in Section 5.5, u′ can still generate a legal query trapdoor.


## 6. Analysis

In this section, we analyze the search correctness and security to prove that our proposed scheme is correct and secure.


### 6.1. Search Correctness Analysis

When an authorized query useru submits his/her query trapdoor Tu(q) to the cloud server, the cloud server firstly obtains the all encrypted locations satisfying the query q by performing a matching operation between an encrypted CATEGORY and Tu(q). Specifically, the cloud server judges whether E1(C)=e(Enrku,h1(q)xu)/e(g,h1(q)xuyu) holds or not for an encryption CATEGORY  E1(C). If the equation holds, then this indicates that the query q correctly matches E1(C) and the cloud server obtains all target locations belong to CATEGORY  C. The correctness can be easily verified as follows:(8)eEnrku,h1qxueg,h1qxuru=egx/xu+ru,h1qxueg,h1qxuru=egx/xu,h1qxuegru,h1qxueg,h1qxuru=eg,h1qxu·x/xueg,h1qxu·rueg,h1qxuru=eh1qx,g=eh1Cx,gC=q=E1C.Then, for any two target locations i and j, the cloud server is able to determine whether i is closer to the query current location than j by evaluating(9)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0.This is because that (10)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT=MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2TTM-1rxu,ryu,rT=xi,yi,-0.5xi2+yi2T-xj,yj,-0.5xj2+yj2TTMTM-1rxu,ryu,rT=0.5rxj2+yj2-xi2+yi2+2xixu+yiyu-xjxu-yjyu=0.5rdxj,yj,xu,yu-dxi,yi,xu,yu,where dxi,yi,xu,yu (d(xj,yj),(xu,yu), resp.) denotes the Euclidean distance between the location i (j, resp.) and the user’s current location. So, (11)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0⟺0.5rdxj,yj,xu,yu-dxi,yi,xu,yu>0dxj,yj,xu,yu>dxi,yi,xu,yu.Thus, the cloud server is able to sort all target locations according to the above distance comparisons in an ascending order and returns back the firstk nearest locations to the query user.


### 6.2. Security Analysis

In our proposed scheme, three encryption schemesE1, E2, and E3 are employed to protect the confidentiality of LBS data. In this section, we will analyze the security of our scheme against the “honest-but-curious” cloud server in the multiuser environment.E 2 is a semantically secure symmetric encryption such as AES that encrypts the TITLE and DESCRIPTION fields of LBS data. The semantic security of AES guarantees the security of TITLE and DESCRIPTION fields of LBS data. We use secure kNN encryption technique denoted as E2 to encrypt the COORDINATE attribute of LBS data and query user’s coordinate to enable a secure and effective distance comparison. The security of the COORDINATE attribute of LBS data and the query user’s coordinate mainly relies on the security of secure kNN scheme. For the CATEGORY attribute of LBS data, we use E3 to encrypt it to enable secure and flexible search over encrypted location data. Specifically, given a location data with CATEGORY attribute C, the ciphertext can be denoted as E3(C)=e(h1(C)x,g)=e(h1(C),g)x. Since e(h1(C),g) is a group element in G2 with a large prime order, the secret key x is acknowledgedly intractable from E3(C) in the large number field due to the well-known DLP assumption. Without the secret key x kept secretly by the LBS provider, the cloud server cannot recover the message C from encryption E3.In addition, in the multiuser environment, the system should prevent an illegal user from requesting for query LBS data stored in the cloud server. In our scheme, when a registered useru wants to query the LBS location data using q, u uses secret query keys xu and ru to generate the query trapdoor of q, trapu(q)=(h1(q)xu,h1(q)xuru). Under the assumption of DLP, attackers cannot compute out xu and ru according to trapu(q). Without the correct xu and ru, an illegal user uI cannot generate the correct query trapdoor such that uI cannot perform the correct query over encrypted location data. For a revoked user uR, although uR can generate the trapdoor trapuR(q) for q, uR still cannot let the cloud server perform a correct query on behalf of him/her due to lacking of the necessary query parameter EnrkuR that has been deleted from the list U-Enrkey by the cloud server in the phase of user revocation.


## 6.1. Search Correctness Analysis

When an authorized query useru submits his/her query trapdoor Tu(q) to the cloud server, the cloud server firstly obtains the all encrypted locations satisfying the query q by performing a matching operation between an encrypted CATEGORY and Tu(q). Specifically, the cloud server judges whether E1(C)=e(Enrku,h1(q)xu)/e(g,h1(q)xuyu) holds or not for an encryption CATEGORY  E1(C). If the equation holds, then this indicates that the query q correctly matches E1(C) and the cloud server obtains all target locations belong to CATEGORY  C. The correctness can be easily verified as follows:(8)eEnrku,h1qxueg,h1qxuru=egx/xu+ru,h1qxueg,h1qxuru=egx/xu,h1qxuegru,h1qxueg,h1qxuru=eg,h1qxu·x/xueg,h1qxu·rueg,h1qxuru=eh1qx,g=eh1Cx,gC=q=E1C.Then, for any two target locations i and j, the cloud server is able to determine whether i is closer to the query current location than j by evaluating(9)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0.This is because that (10)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT=MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2TTM-1rxu,ryu,rT=xi,yi,-0.5xi2+yi2T-xj,yj,-0.5xj2+yj2TTMTM-1rxu,ryu,rT=0.5rxj2+yj2-xi2+yi2+2xixu+yiyu-xjxu-yjyu=0.5rdxj,yj,xu,yu-dxi,yi,xu,yu,where dxi,yi,xu,yu (d(xj,yj),(xu,yu), resp.) denotes the Euclidean distance between the location i (j, resp.) and the user’s current location. So, (11)MTxi,yi,-0.5xi2+yi2T-MTxj,yj,-0.5xj2+yj2T·M-1rxu,ryu,rT>0⟺0.5rdxj,yj,xu,yu-dxi,yi,xu,yu>0dxj,yj,xu,yu>dxi,yi,xu,yu.Thus, the cloud server is able to sort all target locations according to the above distance comparisons in an ascending order and returns back the firstk nearest locations to the query user.


## 6.2. Security Analysis

In our proposed scheme, three encryption schemesE1, E2, and E3 are employed to protect the confidentiality of LBS data. In this section, we will analyze the security of our scheme against the “honest-but-curious” cloud server in the multiuser environment.E 2 is a semantically secure symmetric encryption such as AES that encrypts the TITLE and DESCRIPTION fields of LBS data. The semantic security of AES guarantees the security of TITLE and DESCRIPTION fields of LBS data. We use secure kNN encryption technique denoted as E2 to encrypt the COORDINATE attribute of LBS data and query user’s coordinate to enable a secure and effective distance comparison. The security of the COORDINATE attribute of LBS data and the query user’s coordinate mainly relies on the security of secure kNN scheme. For the CATEGORY attribute of LBS data, we use E3 to encrypt it to enable secure and flexible search over encrypted location data. Specifically, given a location data with CATEGORY attribute C, the ciphertext can be denoted as E3(C)=e(h1(C)x,g)=e(h1(C),g)x. Since e(h1(C),g) is a group element in G2 with a large prime order, the secret key x is acknowledgedly intractable from E3(C) in the large number field due to the well-known DLP assumption. Without the secret key x kept secretly by the LBS provider, the cloud server cannot recover the message C from encryption E3.In addition, in the multiuser environment, the system should prevent an illegal user from requesting for query LBS data stored in the cloud server. In our scheme, when a registered useru wants to query the LBS location data using q, u uses secret query keys xu and ru to generate the query trapdoor of q, trapu(q)=(h1(q)xu,h1(q)xuru). Under the assumption of DLP, attackers cannot compute out xu and ru according to trapu(q). Without the correct xu and ru, an illegal user uI cannot generate the correct query trapdoor such that uI cannot perform the correct query over encrypted location data. For a revoked user uR, although uR can generate the trapdoor trapuR(q) for q, uR still cannot let the cloud server perform a correct query on behalf of him/her due to lacking of the necessary query parameter EnrkuR that has been deleted from the list U-Enrkey by the cloud server in the phase of user revocation.


## 7. Evaluation

In this section, we evaluate the performance of our proposed scheme from the perspective of the LBS provider, the LBS user, and the cloud server, respectively. The software and hardware configurations of the LBS provider and LBS user side are Windows 7 desktop systems with Intel Core 2 Duo CPU 2.26 GHZ, 3 GB memory, and 320 GHZ hard driver and the cloud sever side is a virtual machine with Core 2 Duo CPU 4 × 2.394 GHZ, 8 GB memory on the Dell blade sever M610, and the Linux Centos 5.8 OS.All programs are developed using Java language and the JPBC library [29] is employed to implement group operations. We execute all experiments in a real data set collected from theopen street map [30] with 50 categories and the number of concrete location data being 1000 by extracting the location data belonging toYuelu District, Changsha, China.


### 7.1. LBS Data Encryption

Figure2(a) shows that the time cost of encrypting LBS data for the LBS provider increases linearly with the increasing size of category set when the total number of location data remains unchanged (n=1000). Figure 2(b) shows the number of concrete location data has little influence on the time cost of encrypting LBS data when fixing the size of category set (c=50). Recall that, in our scheme, E1 is used to encrypt categories in category set and E2 and E3 are used to encrypt location data. Experimental results from Figure 2 illustrate that the time cost of encrypting LBS data is closely related to the encryption E1 while not being almost affected by E2 and E3. It is reasonable that the E1 consists of the time-consuming pair operation and exponent operation over the ellipse curve group while E2 and E3 almost do not consume time when an extremely small message and 3-dimensional vector are encrypted by them, respectively.Figure 2
(a) The time cost of encrypting LBS data for LBS provider for different size of category set with fixed number of location data,n=1000; (b) the time cost of encrypting location data for LBS provider for different number of location data with fixed size of category set, c=50.
(a) (b)


### 7.2. Query Request Encryption

According to the query trapdoor generation proposed in the Section5.4, in the whole processes of the query request encryption, three key operations are involved to encrypt an interested query keyword and current location coordinate for a registered LBS user (i.e., the hash operation, the exponentiation operation on group, and the matrix multiplication operation between a 3×3 matrix and a 3-dimensional column vector). The time cost of each operation based on our software/hardware setting is shown in Table 2. Therefore, the total time cost of generating a query request for an LBS user can be denoted as h1+2∗EG1+M≈161 ms; it is extremely efficient in practice.Table 2
Time cost of operation.
Notations Descriptions Time (ms) h1 Hash functionh1:{0,1}∗→G1 ≈93 EG1 Exponentiation operation on groupG1 ≈34 M Matrix multiplication operation <1


### 7.3. Query over Encrypted LBS Data

Figures3(a) and 3(b) show the time cost of search over encrypted location data for the cloud server. We can observe that the number of categories and encrypted location data have little influence on the overhead of search for the cloud server. This is because that the main time cost for the search is to only enforce two relatively time-consuming pairing operations while linear search over 50 categories according to the query trapdoor for target location data and 3-dimensional vector computation for distance comparison almost does not consume time.Figure 3
(a) The time cost of search for cloud server for different number of categories with fixed number of location data,n=1000; (b) the time cost for search for cloud server for different number of location data with fixed number of categories; (c) the system response time for different number of search users with fixed number of categories and location data, n=1000, c=50.
(a) (b) (c)Figure3(c) shows the average response time of our query scheme for different sizes of query users. We can see that the response time grows linearly with the increasing number of query users. When the number of query users achieves 100, the response time is about 6.82 s, and this is extremely efficient in practical application.


## 7.1. LBS Data Encryption

Figure2(a) shows that the time cost of encrypting LBS data for the LBS provider increases linearly with the increasing size of category set when the total number of location data remains unchanged (n=1000). Figure 2(b) shows the number of concrete location data has little influence on the time cost of encrypting LBS data when fixing the size of category set (c=50). Recall that, in our scheme, E1 is used to encrypt categories in category set and E2 and E3 are used to encrypt location data. Experimental results from Figure 2 illustrate that the time cost of encrypting LBS data is closely related to the encryption E1 while not being almost affected by E2 and E3. It is reasonable that the E1 consists of the time-consuming pair operation and exponent operation over the ellipse curve group while E2 and E3 almost do not consume time when an extremely small message and 3-dimensional vector are encrypted by them, respectively.Figure 2
(a) The time cost of encrypting LBS data for LBS provider for different size of category set with fixed number of location data,n=1000; (b) the time cost of encrypting location data for LBS provider for different number of location data with fixed size of category set, c=50.
(a) (b)


## 7.2. Query Request Encryption

According to the query trapdoor generation proposed in the Section5.4, in the whole processes of the query request encryption, three key operations are involved to encrypt an interested query keyword and current location coordinate for a registered LBS user (i.e., the hash operation, the exponentiation operation on group, and the matrix multiplication operation between a 3×3 matrix and a 3-dimensional column vector). The time cost of each operation based on our software/hardware setting is shown in Table 2. Therefore, the total time cost of generating a query request for an LBS user can be denoted as h1+2∗EG1+M≈161 ms; it is extremely efficient in practice.Table 2
Time cost of operation.
Notations Descriptions Time (ms) h1 Hash functionh1:{0,1}∗→G1 ≈93 EG1 Exponentiation operation on groupG1 ≈34 M Matrix multiplication operation <1


## 7.3. Query over Encrypted LBS Data

Figures3(a) and 3(b) show the time cost of search over encrypted location data for the cloud server. We can observe that the number of categories and encrypted location data have little influence on the overhead of search for the cloud server. This is because that the main time cost for the search is to only enforce two relatively time-consuming pairing operations while linear search over 50 categories according to the query trapdoor for target location data and 3-dimensional vector computation for distance comparison almost does not consume time.Figure 3
(a) The time cost of search for cloud server for different number of categories with fixed number of location data,n=1000; (b) the time cost for search for cloud server for different number of location data with fixed number of categories; (c) the system response time for different number of search users with fixed number of categories and location data, n=1000, c=50.
(a) (b) (c)Figure3(c) shows the average response time of our query scheme for different sizes of query users. We can see that the response time grows linearly with the increasing number of query users. When the number of query users achieves 100, the response time is about 6.82 s, and this is extremely efficient in practical application.


## 8. Conclusion

In this paper, we propose a privacy-preserving multiuser LBS query scheme based on the hybrid encryption in the cloud environment. Adopting different encryptions on different attributes of LBS data, our proposed scheme can achieve users’ location privacy protection and the confidentiality of LBS data. In particular, the LBS query is performed in the cipher environment, thus the LBS users can get the accurate LBS query results without disclosing their private information. Besides, we consider LBS user accountability and LBS user dynamics, for preventing the unregistered users and expired users accessing. And extensive experiments show that our proposed scheme is highly efficient. In the future, we will consider collusion attacks in the cloud-based LBSs.



---

*Source: 4724815-2018-03-08.xml*