## 4 Our Construction
### Scheme Construction
\begin{table}
\begin{tabular}{c c c c c c} \hline \multirow{2}{*}{**Schemes**} & \multicolumn{2}{c}{**Computation**} & \multicolumn{2}{c}{**Communication**} & \multirow{2}{*}{**Backward Privacy Type**} \\ \cline{2-2} \cline{4-5}  & **Search** & & & **Update** & **Search** & **Update** \\ \hline \multirow{2}{*}{Fort} & \(\mathcal{O}(n_{w}+\Sigma_{w}d_{w})\) & \(\mathcal{O}\Big{(}\log^{2}N\Big{)}\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & I \\ \hline \multirow{2}{*}{Maiden} & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & I \\ \hline \multirow{2}{*}{Bunker-B} & \(\mathcal{O}(a_{w})\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & II \\ \hline \multirow{2}{*}{SGX-SE1} & \(\mathcal{O}(n_{w}+d)\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & II \\ \hline \multirow{2}{*}{SGX-SE2} & \(\mathcal{O}(n_{w}+\
u_{d})\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & II \\ \hline \multirow{2}{*}{Proposed} & \(\mathcal{O}(n_{w}+d)\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & II \\ \hline \multirow{2}{*}{Bunker-A} & \(\mathcal{O}(a_{w})\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(n_{w})\) & \(\mathcal{O}(1)\) & III \\ \hline \end{tabular}

* \(N\): the total number of keyword/document pairs; \(W\): the total number of keywords; \(a_{w}\), \(n_{w}\), \(d\): the total number of entries (including all updates) performed on \(w\), the number of non-deleted documents containing \(w\), and the number of deleted documents, respectively; \(\
u_{d}\): the vector of a bloom filter to check the membership of \(\#d\) documents.

\end{table} 
Table 4: Comparison of SGX-based DSSE schemes. \begin{table}
\begin{tabular}{c c c} \hline \multirow{2}{*}{**Schemes**} & \multicolumn{2}{c}{**Storage**} \\ \cline{2-3}  & **Client** & **Enclave** \\ \hline \multirow{2}{*}{Fort} & \(\mathcal{O}(W\log D)\) & - \\ \hline \multirow{2}{*}{Maiden} & \(\mathcal{O}(W\log D+a_{w}+N\) & - \\ \hline \multirow{2}{*}{Bunker-B} & \(\mathcal{O}(W\log D)\) & - \\ \hline \multirow{2}{*}{SGX-SE1} & - & \(\mathcal{O}(W\log D+d)\) \\ \hline \multirow{2}{*}{SGX-SE2} & - & \(\mathcal{O}\Big{(}W\log D+|\widetilde{b}f|\Big{)}\) \\ \hline \multirow{2}{*}{Proposed} & - & \(\mathcal{O}(W\log D+d+|K|)\) \\ \hline \multirow{2}{*}{Bunker-A} & \(\mathcal{O}(W\log D)\) & - \\ \hline \end{tabular}

* \(N\): the total number of keyword/document pairs; \(D\): the total number of documents; \(W\): the total number of keywords; \(a_{w}\): the total number of entries (including all updates) performed on \(w\); \(d\): the number of deleted documents; \(\bar{f}\): the configurable bloom filter vector; \(K\): the number of frequently searched documents cached in \(\bar{F}D\).

\end{table} 
Table 5: Storage comparison. case, demonstrating the proposed scheme outperforms SGX-SE1 slightly. Compared to Bunker-B, both the proposed scheme and SGX-SE1 show significantly higher efficiency as the number of inserted documents increases. For deletion, we evaluate the runtime by varying the portion of deletion from \(1\times 10^{5}\) documents: 25%, 50%, and 75%. As shown in Figure 2(b), Bunker-B takes 2065 ms, 3907 ms, and 5885 ms to delete 25%, 50%, and 75% of documents, respectively. SGX-SE1 takes 164 ms, 319 ms, and 470 ms, and the proposed scheme takes 169 ms, 346 ms, and 480 ms for each respective case. It shows the proposed scheme and SGX-SE1 have almost the same computational overhead while significantly outperforming Bunker-B. This is mainly because the proposed scheme and SGX-SE1 implement the deletion process by simply inserting the _id_s of the documents to be deleted into a list, but Bunker-B actually deletes the documents from the EDB as in the insertion process. #### 6.2.2 Search Time

Now, we evaluate the search time or query delay of the proposed scheme. Because the proposed scheme caches frequently searched documents \(FD\) within the enclave for obfuscation and faster retrieval, it is important to find the optimal size of \(FD\).