## 4 ROLQ-TEE Scheme
### Detailed Construction
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Schemes**} & \multicolumn{2}{c}{**Query Computation Complexity**} & \multicolumn{3}{c}{**Storage**} & \multirow{2}{*}{**RNN**} & \multirow{2}{*}{**Revocation**} & \multirow{2}{*}{**TEE**} \\ \cline{2-2} \cline{5-8}  & **S(TEE)** & & & & & & & \\ \hline \multirow{3}{*}{RNNQ/S [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \((n_{\mu}\cdot s)\)Mu & \multirow{3}{*}{\((n_{\mu}\cdot s)\)Mu} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{HOO}})\)} & \multirow{3}{*}{\(\check{\mathcal{V}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(\hat{n}\cdot s\)(2E+Mu) & \(s\)(2E+Mu) & & & & & & \\  & \(s\)(Div+E+Mu) & & & & & & & \\ \hline \multirow{3}{*}{AVGQ/S [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \(2n_{\mu}\cdot\)Mu & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{DO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(2\hat{n}\)(2E+Mu) & \(2\)(2E+Mu) & \(1\) Div & & & & & \\ \hline \multirow{3}{*}{MAXQ/S [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \(w\cdot(n_{\mu}-1)\)Mu & \multirow{3}{*}{\(w\cdot\)E} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{DO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(\hat{n}\cdot w\)(2E+Mu) & \(w\cdot\)E & & & & & \\  & \(w\)(Div+E+Mu) & & & & & & \\ \hline \multirow{3}{*}{RNNQ/C [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \multirow{3}{*}{\(s\)(2E+Mu)} & \multirow{3}{*}{\(s\)(Div+E+Mu)} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{HOO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \((n_{\mathcal{DO}}+s)\)Mu & & & & & & \\ \hline \multirow{3}{*}{AVGQ/C [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \(2\)(Div+E+Mu) & \multirow{3}{*}{\(1\) Div} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{DO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(2\)(2E+Mu)+2\(n_{\mathcal{DO}}\cdot\)Mu & & & & & & \\  & \(n_{\mathcal{MO}}\cdot\)E & & & & & & \\ \hline \multirow{3}{*}{MAXQ/C [9]} & \((n_{\mathcal{DO}}\cdot s)dist\) & \((w\cdot q)\)(Div+E+Mu) & \multirow{3}{*}{\(O(n_{\mathcal{HO}}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{HOO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(w\cdot\)E \(\leq w\)(2E+Mu) & & & & & & \\ \hline \multirow{3}{*}{RNNQ} & \((n_{I}\cdot s)dist\) & \(2\)(3E+P+2H+Mu) & \multirow{3}{*}{\(O(1)\)} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{HOO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(\hat{n}_{I}\)-Dec & \(2\)P+Mu+Div & & & & & \\  & \(5\)P+3 Mu+2 Div+3E+2H & & & & & & \\ \hline \multirow{3}{*}{AVGQ} & \((n_{I}\cdot s)dist\)+\(s\)Div & \(2\)(3E+P+2H+Mu) & \multirow{3}{*}{\(O(1)\)} & \multirow{3}{*}{\(O(n_{\mu}+s)\)} & \multirow{3}{*}{\(O(n_{\mathcal{DO}})\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} & \multirow{3}{*}{\(\check{\mathcal{X}}\)} \\  & \(n_{I}\)-Dec & \(2\)

### Communication

In this section, the communication overhead of these schemes can be found in Table 4. This table describes the communication overhead of the entity in the system model, which mainly considers the transmitted ciphertext, the query request, and the query result. The keys have little effect on the communication overhead and are not considered for the time being. Yilmaz [9] implemented two protocols, one based on client query protocol and the other based on server query. As can be seen in Table 4, the communication overhead of our scheme on both the data owner side and the cloud server provider side is smaller than that of Yilmaz's two protocols.