## 4 ROLQ-TEE Scheme
### System Architecture  
As shown in Figure 3, we consider a multi-parties scenario. The ROLQ-TEE scheme consists of three entities, namely a data owner (\(\mathcal{DO}\)), data users (\(\mathcal{DU}\)), and a cloud service provider (\(\mathcal{CSP}\)) that supports TEE, where \(\mathcal{DU}=\{\mathcal{DU}_{1},\ldots,\mathcal{DU}_{n}\}\). \(\mathcal{DO}\) has a private customer set \(U_{\mathcal{DO}}=\{(x_{1},l_{1}),\ldots,(x_{n_{\mathcal{DO}}},l_{n_{\mathcal{ DO}}})\}\), where \(x_{i}\) is the \(i\)th unique customer identity of the \(\mathcal{DO}\) and \(l_{i}\) is the location information of \(x_{i}\), \(1\leq i\leq n_{\mathcal{DO}}\). In fact, \(l_{i}\) can be an expression of a point in any coordinate system, for example, \(l_{i}=(u_{i},v_{i})\) in the Cartesian coordinate system or \(l_{i}=(ln_{i},lat_{i})\) in the geographic coordinate system. Each \(\mathcal{DU}_{\mu}\) has a private customer list \(U_{\mu}=\{y_{\mu,1},\ldots,y_{\mu,n_{\mu}}\}\), where \(y_{\mu,j}\) is the \(j\)th unique customer identity of the \(\mathcal{DU}_{\mu}\), \(1\leq\mu\leq n\), and \(1\leq j\leq n_{\mu}\). Additionally, each \(\mathcal{DU}_{\mu}\) has a candidate list of facilities \(\mathcal{F}_{\mu}=\{f_{1},\ldots,f_{s}\}\), where \(f_{\xi}\) also represents the expression of a point in any coordinate system, \(1\leq\xi\leq s\). Their respective tasks and system flows are described as follows:  
* Data owner (\(\mathcal{DO}\)): The data owner is mainly responsible for system setup, data encryption and ciphertext uploading. In addition, the \(\mathcal{DO}\) establishes the secure channel through remote attestation with the TEE of the \(\mathcal{CSP}\) and generates the session key to transfer the secret key and data.
* Cloud service provider (\(\mathcal{CSP}\)): This is mainly divided into two areas: one is the TEE area, and the other is the storage area. The TEE is mainly responsible for query key  
Figure 2: Intel SGX features.  
generation, map table construction, optimal location query, and query key refresh. The storage area is mainly responsible for storing encrypted data.
* Data users (\(\mathcal{DU}\)): The \(\mathcal{DU}_{\mu}\) is mainly responsible for providing a candidate set \(\mathcal{F}_{\mu}=\{f_{\xi}\}_{1}^{s}\) and generating query requests \(\mathcal{Q}\) for the candidate set. Additionally, the \(\mathcal{DU}_{\mu}\) is also responsible for decrypting the optimal location query results.  
As shown in Figure 3, the \(\mathcal{DO}\) establishes a secure channel with the TEE of the \(\mathcal{CSP}\) through remote attestation in advance and generates the session key \(K_{s}\). Next, the \(\mathcal{DO}\) executes the system setup to generate master secret key \(msk\) and master public parameters \(mpk\) in step 1. In step 2, the \(\mathcal{DO}\) uploads encrypted data to the \(\mathcal{CSP}\). After that, the TEE generates the storage key \(sk_{\mathcal{DO}}\) and the query keys \(sk_{\mu}\) for the \(\mathcal{DO}\) and all \(\mathcal{DU}_{\mu}\) in step 3. In step 4, the TEE performs query key distribution for all \(\mathcal{DU}_{\mu}\). In step 5, the TEE constructs the map table and re-encrypts the location data. In step 6, the \(\mathcal{DU}_{\mu}\) generates optimal location query requests and sends them to the TEE. In step 7, the TEE executes the optimal location query algorithm to obtain a query result \(res\). The TEE sends the encrypted query results \(C_{res}\) to the \(\mathcal{DU}_{\mu}\) in step 8. In step 9, the \(\mathcal{DU}_{\mu}\) performs the Dec algorithm to obtain the query result \(res\). The TEE performs a query key refresh operation to revoke the query permissions of the user in the revocation list, and updates user list \(UL\), revocation list \(RL\), time list \(TL\), and the query keys of the unrevoked users in step 10.