A Fine-Grained and Privacy-Preserving Query Scheme for Fog Computing-Enhanced Location-Based Service

Abstract

Location-based services (LBS), as one of the most popular location-awareness applications, has been further developed to achieve low-latency with the assistance of fog computing. However, privacy issues remain a research challenge in the context of fog computing. Therefore, in this paper, we present a fine-grained and privacy-preserving query scheme for fog computing-enhanced location-based services, hereafter referred to as FGPQ. In particular, mobile users can obtain the fine-grained searching result satisfying not only the given spatial range but also the searching content. Detailed privacy analysis shows that our proposed scheme indeed achieves the privacy preservation for the LBS provider and mobile users. In addition, extensive performance analyses and experiments demonstrate that the FGPQ scheme can significantly reduce computational and communication overheads and ensure the low-latency, which outperforms existing state-of-the art schemes. Hence, our proposed scheme is more suitable for real-time LBS searching.

1. Introduction

With the rapid development of the Internet of Things (IoTs), fog computing has been presented by Cisco in 2012 [1] as a supplement to cloud computing. Based on its network edge computing feature, fog computing is able to provide location-awareness applications, where the location-based service (LBS) is the most popular [2,3]. With the assistance of fog computing, the LBS providers can outsource the LBS data to fog nodes and thus provide people a convenient life [4]. For instance, through the LBS provided by a local fog node, a mobile user can query and search points of interest (POIs) within a given distance to his/her location [5,6]. Actually, LBS query has become one of the killer applications in LBS, which allows mobile users to query a LBS provider (such as Google or Bing maps) to obtain the detailed information about POIs in their vicinity (e.g., restaurants, hospitals, etc.). For example, when a tourist arrives at a new place, it is very necessary to query some interesting places, such as hotels, restaurants, scenic spots and so on, based on the LBS. Hence, we focus on the LBS query in this paper.

Although LBS can benefit people a lot, the submitted queries may lead to some sensitive information about users being revealed, such as hobbies, current location and the location where mobile users will reach [7,8]. To clearly illustrate the privacy challenge in LBS query, we consider the following scenario, where a mobile user wants to find a hospital by exposing his location to a local fog node. Thus, this fog node can infer user’s location where he will reach according to his request (the content of the matched POIs). However, even worse, the health condition that is very sensitive to this user, may be disclosed. Conceivably, without the privacy assurance in fog computing, the LBS can not continue to its flourish because users’ personal trajectory and hobby may be exposed. In addition, owing to the mobility of mobile users, the low-latency is very critical for the LBS query [9]. For example, when a driver wants to find the nearest restaurant on a heavy-traffic road, he has to keep driving while waiting for the response to ensure smooth traffic. If the response is slow, the result may already not satisfy the current spatial range of this diver, i.e., the driver has traveled far away. Therefore, latency should also be taken into account.

Recently, many privacy-preserving LBS schemes have been proposed to prevent the location privacy of LBS users. For examples, location obfuscation technology has been presented to protect users’ precise locations from disclosing [10,11]. In addition, spatial cloaking technology has been proposed to conceal the precise location in a cloaking area [12,13]. However, the accuracy of the matched results in these schemes are not satisfactory, since the locations submitted by users are not precise. In order to ensure the data privacy and improve the accuracy of results simultaneously, privacy information retrieval (PIR) [14] has been applied to the LBS query [15,16]. Unfortunately, as mentioned in [17], PIR needs to transmit the entire LBS data to the mobile users, which brings about the heavy communication burden, especially for big data. In addition, a mobile user has to additionally access the LBS database’s index data in a privacy-preserving way, which leads to the linear calculations of all LBS data. Hence, the communication and computational costs are tremendous, which is not cost-efficient for mobile users. To overcome this disadvantage, some efficient cryptographic algorithm-based schemes have been developed for the LBS query, where most of these schemes focused on cloud computing, as it can offer on-demand and scalable storage and unlimited computing capacity, especially for big data processing. For examples, Li et al. [18] discussed an efficient privacy-preserving location-based query over outsourced encrypted data by coding and bilinear pairing techniques; Zhu et al. [19] proposed a new efficient and privacy-preserving LBS query scheme in the outsourced cloud; Peng et al. [20] developed the collaborative trajectory privacy-preserving scheme for the trajectory privacy of continuous queries. However, with vast LBS requests generated everyday, the transmission of the extraordinarily huge volume data to the cloud has resulted in unbearable transmission latency, which will degrade the quality of service to end users, especially mobile users [9,21,22]. As a result, privacy-preserving LBS query schemes designed for cloud computing may not satisfy the low-latency.

Hence, the content of fog computing has been introduced to make up the disadvantage of the centralized processing in the cloud [1]. As far as we know, existing schemes in fog computing mainly concentrated on location privacy in wireless sensor networks [23] or real-time navigation of vehicular ad hoc networks [24]. Nevertheless, few fog computing-based schemes considered the privacy issue in the LBS query. Moreover, almost all state-of-the-art LBS query schemes only take the location matching into consideration without considering content matching, and thus this is not fine-grained. For instance, when a mobile user wants to query a hospital within 500 m, the returned results in existing schemes are all the LBS data meeting the spatial range (within 500 m). That is, in addition to the hospital, the result may include a restaurant, a park, or a mall and so on. In fact, these results are not necessary for LBS users, and it will lead to additional communication and computational costs, e.g., users have to decrypt all the returned ciphertexts to find the point of interest.

To not only ensure the privacy-preserving and low-latency, but also achieve the fine-grained query result, in this paper, we propose a fine-grained and privacy-preserving query scheme for fog computing-enhanced location-based service (FGPQ). The contributions of this paper are threefold as follows.

• First, we present our FGPQ scheme, which is characterized by employing the bilinear pairing [25] and the asymmetric scalar-product preserving encryption (ASPE) [26] to realize the LBS searching. In addition to satisfying the given spatial range, the searching result satisfies the given searching content, which is not considered in many up-to-date schemes.
• Secondly, we give detailed privacy analysis to show that our proposed FGPQ indeed achieves the privacy preservation of both the LBS provider and mobile users.
• Finally, we theoretically analyze the computational and communication overheads, and run extensive experiments to demonstrate that our FGPQ scheme is more efficient than the EPLQ scheme [18] and EPQ scheme [19]. In addition, the latency analysis shows that our FGPQ scheme is really low-latency, which is suitable for the real-time LBS query.

The remainder of this paper is organized as follows. In Section 2, we introduce our system model and design goals. Then, we describe some preliminaries in Section 3. In Section 4, we present our FGPQ scheme, followed by privacy analysis and performance analysis in Section 5 and Section 6, respectively. Finally, we draw our conclusions in Section 7.

2. System Model and Design Goals

In this section, we formalize the system model used in this paper, and identify design goals.

2.1. System Model

We illustrate an overall architecture of fog computing-enhanced LBS query in Figure 1, which includes a set of mobile users, a set of fog nodes $\{i{d}_1,i{d}_2,\dots ,i{d}_n\}$ and an LBS provider.

• LBS provider: the LBS provider acts as a profit company, providing the location-based services for the registered mobile users. With the advantages of fog computing, the LBS provider prefers to outsource its LBS data containing service content and the corresponding geographic location to appropriate fog nodes based on the geographic location distance, which can provide the low-latency LBS for mobile users.
• Fog nodes $\{i{d}_1,i{d}_2,\dots ,i{d}_n\}$: with the pay-as-you-use way, each fog node $i{d}_j$ stores the LBS data from the LBS provider and provides the fine-grained query services for mobile users.
• Mobile users: a mobile user who acts as a registered member of the LBS provider, sends a query that contains the searching content, current location information and searching spatial range, to a local fog node for requesting the nearby POIs satisfying both the given searching content and spatial range.

Similar to the most common assumption in research literature (see [27,28]), fog nodes are considered honest-but-curious, which honestly follow the underlying scheme, but are curious about the privacy of mobile users and the LBS provider. In the LBS applications, the LBS provider or mobile users would not collude with fog nodes to obtain others’ privacy. This is because if the LBS provider agree to collude with a fog node to obtain the content of a user’ request, then this node can obtain some LBS data considered as provider’s privacy from the LBS searching. For example, if a fog node obtain a mobile user’s request (e.g., a hospital within 500 m) from the collusion attack, then it can obtain the real information of the matched LBS data, i.e., it knows that the service content of all matched LBS data is the hospital and the corresponding location is within 500 m of the current location. In other words, once the privacy of mobile users is disclosed, the privacy of the LBS provider will also be disclosed. Therefore, the LBS provider would not collude with fog nodes. Similarly, mobile users would also not collude with fog nodes. Note that, since the privacy preservation is our focus, some active attacks are beyond the scope of this work and will be discussed in the future.

2.2. Design Goals

The goals of our proposed FGPQ scheme are described as follows:

• Privacy preservation. As a profit company, the LBS data are considered as the LBS provider’s own asset, which should be protected from disclosing. Therefore, the LBS data should be encrypted before being outsourced to fog nodes. For mobile users, a service query may contain some sensitive information, e.g., hobbies, current location and the location where mobile users will reach, which should also be protected from disclosing. Hence, mobile users should send the encrypted query request to the nearby fog node.
• Fine-grained query result. Besides the searching spatial range, the FGPQ scheme should satisfy the searching content, e.g., a hospital or a restaurant. That is, the query result should satisfy the given searching content and searching spatial range simultaneously.
• Efficiency. Owing to the mobility of mobile users, the low-latency is very critical for the LBS [9]. Hence, computational costs and communication delay should be as less as possible.

3. Preliminaries

In this section, we first outline the bilinear pairing [25], which will be used for generating the index of the service content to complete the content matching. Then, we describe the asymmetric scalar-product preserving encryption algorithm (ASPE) [26], which will be applied to achieve the encrypted location matching.

3.1. Bilinear Pairing

Given a security parameter $\kappa \in {\mathbb{Z}}^{+}$, a bilinear-parameter generation algorithm $\mathcal{G}(\kappa )$ outputs a tuple $(p,g,\mathbb{G},{\mathbb{G}}_T,e)$, where p is a $\kappa$-bit prime number, $\mathbb{G}$ and ${\mathbb{G}}_T$ are two multiplicative cyclic groups of order p, g is a generator of $\mathbb{G}$, and $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$ is a bilinear pairing with the following properties:

• Bilinearity: for all $u,v\in \mathbb{G}$ and $a,b\in {\mathbb{Z}}_p^{*}$, we have $e(u^a,v^b)=e{(u,v)}^{ab}$.
• Non-degeneracy: $e(g,g)\ne 1$.

The definitions of bilinear pairing parameter generator and the related complexity assumptions are described below [25,29].

Definition 1.

(Bilinear generator) The bilinear parameter generator $Gen(·)$ is a probabilistic algorithm that takes a security parameter κ as input and outputs a 5-tuple $(\mathbb{G},{\mathbb{G}}_T,p,g,e)$.

Definition 2.

(Computational Diffie–Hellman (CDH) problem) Given $(g,g^a,g^b)\in \mathbb{G}$, for unknown $a,b\in {\mathbb{Z}}_p^{*}$, compute $g^{ab}\in \mathbb{G}$.

Definition 3.

(Discrete logarithm (DL) problem) Given $Q\in \mathbb{G}$, compute $a\in {\mathbb{Z}}_p^{*}$ such that $g^a=Q$.

3.2. The Asymmetric Scalar-Product Preserving Encryption (ASPE)

Wong et al. [26] developed an asymmetric scalar-product preserving encryption (ASPE), which has been widely applied to the outsourced range matching in the ciphertext [30,31]. Hence, this encryption algorithm can also applied to the outsourced spatial range query in the ciphertext.

• Key generation ($Gen(d)$). Given a security parameter d, two $d\times d$ invertible matrices $M_1$ and $M_2$, and a d-dimensional binary vector S are chosen as the private key, denoted as $sk=(S,M_1,M_2)$. Note that the binary vector S is a splitting indicator to split the plaintext vector into two random vectors, where $S\left[i\right]$ is the i-th bit in S.
• Tuple encryption function $E_T(·)$. Consider a d-dimensional vector P in a database. Firstly, split P into two d-dimensional vectors $(P_a,P_b)$ based on the splitting indicator S. Specifically, if $S\left[i\right]=0(i=1,2,\dots ,d)$, $P_a\left[i\right]=P_b\left[i\right]=P\left[i\right]$; if $S\left[i\right]=1(i=1,2,\dots ,d)$, the value of $P\left[i\right]$ will be randomly split into $P_a\left[i\right]$ and $P_b\left[i\right]$ such that $P\left[i\right]=P_a\left[i\right]+P_b\left[i\right]$. Then, the encrypted value of P can be calculated as

  $$E_T(P,sk)=(P_a{M}_1,P_b{M}_2).$$

  (1)
• Query encryption function $E_Q(·)$. Consider a d-dimensional vector Q, split it into two d-dimensional vectors $(Q_a,Q_b)$: if $S\left[i\right]=0(i=1,2,\dots ,d)$, the value of $Q\left[i\right]$ can be randomly split into $Q_a\left[i\right]$ and $Q_b\left[i\right]$ with $Q\left[i\right]=Q_a\left[i\right]+Q_b\left[i\right]$; if $S\left[i\right]=1(i=1,2,\dots ,d)$, $Q_a\left[i\right]=Q_b\left[i\right]=Q\left[i\right]$. The encrypted value of Q can be generated as

  $$E_Q(Q,sk)=(M_1^{-1}{Q}_a^{\mathrm{T}},M_2^{-1}{Q}_b^{\mathrm{T}}),$$

  (2)

  where $Q_a^{\mathrm{T}}$ and $Q_b^{\mathrm{T}}$ denote the transpose of $Q_a$ and $Q_b$, respectively.
• Outsourced scalar-product calculation. With two ciphertexts $E_T(P,sk)$ and $E_Q(Q,sk)$, the outsourced scalar-product can be calculated as

  $$\begin{array}{ccc}\hfill E_T(P,sk)·E_Q(Q,sk)& =& (P_a{M}_1,P_b{M}_2)·(M_1^{-1}{Q}_a^{\mathrm{T}},M_2^{-1}{Q}_b^{\mathrm{T}})\hfill \\ & =& P_a{M}_1·M_1^{-1}{Q}_a^{\mathrm{T}}+P_b{M}_2·M_2^{-1}{Q}_b^{\mathrm{T}}\hfill \\ & =& P_a·Q_a^{\mathrm{T}}+P_b·Q_b^{\mathrm{T}}\hfill \\ & =& P·Q.\hfill \end{array}$$
  The correctness of the scalar-product calculation can be referred to [26].
• Decryption Function $D(·)$. Consider an encrypted value $(P_a{M}_1,P_b{M}_2)$. Firstly, compute the inverse matrices $M_1^{-1}$ and $M_2^{-1}$, and then extract two vectors $P_a$ and $P_b$, i.e., $P_a=P_a{M}_1·M_1^{-1}$, $P_b=P_b{M}_2·M_2^{-1}$. Finally, recover the original d-dimensional vector P with the splitting indicator S:

  $$P\left[i\right]=\left\{\begin{array}{ccc}\hfill P_a\left[i\right]=P_b\left[i\right],& if& S\left[i\right]=0,\hfill \\ \hfill P_a\left[i\right]+P_b\left[i\right],& if& S\left[i\right]=1.\hfill \end{array}\right.$$

The Properties of ASPE Algorithm: For any encrypted tuple $E_T(P_i,sk)$ and an encrypted query $E_Q(Q,sk)$, the ASPE algorithm satisfies the following two properties:

• For any $P_i$ encrypted by $E_T(·)$ and any query Q encrypted by $E_Q(·)$:

  $$P_i·Q=E_T(P_i,sk)·E_Q(Q,sk).$$

  (3)
• For any $P_i$ and $P_j$ encrypted by $E_T(·)$:

  $$P_i·P_j\ne E_T(P_i,sk)·E_T(P_j,sk).$$

  (4)

Note that the actual dimension d may be too small to resist the brute-force attack. Therefore, it is better to improve the system security by making d larger, which can be achieved by adding artificial dimensions to the data vector. In particular, extend a d-dimensional vector to a $d^{\prime }$-dimensional ($d\le d^{\prime }$) by padding artificial data such that the scalar-product over the added data is 0. In addition, $d^{\prime }\ge 80$ is large enough to make the system security. The details can be referred to [26]. Unless other specification, the encryption $E_T(P,sk)$ and $E_Q(Q,sk)$ are denoted by $E_T(P)$ and $E_Q(Q)$ for short in the rest of this paper, respectively.

4. Proposed FGPQ Scheme

This section presents a fine-grained and privacy-preserving query scheme for fog computing-enhanced LBS (FGPQ), which mainly consists of two parts: system initialization and privacy-preserving LBS query. In particular, the LBS provider mainly initializes the LBS system in the system initialization part, which includes the generation of public and private keys, and LBS data encryption. The privacy-preserving LBS query completes the LBS query process, which includes query request generation, LBS searching and result retrieval. The details are shown as follows.

4.1. System Initialization

The LBS provider initializes the system by following steps:

• Key generation. The LBS provider generates the public and private keys, which are used to encrypt the LBS data and the query request. Specifically, the LBS provider first generates the bilinear pairing tuple $(p,g,\mathbb{G},{\mathbb{G}}_T,e)$ and the ASPE algorithm’s private key $(S,M_1,M_2)$, respectively. Then, it chooses a large random number $\alpha \in {\mathbb{Z}}_p^{*}$ as the master-key, and a cryptographic hash function $h:{\{0,1\}}^{*}\to {\mathbb{Z}}_p^{*}$. In addition, in our proposed scheme, the actual dimension d of the ASPE algorithm is 7, which can not ensure the sufficient security; thus, we should extend d to $d^{\prime }=80$. To this end, the LBS provider also chooses $(d^{\prime }-d)$ random numbers ${\omega }_{d+1},{\omega }_{d+2},\dots ,{\omega }_{d^{\prime }}$ as the private key of the ASPE algorithm. After that, the LBS provider publishes $(p,g,\mathbb{G},{\mathbb{G}}_T,e,h)$ as the public key. Once a mobile user is registered in the LBS provider, the LBS provider will assign the private key $(\alpha ,S,M_1^{-1},M_2^{-1},{\omega }_{d+1},\dots ,{\omega }_{d^{\prime }})$ to mobile users through the secure channel.
• LBS data encryption. As mentioned in [18,19], the LBS provider has all LBS data in the system, which can be denoted as $\{(m_1,(X_1,Y_1)),\dots ,(m_k,(X_k,Y_k))\}$. In particular, $m_i$ and $(X_i,Y_i)$ denote the service content and the corresponding location for i-th service, respectively. In order to protect the privacy, the LBS provider encrypts the LBS data and separately sends them to appropriate fog nodes. Concretely, for each service item $(m_i,(X_i,Y_i))$, where $i=1,2,\dots ,k$, the LBS provider conducts the following calculations.
  • For the service content $m_i$, the LBS provider chooses a random number $r_i\in {\mathbb{Z}}_p^{*}$, and generates the ciphertext as

    $$E(m_i)=(g^{\alpha h(m_i)r_i},g^{r_i}).$$
  • For the location information $(X_i,Y_i)$, the LBS provider first generates a 7-dimensional vector as $W^{(i)}=(1,1,X_i^2,Y_i^2,-2X_i,-2Y_i,-1)$, and extends it to a $d^{\prime }$-dimensional vector $\widehat{W^{(i)}},$ where the first seven dimensions are copied from $W^{(i)}$, and for $j=8$ to $d^{\prime }-1$, set $\widehat{W^{(i)}}\left[j\right]=r_j$ ($r_j$ is a random number), and $\widehat{W^{(i)}}\left[d^{\prime }\right]=\frac{-{\sum }_{j=8}^{d^{\prime }-1}{\omega }_j{r}_j}{{\omega }_{d^{\prime }}}$, i.e., $\widehat{W^{(i)}}=(1,1,X_i^2,Y_i^2,-2X_i,-2Y_i,-1,r_8,r_9,\dots ,r_{d^{\prime }-1},\frac{-{\sum }_{j=8}^{d^{\prime }-1}{\omega }_j{r}_j}{{\omega }_{d^{\prime }}})$. Then, the LBS provider encrypts $\widehat{W^{(i)}}$ with the private key $(S,M_1,M_2)$ by means of the tuple encryption function $E_T(·)$ (the Equation (1)), that is,

    $$E_T(\widehat{W^{(i)}})=(\widehat{W_a^{(i)}}·M_1,\widehat{W_b^{(i)}}·M_2),$$

    where $\widehat{W_a^{(i)}}$ and $\widehat{W_b^{(i)}}$ are two split vectors of $\widehat{W^{(i)}}$.

Finally, based on the geographic location distance, the LBS provider outsources all k encrypted LBS data $(E(m_i),E_T(\widehat{W^{(i)}}))$, where $i=1,2,\dots ,k$, to appropriate fog nodes.

4.2. Privacy-Preserving LBS Query

This section achieves the privacy-preserving LBS query by means of the bilinear pairing and the ASPE algorithm, which includes LBS query request generation, LBS searching and request result decryption. Before that, we first define a range query used for location range matching.

Definition 4.

Given the location coordinate $(x_{*},y_{*})$ and the searching spatial range T, a location coordinate $(x_i,y_i)$ is within the searching spatial range if and only if

$$R=\sqrt{{(x_{*}-x_i)}^2+{(y_{*}-y_i)}^2}\le T,$$

(5)

where R is the Euclidean distance used to compute the distance between two coordinates [32].

4.2.1. LBS Query Request Generation

When a mobile user wants to search for a POI within a certain range, e.g., a hospital within 1000 m of the current location, he should send the query request that contains the searching content $m_{*}$ (a hospital), the current location $(X_{*},Y_{*})$ and the searching spatial range $T_{*}$ (within 1000 m), to a local fog node (denoted as $i{d}_j$). In order to ensure the privacy, he encrypts the request information $(m_{*},(X_{*},Y_{*}),T_{*})$ firstly, and then sends the encrypted query request to the fog node $i{d}_j$. The details are described as follows.

• For the searching content $m_{*}$, the user chooses a random number $r_{*}\in {\mathbb{Z}}_p^{*}$, and generates the ciphertext as

  $$E(m_{*})=(g^{\alpha h(m_{*})r_{*}},g^{r_{*}}).$$
• For the location information $(X_{*},Y_{*})$ and the searching spatial range $T_{*}$, the user first generates a 7-dimensional vector as $L=(X_{*}^2,Y_{*}^2,1,1,X_{*},Y_{*},T_{*}^2)$, and extends it to a $d^{\prime }$-dimensional vector $\widehat{L}$ where the first seven dimensions are copied from L, and for $i=8$ to $d^{\prime }$, set $\widehat{L}\left[i\right]={\omega }_i$, i.e., $\widehat{L}=(X_{*}^2,Y_{*}^2,1,1,X_{*},Y_{*},T_{*}^2,{\omega }_8,{\omega }_9,\dots ,{\omega }_{d^{\prime }})$. Then, the user chooses a random large positive number $\beta$ to confuse $\widehat{L}$, and computes ${\widehat{L}}^{\prime }=\beta ·\widehat{L}$. After that, the user encrypts ${\widehat{L}}^{\prime }$ with the private key $(S,M_1^{-1},M_2^{-1})$ by means of the query encryption function $E_Q(·)$ (the Equation (2)) as

  $$E_Q({\widehat{L}}^{\prime })=(M_1^{-1}·{\widehat{L}}_a^{\prime },M_2^{-1}·{\widehat{L}}_b^{\prime }),$$

  where ${\widehat{L}}_a^{\prime }$ and ${\widehat{L}}_b^{\prime }$ are two column vectors split from ${\widehat{L}}^{\prime }$.

Finally, the user sends the encrypted query request $\{E(m_{*}),E_Q({\widehat{L}}^{\prime })\}$ to the fog node $i{d}_j$.

4.2.2. LBS Searching

After receiving the encrypted query request $\{E(m_{*}),E_Q({\widehat{L}}^{\prime })\}$, the fog node $i{d}_j$ completes the LBS searching to find the most matched LBS item, which not only meets both the searching content and spatial range, but also has the shortest distance from the user’s location. Specifically, suppose the fog node $i{d}_j$ receives $k_j$ encrypted LBS items from the LBS provider, denoted as $\{(E(m_1),E_T(\widehat{W^{(1)}})),(E(m_2),E_T(\widehat{W^{(2)}})),\dots ,(E(m_{k_j}),E_T(\widehat{W^{(k_j)}}))\}$. For each $(E(m_i),E_T(\widehat{W^{(i)}}))$, where $i=1,2,\dots ,k_j$, the fog node $i{d}_j$ executes the following operations.

• For $E_T(\widehat{W^{(i)}})$, the fog node $i{d}_j$ first computes

  $$\begin{array}{ccc}\hfill R_i& =& E_T(\widehat{W^{(i)}})·E_Q({\widehat{L}}^{\prime })=(\widehat{W_a^{(i)}}{M}_1,\widehat{W_b^{(i)}}{M}_2)·(M_1^{-1}{\widehat{L}}_a^{\prime },M_2^{-1}{\widehat{L}}_b^{\prime })\hfill \\ \hfill & =& \widehat{W_a^{(i)}}{M}_1·M_1^{-1}{\widehat{L}}_a^{\prime }+\widehat{W_b^{(i)}}{M}_2·M_2^{-1}{\widehat{L}}_b^{\prime }\hfill \\ \hfill & =& \widehat{W_a^{(i)}}{\widehat{L}}_a^{\prime }+\widehat{W_b^{(i)}}{\widehat{L}}_b^{\prime }\hfill \\ \hfill & =& \widehat{W^{(i)}}·{\widehat{L}}^{\prime }\hfill \\ \hfill & =& \beta ({(X_{*}-X_i)}^2+{(Y_{*}-Y_i)}^2-T_{*}^2+{\omega }_8{r}_8+\cdots +{\omega }_{d^{\prime }-1}{r}_{d^{\prime }-1}-\sum _{j=8}^{d^{\prime }-1}{\omega }_j{r}_j)\hfill \\ \hfill & =& \beta ({(X_{*}-X_i)}^2+{(Y_{*}-Y_i)}^2-T_{*}^2).\hfill \end{array}$$

  (6)
  Then, it checks whether $R_i\le 0$ holds. If not, it means that the LBS item $(E(m_i),E_T(\widehat{W^{(i)}}))$ does not satisfy the searching spatial range.
• If $R_i\le 0$ holds, similarly to [33], the fog node $i{d}_j$ checks whether

  $$e(g^{\alpha h(m_i)r_i},g^{r_{*}})=e(g^{\alpha h(m_{*})r_{*}},g^{r_i})$$

  (7)

  holds. If not, it means that the service content $m_i$ does not satisfy the given searching content $m_{*}$. Otherwise, the LBS item $(m_i,(X_i,Y_i))$ satisfy the searching condition given by mobile users.

Eventually, the fog node $i{d}_j$ sends the matched result $E_T(\widehat{W^{(i)}})$ to the user. Note that if the service $m_{*}$ has multi-matched locations, the fog node $i{d}_j$ always returns the nearest location from the user (the location with the smallest $R_i$).

4.2.3. Request Result Decryption

After receiving the result, e.g., $E_T(\widehat{W^{(i)}})=(\widehat{W_a^{(i)}}{M}_1,\widehat{W_b^{(i)}}{M}_2)$, the user recovers the vector $\widehat{W^{(i)}}$ by means of the decryption function D, and then extracts the first seven dimensions in it, i.e., $W^{(i)}=(1,1,X_i^2,Y_i^2,-2X_i,-2Y_i,-1)$. According to $W^{(i)}$, the user can obtain the matched location $(X_i,Y_i)$ about the searching content $m_{*}$.

5. Privacy Analysis

Following our design goals, we discuss how the proposed FGPQ scheme achieves the privacy preservation of the LBS provider and mobile users.

The privacy preservation of mobile users: When a mobile user wants to search the POI satisfying the special spatial range and searching content, he or she sends an encrypted request $(E(m_{*}),E_Q({\widehat{L}}^{\prime }))$ to the fog node $i{d}_j$. In particular, the ciphertext $E(m_{*})$ is computed as $E(m_{*})=(g^{\alpha h(m_{*})r_{*}},g^{r_{*}})$. Hence, based on hard problems of the CDH and DL in bilinear pairing (Definitions 2 and 3), the fog node $i{d}_j$ can not obtain any plaintext information from $E(m_{*})$ without knowing $r_{*}$ and $\alpha$. As $E_Q({\widehat{L}}^{\prime })$ is a ciphertext of the ASPE algorithm, the privacy-preserving totally depends on the security of the ASPE algorithm. As analysed in [26], once the vector dimension d satisfies $d\ge 80$, it is generally very difficult for an attacker to successfully attack the ASPE algorithm. Therefore, under the parameter setting in Section 4.1, the location can be protected from disclosing. In other words, fog nodes can not obtain any plaintext information from the request $(E(m_{*}),E_Q({\widehat{L}}^{\prime }))$. In addition, even if the value of scalar-product (see Formula (6)) has been obtained, the fog node $i{d}_j$ cannot get the location, since a large random number $\beta$ has been applied to confuse the real scalar-product value. Note that fog nodes do not collude with the LBS provider in this paper, so they will not directly forward users’ encrypted requests to the LBS provider, thereby, the LBS provider will not obtain users’ privacy. Consequently, the privacy-preserving of mobile users can be achieved.

The privacy preservation of the LBS provider: Under the aforementioned scheme, the LBS provider would encrypt all LBS data before outsourcing. Thus, fog nodes can only obtain the encrypted LBS items. Similarly, the fog node $i{d}_j$ can not obtain any plaintext information from the stored content information $E(m_i)(i=1,2,\dots ,k_j)$ based on the CDH and DL problems. In addition, according to properties of the ASPE algorithm (Formulas (3) and (4)), even though the fog node $i{d}_j$ manages $k_j$ encrypted LBS items, it can not obtain any plaintext information about locations. Conceivably, the privacy preservation of the LBS provider can be achieved.

6. Performance Analysis

In this section, we evaluate our proposed FGPQ scheme in terms of the communication overhead, computational costs and latency, respectively. Moreover, we give a comparison with the EPLQ scheme [18] and EPQ scheme [19].

6.1. Computational Costs

In our FGPQ scheme, the LBS provider needs to encrypt k LBS data, where each service content $m_i$ is encrypted by the bilinear pairing technology, i.e., $e(g^{\alpha h(m_i)r_i},g^{r_i})$, and the correponding location $(X_i,Y_i)$ is encrypted by the tuple encryption function $E_T$ of the ASPE algorithm. According to the empirical evaluation in [26,30], the computational costs for the ASPE algorithm are microseconds, which are considered negligible compared to the exponentiation and pairing operations. Hence, the computational costs of the LBS provider are $2k$ exponentiations in $\mathbb{G}$. When a mobile user wants to request the LBS searching, he or she encrypts the query request $(m_{*},(X_{*},Y_{*}),T_{*})$, which costs two exponentiations in $\mathbb{G}$. After receiving the encrypted request, for each encrypted LBS item $(E(m_i),E_T(\widehat{W^{(i)}}))$, where $i=1,2,\dots ,k_j$, the fog node $i{d}_j$ first computes the Formula (6) to select the LBS items meeting the spatial range. After retrieving f LBS items matched the spatial range, it verifies the Equation (7), where each verification requires two pairing operations. Since the computational costs of the ASPE algorithm are negligible, the computational costs of the fog node $i{d}_j$ are $2f$ pairing operations. Finally, the total computational costs for the LBS provider, a mobile user and a fog node $i{d}_j$ will be $2k$ exponentiations in $\mathbb{G}$, two exponentiations in $\mathbb{G}$ and $2f$ pairing operations, respectively, in the proposed FGPQ scheme.

In the EPLQ scheme [18], to generate a query, a mobile user needs to encode the location and the searching spatial range into two N-dimensional vectors, and then encrypt these two vectors as $K_i=(g^{u_{i,1}^{{}^{″}}},g^{u_{i,2}^{{}^{″}}},\dots ,g^{u_{i,N}^{{}^{″}}},e{(g,g)}^{h_i})$, where $(u_{i,1}^{{}^{″}},u_{i,2}^{{}^{″}},\dots ,u_{i,N}^{{}^{″}})$ is the encoded vector. Hence, the corresponding computational costs are about $2N$ exponentiations in $\mathbb{G}$. In order to ensure the privacy, the LBS provider also needs to encode the location of each LBS into a N-dimensional vectors, and then encrypt it as $C_j=(g^{v_{j,1}^{{}^{″}}},g^{v_{j,2}^{{}^{″}}},\dots ,g^{v_{j,N}^{{}^{″}}},e{(g,g)}^{s_j})$, which requires N exponentiations in $\mathbb{G}$ and one exponentiation in ${\mathbb{G}}_T$. For all k LBS items, it totally spends $N*k$ exponentiations in $\mathbb{G}$ and k exponentiations in ${\mathbb{G}}_T$ to complete the encryption. In addition, to assist the cloud in checking the spatial range, the LBS provider still needs to compute ${\tau }_2-{\tau }_1$ values ${\mathrm{\Omega }}_i=Hash(e{(g,g)}^{{(\alpha \times perm(i)+\beta )}^d})$, where $i\in [{\tau }_1,{\tau }_2]$. That is, the computational costs are about $({\tau }_2-{\tau }_1)$ exponentiations in ${\mathbb{G}}_T$. Hence, the total computational costs for the LBS provider are about $N*k$ exponentiations in $\mathbb{G}$ and $k+({\tau }_2-{\tau }_1)$ exponentiations in ${\mathbb{G}}_T$. To determine whether the encrypted LBS items match the given query or not, it requires the cloud to compute $check(K_i,C_j)$, which costs N pairing operations and N multiplications in ${\mathbb{G}}_T$. Note that searching $\widehat{ss}$-tree to find the matched LBS items requires traversing through about $logk+f$ tree nodes with k LBS items and f items matched the spatial range. Therefore, the total computational costs for the cloud are about $(logk+f)N$ pairing operations and $(logk+f)N$ multiplications in ${\mathbb{G}}_T$.

In the EPQ scheme [19], the LBS provider outsources all encrypted LBS items to the cloud, where each location index is encrypted as $l_{s1}=e{(g,g)}^{q_1{x_{s_0}}^2}$, $l_{s2}=e{(g,g)}^{q_1{y_{s_0}}^2}$, $l_{s3}=g^{x_{s_0}}·h^{r_{s_1}}$ and $l_{s4}=g^{x_{s_0}}·h^{r_{s_2}}$. The corresponding computational costs for all k LBS items are about $4k$ exponentiations in $\mathbb{G}$, $2k$ exponentiations in ${\mathbb{G}}_T$ and $2k$ multiplications in $\mathbb{G}$. To request a LBS query, a mobile user generates an encrypted query $(r{q}_1,r{q}_2,r{q}_3,r{q}_4)=(e{(g,g)}^{q_1({x_{s_0}}^2-d^2)},e{(g,g)}^{q_1{y_0}^2},g^{q_1·2x_0},g^{q_1·2y_0})$, which requires two exponentiations in $\mathbb{G}$ and two exponentiations in ${\mathbb{G}}_T$. After receiving the query from the user, the cloud computes the search criteria $T_s$ for each LBS item stored in it, which requires $2k$ pairing operations and $5k$ multiplications in ${\mathbb{G}}_T$.

We present the computational costs comparison of our FGPQ scheme, the EPLQ scheme [18] and the EPQ scheme [19] in

Table 1. Comparison of computational costs.

	Mobile User	LBS Provider	Cloud/Fog Node
EPLQ [18]	$2N·C_e$	$N·k·C_e+(k+{\tau }_2-{\tau }_1)·C_{et}$	$(logk+f)N·(C_p+C_{mt})$
EPQ [19]	$2·(C_e+C_{et})$	$4k·C_e+2k·(C_{et}+C_m)$	$2k·C_p+5k·C_{mt}$
FGPQ	$2·C_e$	$2k·C_e$	$2f·C_p$

, where k and f denote the number of LBS data items and the matched LBS data items, respectively. Obviously, k and f satisfy $f\le k$, and the codeword length N satisfies $N\ge 7$ [18]. Note that $C_e$, $C_{et}$, $C_p$, $C_{mt}$ and $C_m$ denote the computational costs of an exponentiation in $\mathbb{G}$, an exponentiation in ${\mathbb{G}}_T$, a pairing operation, a multiplication in ${\mathbb{G}}_T$ and a multiplication in $\mathbb{G}$, respectively. From the table, it is obvious that the FGPQ scheme largely reduces the computational costs compared to the EPLQ scheme [18] and the EPQ scheme [19]. Moreover, for mobile users, the efficiency of our FGPQ scheme is better than the others. Thus, as declared in [18,19], it is convincing that our FGPQ scheme is more suitable for energy-poor mobile devices.

6.2. Communication Overhead

In our FGPQ scheme, the communication overhead can be divided into two parts: LBS provider-to-fog and user-to-fog. We first discuss the LBS provider-to-fog communication, where the LBS provider delivers all encrypted LBS items to each fog node $i{d}_j(j=1,2,\dots ,n)$. The encrypted LBS item is in the form of ${\{E(m_i),E_T(\widehat{W^{(i)}})\}}_{i=1,2,\dots ,k_j}$ for the fog node $i{d}_j$, and its size should be $(1024+|E_T(\widehat{W^{(i)}})|)k_j$ bits if we choose 512-bit $\mathbb{G}$. As mentioned in [30], each dimension in the ASPE algorithm is a float number (the size of each float number is 32 bits). Thus, the total size of $E_T(\widehat{W^{(i)}})=(\widehat{W_a^{(i)}}{M}_1,\widehat{W_b^{(i)}}{M}_2)$ is 5120 bits if the dimension is 80 (see Section 4.1). Accordingly, the communication overheads for LBS provider-to-fog communication are ${\sum }_{j=1}^n(6144·k_j)$ bits. As mentioned in Section 4.2.2, since all k encrypted LBS items are distributed to n fog nodes, we can obtain ${\sum }_{j=1}^n{k}_j=k$, where $k_j$ denotes the number of fog node $i{d}_j$’s LBS items received from the LBS provider. That is, the value ${\sum }_{j=1}^n(6144·k_j)$ can be implicitly simplified as $(6144·k)$. Next, we consider the user-to-fog communication. Firstly, a mobile user sends an encrypted request $\{E(m_{*}),E_Q({\widehat{L}}^{\prime })\}$ to a fog node, which requires 6144 bits to transmit. Then, this fog node performs the LBS searching and returns the most matched encrypted location $E_T(\widehat{W^{(i)}})$ to this user, which costs 5120 bits. Therefore, the total communication overheads for user-to-fog communication are about 11,264 bits.

In the EPLQ scheme [18], the LBS provider outsources all encrypted LBS items to the cloud. The communication overheads are $(N+1)k·512+k·128+128·({\tau }_2-{\tau }_1)$ bits if the bit length of p, standard symmetric encryption (e.g., AES) and the hash value $hash()$ satisfy $\left|p\right|=512$ bit, $\left|AES\right|=128$ bit and $|hash()|=128$ bit, respectively. To achieve the LBS searching, a mobile user sends two encrypted tokens to the cloud, which requires $2(N+1)·512$ bits. After receiving the LBS searching request, the cloud performs LBS checking to find the LBS items matched the given spatial range. After that, the cloud returns the matched LBS data items to this user. If the number of matched LBS items is f, then the communication overheads are about $f·128$ bits, where each ciphertext of the symmetric encryption is 128 bits. Therefore, the LBS provider-to-cloud communication and the user-to-cloud communication require $(512·(N+1)k+128·k+128\times {10}^8)$ bits and $(1024·(N+1)+128·f)$ bits, respectively.

In the EPQ scheme [19], in order to enjoy the location-based services, a mobile user sends an encrypted LBS query request to the cloud. The encrypted LBS query request is in the form of $(I{D}_{LBS}|\left|E_{LQR}\right|\left|U_i\right|\left|TS\right||Si{g}_i)$, and its size is about 5280 bits if we set $\mid I{D}_{LBS}\left|\right|U_i\left|\right|TS\mid =160$ bits. To provide the better quality of services, the LBS provider outsources all encrypted LBS data to the cloud. Since each outsourced LBS item is in the form of $(I{D}_{LBS}|\left|T_j\right|\left|l_{s_1}\right|\left|l_{s_2}\right|\left|l_{s_3}\right|\left|l_{s_4}\right||E_s)$, the communication overheads for all k LBS items are about $4384·k$ bits. In addition, in order to help the cloud to complete the query in the ciphertexts, the LBS provider also sends the evaluation data set $EDS=\{E{D}_0,E{D}_1,\dots ,E{D}_i,\dots ,E{D}_{10,000,000,000}\}$ to the cloud, where $E{D}_i=H(P{B}^i)$. If the bit length of hash $H()$ is set as $|H()|=128$ bit, then the size of the set $EDS$ is about $128\times {10}^{10}$ bits. Hence, the communication overheads for the LBS provider are about $(4384·k+128\times {10}^{10})$ bits. After finding f matched LBS items, the cloud returns the query result $(E_{r{q}_1}(TRL)|\left|I{D}_{CS}\right|\left|TS\right||Si{g}_{CS})$ to the user, which requires $(128·f+1184)$ bits to transmit. Hence, the total communication overheads between a mobile user and the cloud are about $(128·f+6464)$ bits.

We present the communication overhead comparison of our FGPQ scheme, the EPLQ scheme [18] and the EPQ scheme [19] in

Table 2. Comparison of communication overhead (Bits).

	LBS Provider-to-Cloud (Fog Nodes)	User-to-Cloud (A Fog Node)
EPLQ [18]	$512·(N+1)k+128·k+128·({\tau }_2-{\tau }_1)$	$1024·(N+1)+128·f$
EPQ [19]	$4384·k+128\times {10}^{10}$	$128·f+6464$
FGPQ	$6144·k$	11264

, where “LBS provider-to-cloud (fog nodes)” and “ User-to-cloud (a fog node) ” denote the communication between the LBS provider and the cloud (or fog nodes) and the communication between a mobile user and the cloud (or a fog node), respectively. As described in the EPLQ scheme [18], the codeword length N satisfies $N\ge 7$, since the original dimension of the location vector is 7. Therefore, from Table 2, we can know that the communication overheads between the LBS provider and the cloud (or fog nodes) in these three schemes are about the same. However, in the user-to-cloud (a fog node) communication, the communication overhead of our FGPQ scheme is much less than that of other two schemes, as the number of LBS items matched the given spatial range is usually more than a few dozen, i.e., f is more than a few dozen, and f is likely to increase with k or the searching spatial range increasing.

6.3. Latency

In order to demonstrate the advantage of fog computing, this section discusses the latency of LBS searching, and gives a comparison with cloud computing-based schemes, e.g., the schemes proposed in [18,19]. In general, the service latency is a time interval from a user sending a request to receiving the feedback, which contains the online computing delay and communication delay. In our FGPQ scheme, since fog nodes are local, the communication delay between mobile users and fog nodes can be neglected, and thus the latency absolutely depends on the online computing time in fog nodes. As shown in Table 1, the online computing time of the fog node $i{d}_j$ is $2f·C_p$ seconds, that is, the latency of our FGPQ scheme is $2f·C_p$ seconds. Alternatively, if the cloud computing system is adopted, the latency depends on the online computing time in the cloud and the communication delay between users and the cloud. Specifically, in the EPLQ scheme [18], the online computing time in the cloud is $(logk+f)·N·(C_p+C_{mt})$ seconds (See Table 1). In addition, based on Table 2, the communication overheads between each user and a fog node are $128·f+1024(N+1)$ bits. Therefore, if l mobile users send requests to the cloud at the same time, the total network traffic is about $(128·f+1024(N+1))·l$ bits. As analysed in [34], the communication delay for uploading 10 MB data takes about 28 s, thereby, the communication delay of the EPLQ scheme [18] is about $(128·f+1024(N+1))·l÷8388608$ s (1 MB =8,388,608 bits). Finally, the latency of the EPLQ scheme [18] is about $((logk+f)·N·(C_p+C_{mt})+(128·f+1024(N+1))·l÷8388608)$ s. Similarity, based on Table 1 and Table 2, the latency of the EPQ scheme [19] is about $(2k·C_p+5k·C_{mt}+(128f+6464)l÷8388608)$ s.

Furthermore, we conduct the experiments with the pairing-based cryptograph library (PBC) [35] and the GNU multiple precision arithmetic library (GMP) [36] running on a $2.6$ GHz-processor computer to study the latency. To this end, we set the security parameter $\left|\kappa \right|=512$ bits. Furthermore, similar to [18], we set $N=37$. With the exact operation costs, we depict the variation of computational costs in terms of the number of LBS items k, the number of matched LBS items and the number of mobile uses l who request LBS searching at the same time, in Figure 2. From the figure, it is obvious that our FGPQ scheme largely reduces the latency compared to the EPLQ scheme [18] and EPQ scheme [19]. In particular, in Figure 2a, our FGPQ scheme remains unchanged when k increases. This is because our FGPQ scheme takes advantage of a very efficient ASPE algorithm, and uses this algorithm to originally select f encrypted LBS items matched the spatial range. In addition, in practice, the number of LBS data stored in each fog node is far less than the total LBS data (i.e., $k_j\ll k$). Therefore, the latency of our FGPQ scheme only depends on the time verifying whether f LBS data satisfy the searching content, i.e., $2f$ pairing operations. In Figure 2c, our FGPQ scheme still remains unchanged when l increases. The main reason is that the communication delay between mobile users and local fog nodes can be neglected, and the computing operations for l users can be performed in parallel. According to Figure 2b, the latency of these three schemes increase with f increasing, but our scheme increase significantly slower.

From the above analyses, our FGPQ scheme is indeed efficient in terms of computational and communication overheads, and also low-latency in fog computing-enhanced system, which is suitable for the real-time LBS searching for mobile users.

7. Conclusions

Fog computing-enhanced location-based services have been widely developed in the Internet of Things. In this paper, we have proposed a fine-grained and privacy-preserving query scheme in fog computing-enhanced location-based services. In our proposed scheme, mobile users can obtain the fine-grained searching result satisfying not only the given spatial range but also the searching content. Detailed privacy analysis shows that our proposed scheme indeed achieves the privacy preservation for the LBS provider and mobile users. In addition, extensive performance analyses and experiments demonstrate that our proposed scheme can significantly reduce computational and communication overheads and ensure low-latency, which outperforms existing state-of-the art schemes. Hence, our proposed scheme is more suitable for real-time LBS searching. In future work, we will consider a stronger adversarial model and design new solutions under the new model. In order to achieve more fine-grained LBS queries, we will consider the extensibility, such as searching the closest restaurant that opens now and satisfies the five-star service score or has good sales volume, which makes the LBS query be more practical.