## 6 Performance Analysis
### 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 \(id_{j}\)\((j=1,2,\ldots,n)\). The encrypted LBS item is in the form of \(\{E(m_{i}),E_{T}(\widehat{W^{(i)}})\}_{i=1,2,\ldots,k_{j}}\) for the fog node \(id_{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^{(i)}_{a}}M_{1},\widehat{W^{(i)}_{b}}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\cdot 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 \(id_{j}\)'s LBS items received from the LBS provider. That is, the value \(\sum_{j=1}^{n}(6144\cdot k_{j})\) can be implicitly simplified as \((6144\cdot 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\cdot 512+k\cdot 128+128\cdot(\tau_{2}-\tau_{1})\) bits if the bit length of \(p\), standard symmetric encryption (e.g., AES) and the hash value \(hash()\) satisfy \(|p|=512\) bit, \(|AES|=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)\cdot 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\cdot 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\cdot(N+1)k+128\cdot k+128\times 10^{8})\) bits and \((1024\cdot(N+1)+128\cdot f)\) bits, respectively. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Mobile User** & **LBS Provider** & **Cloud/Fog Node** \\ \hline
**EPLQ**[18] & \(2N\cdot C_{e}\) & \(N\cdot k\cdot C_{e}+(k+\tau_{2}-\tau_{1})\cdot C_{et}\) & \((\log k+f)N\cdot(C_{p}+C_{mt})\) \\
**EPQ**[19] & \(2\cdot(C_{e}+C_{et})\) & \(4k\cdot C_{e}+2k\cdot(C_{et}+C_{m})\) & \(2k\cdot C_{p}+5k\cdot C_{mt}\) \\
**FGPQ** & \(2\cdot C_{e}\) & \(2k\cdot C_{e}\) & \(2f\cdot C_{p}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of computational costs. 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 \((ID_{LBS}||E_{LQR}||U_{i}||TS||Sig_{i})\), and its size is about 5280 bits if we set \(|\ ID_{LBS}||U_{i}||TS\ |=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 \((ID_{LBS}||T_{j}||U_{s_{1}}||I_{s_{2}}||I_{s_{3}}||I_{s_{4}}||E_{s})\), the communication overheads for all \(k\) LBS items are about \(4384\cdot k\) bits.