## 6 Performance Analysis
### 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^{\mathit{a}{\mathit{k}}(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,\ldots,k_{j}\), the fog node \(id_{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 \(id_{j}\) are \(2f\) pairing operations. Finally, the total computational costs for the LBS provider, a mobile user and a fog node \(id_{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^{\mathit{u}_{i1}},g^{\mathit{u}_{i2}},\ldots,g^{\mathit{u}_{iN}},e(g,g)^{\mathit{h}_{i}})\), where \((u_{i1}^{\mathit{u}},u_{i2}^{\mathit{u}},\ldots,u_{i,N}^{\mathit{u}})\) 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^{\mathit{u}_{j1}^{\mathit{u}_{j2}}},g^{\mathit{u}_{j2}^{\mathit{u}} },\ldots,g^{\mathit{u}_{jN}^{\mathit{u}_{jN}}},e(g,g)^{\mathit{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 \(\Omega_{i}=\mathit{Hash}(e(g,g)^{(\alpha\times perm(i)+\beta)^{4}})\), 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 \(\mathit{check}(K_{i},C_{j})\), which costs \(N\) pairing operations and \(N\) multiplications in \(\mathbb{G}_{T}\). Note that searching \(\mathit{\hat{s}}\)s-tree to find the matched LBS items requires traversing through about \(\log k+f\) tree nodes with \(k\) LBS items and \(f\) items matched the spatial range. Therefore, the total computational costs for the cloud are about \((\log k+f)N\) pairing operations and \((\log k+f)N\) multiplications in \(\mathbb{G}_{T}\).