## 4 ROLQ-TEE Scheme
### Detailed Construction  
Our ROLQ-TEE scheme includes the following eight algorithms: _Setup_, _KeyGen_, _Enc_, _Build_, _GenToken_, _OptLocQue_, _Dec_, and _KeyFresh_. We first summarize important notations used in ROLQ-TEE, as shown in Table 1. Next, we present our construction as follows:  
\(Setup(1^{\lambda})\)\(\rightarrow\)\((msk,mpk)\). The \(Setup\) algorithm is run by the \(\mathcal{DO}\). It takes as input a security parameter \(\lambda\). It outputs the master secret key \(msk\) and system master public key \(mpk\). 1. The \(\mathcal{DO}\) chooses a bilinear map \(e:\mathbb{G}\times\mathbb{G}\)\(\rightarrow\)\(\mathbb{G}_{\mathbb{T}}\), where \(\mathbb{G}\) and \(\mathbb{G}_{\mathbb{T}}\) are two cyclic groups with order \(q\). Then, the \(\mathcal{DO}\) randomly chooses a generator \(g\) of \(\mathbb{G}\) and a generator \(g_{t}\) of \(\mathbb{G}_{\mathbb{T}}\), respectively. After that, the \(\mathcal{DO}\) chooses two different collision-resistant hash functions, \(H_{1}\):\(\{0,1\}^{*}\)\(\rightarrow\)\(\mathbb{G}\) and \(H_{2}\):\(\{0,1\}^{*}\)\(\rightarrow\)\(\mathbb{G}\), randomly. Additionally, the \(\mathcal{DO}\) chooses an pseudo-random function \(F\). 2. The \(\mathcal{DO}\) chooses some random values \(\alpha,\alpha_{\mu}\in Z_{q}^{*}\), and computes \(h=g^{\alpha}\) and \(h_{\mu}=g^{\alpha_{\mu}}\), \(1\leq\mu\leq n\). 3. The \(\mathcal{DO}\) executes remote attestation with the TEE of the \(\mathcal{CSP}\) to generate the session key \(K_{s}\). Meanwhile, both parties establish a secure channel. 4. Finally, the \(\mathcal{DO}\) publishes \(mpk=(\mathbb{G},\mathbb{G}_{\mathbb{T}},e,g,q\), \(h_{\mu},h,H_{1},H_{2})\) as the system parameters, and sends the encrypted \(msk=\{\alpha,\alpha_{\mu}\}\) to the TEE through the secure channel. \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Descriptions** \\ \hline \(msk\) & System master secret key \\ \(mpk\) & System master public key \\ \(sk_{\mu}\) & The query key of \(\mathcal{DU}_{\mu}\) \\ \(sk_{\mathcal{DO}}\) & The storage key of \(\mathcal{DO}\) \\ \(TL\) & The timestamp list \\ \(RL\) & The revocation list \\ \(UL\) & The data user list \\ \(U_{\mathcal{DO}}\) & The customer sets of \(\mathcal{DO}\) \\ \(U_{\mu}\) & The customer sets of \(\mu\)-th \(\mathcal{DU}_{\mu}\) \\ \(L_{\mathcal{DO}}\) & The location information set of \(\mathcal{DO}\) \\ \(n,s\) & The total number of users and existing facilities \\ \(n_{\mathcal{DO}}\) & The total number of customers of \(\mathcal{DO}\) \\ \(n_{\mu}\) & The total number of customers of the \(\mu\)-th \(\mathcal{DU}_{\mu}\) \\ \(n_{I}\) & The total number of data in intersection \(I\) \\ \(res\) & The query result of the optimal location query \\ \(x_{i}\) & The \(i\)-th customer data of \(\mathcal{DO}\) \\ \(y_{\mu,j}\) & The \(j\)-th customer data of the \(\mathcal{DU}_{\mu}\) \\ \(U_{I}\) & The intersection set of the customer of \(\mathcal{DO}\) and \(\mathcal{DU}_{\mu}\) \\ \(dist(a,b)\) & A distance function that computes the euclidean \\ distance between any two objects \(a\) and \(b\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. * \(Enc(U_{\mathcal{DO}},msk,iv,add,K_{s}){\rightarrow}(\mathcal{C},\mathcal{C}_{msk}, tag,tag_{msk})\). The \(Enc\) algorithm is run by the \(\mathcal{DO}\). It takes as input the data \(U_{\mathcal{DO}}=\{M_{i}=x_{i}||l_{i}\}\), the master system key \(msk\), the initial vector \(iv=\{iv_{0},iv_{1},\ldots,iv_{n_{\mathcal{DO}}}\}\), the additional authentication data \(add=\{add_{0},add_{1},\ldots,add_{n_{\mathcal{DO}}}\}\), and the session key \(K_{s}\). It outputs the ciphertexts \(\mathcal{C}=\{\mathcal{C}_{i}\}\) and \(\mathcal{C}_{msk}\), and the encrypted tags \(tag=\{tag_{i}\}\) and \(tag_{msk}\), where \(1\leq i\leq n_{\mathcal{DO}}\). * \(KeyGen(\mathcal{C}_{msk},K_{s},mpk){\rightarrow}(sk_{\mu},sk_{\mathcal{DO}}, TL,RL,UL)\). The KeyGen algorithm is run by the TEE. It takes as input the encrypted master secret key \(\mathcal{C}_{msk}\) and the master public key \(mpk\).