## 4 Proposed FGPQ Scheme
### System Initialization  
The LBS provider initializes the system by following steps:  
1. 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\}^{*}\rightarrow\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},\ldots,\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},\ldots,\omega_{d^{\prime}})\) to mobile users through the secure channel.
2. 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})),\ldots,(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,\ldots,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^{ah(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)}}[j]=r_{j}\) (\(r_{j}\) is a random number), and \(\widehat{W^{(i)}}[d^{\prime}]=\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}, \ldots,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}(\cdot)\) (the Equation (1)), that is, \[E_{T}(\widehat{W^{(i)}})=(\widehat{W^{(i)}_{a}}\cdot M_{1},\,\widehat{W^{(i)}_ {b}}\cdot 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,\ldots,k\), to appropriate fog nodes.