## 4 ROLQ-TEE Scheme
### Detailed Construction
The communication overhead on the data user side is significantly greater than that of the Yilmaz [9] scheme, mainly because the client in the [9] scheme is both the data owner \(\mathcal{DO}\) and the data user \(\mathcal{DU}_{\mu}\), and the data user \(\mathcal{DU}_{\mu}\) in our scheme needs to send not only requests but also customer identifiers. In addition, regardless of how the number of candidate facilities \(s\) and the amount of data owner data \(n_{\mathcal{DO}}\) increase, the communication overhead of the cloud server provider in our scheme is almost constant. Similarly, this also means that the computational overhead of the data owner is constant. ### Efficiency

We implemented this scheme in C/C++ on a workstation that supports Intel SGX. All experiments were performed on a 64-bit Ubuntu 22.04.3 LTS machine with a 2.9 \(\times\) 16 GHz Intel Core i7 processor and 32 GB of RAM. All distances were calculated using the trusted execution environment in the Euclidean metric. In our experiments, we utilized real datasets [36] comprising 573,703 check-ins from Tokyo. The \(x\) and \(y\) coordinates were scaled to integer values ranging from 1 to 10,000. As the total number of users in the dataset is fewer than 5000, we treated each check-in location as the location of an individual data user. Thus, we set \(n_{\mathcal{MO}}\) = 573,703 in the Tokyo dataset. We randomly selected 60 percent of the data in the above dataset and some synthetic data as a dataset for a data user \(\mathcal{DU}_{\mu}\). For existing facilities, we also selected 1 \begin{table}
\begin{tabular}{c c c c} \hline \hline \multirow{2}{*}{**Schemes**} & \multicolumn{3}{c}{**Communication**} \\ \cline{2-4}  & \(\mathbf{C(\mathcal{DO})}\) & \(\mathcal{DU}\) & \(\mathbf{S}\) \\ \hline RNNQ/S [9] & \(s(log_{2}q+log_{2}N)\) & / & \(log_{2}N(n_{\mathcal{DO}}+2s)\) \\ AVGQ/S [9] & \(s(log_{2}q+log_{2}N)\) & / & \(log_{2}N(n_{\mathcal{DO}}+2s)\) \\ MAXQ/S [9] & \(s(log_{2}q+log_{2}N)\) & / & \(log_{2}N(n_{\mathcal{DO}}+2s)\) \\ \hline RNNQ/C [9] & \(s\cdot log_{2}q+n_{\mu}\cdot log_{2}N\) & / & \(s\cdot log_{2}N\) \\ AVGQ/C [9] & \(s\cdot log_{2}q+n_{\mu}\cdot log_{2}N\) & / & \(s\cdot log_{2}N\) \\ MAXQ/C [9] & \(s\cdot log_{2}q+n_{\mu}\cdot log_{2}N\) & / & \(s\cdot log_{2}N\) \\ \hline RNNQ & \(2n_{\mathcal{DO}}\cdot log_{2}q\) & \((s+1)|\mathcal{G}_{\mathbb{T}}|+2(s+1)|\mathbb{G}|\) & \(|\mathcal{G}_{\mathbb{T}}|+2|\mathbb{G}|\) \\ AVGQ & \(2n_{\mathcal{DO}}\cdot log_{2}q\) & \((s+1)|\mathcal{G}_{\mathbb{T}}|+2(s+1)|\mathbb{G}|\) & \(|\mathcal{G}_{\mathbb{T}}|+2|\mathbb{G}|\) \\ MAXQ & \(2n_{\mathcal{DO}}\cdot log_{2}q\) & \((s+1)|\mathcal{G}_{\mathbb{T}}|+2(s+1)|\mathbb{G}|\) & \(|\mathcal{G}_{\mathbb{T}}|+2|\mathbb{G}|\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Communication overhead compared with previous work. We assume that \(log_{2}q\) represents the bit size of the elements on \(Z_{q}\), \(log_{2}N\) represents the bit size of the elements on \(Z_{N}\), \(|\mathcal{G}_{\mathbb{T}}|\) represents the bit size of the element on the group \(\mathbb{G}_{\mathbb{T}}\) with order \(q\), and \(|\mathbb{G}|\) represents the bit size of the element on the group \(\mathbb{G}\) with order \(q\), where \(N=pq\) and \(p\) and \(q\) are large prime numbers of the same size. \begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{**Schemes**} & \multicolumn{3}{c}{**Memory Usage**} \\ \cline{2-3}  & \(\mathbf{n_{I}=10,000,000}\) & \(\mathbf{s=100}\) \\ \hline
[9] & 250 MB & 25 KB \\ ROLQ-TEE & 28.61 MB & 29.3 KB \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Memory usage compared with previous work. percent of the location data in the Tokyo dataset as the location of existing facilities. For synthetic datasets, the \(x\) and \(y\) coordinates of the user locations and facility locations were randomly generated as integer values ranging from 1 to \(maxvalue=10,000\).