## 4 Our Construction
### Scheme Construction
Figure 3(a) shows the search time of the proposed scheme with various sizes of \(FD\). The search time decreases as the number of documents in \(FD\) increases up to 200; but, when more than 250 documents are stored, the search time rather increases. We observed that this is mainly due to the limitation of the enclave memory, which triggers the paging mechanism more frequently to process the search query when it caches more than 250 documents. With the synthetic data with \(1\times 10^{5}\) documents, we set the optimal size of \(FD\) as 200 which shows the average search time of 346 \(\upmu\)s.

Next, with the optimal size of \(|FD|=200\), we compare the search time of the proposed scheme with those of Bunker-B and SGX-SE1. Figure 3(b) illustrates the search time when inserting \(1\times 10^{5}\) documents and deleting 50% of the documents. In the experiment, we select the top 20 frequent keywords to perform the _Search_ algorithm. For the top-20 frequent keywords, Bunker-B takes on average 9434 \(\upmu\)s to query, SGX-SE1 takes 203 \(\upmu\)s, and the proposed scheme takes 348 \(\upmu\)s. Because Bunker-B requires documents to be re-encrypted, it has a larger computational overhead of which computation complexity is \(\mathcal{O}(a_{w})\). The proposed scheme requires on average 9086 \(\upmu\)s less search time (27\(\times\) faster) than Bunker-B, while guaranteeing a similar level of security, on average 140 \(\upmu\)s more search time (1.7\(\times\) slower) than SGX-SE1 due to the extra computations required to obfuscate access patterns on \(M_{I}\) and \(R\) while providing higher security. #### 6.2.3 Storage Overhead

We can consider three storage types: client, server, and enclave. Among them, the server storage is used to store all of the data for data retrieval such as EDB, encrypted indices, and so on. Because it is a commonly required storage overhead in all of the schemes,

Figure 3: Total time for insertion/deletion. (**a**) Insertion. (**b**) Deletion. we exclude the server storage when analyzing the storage overhead, and consider only the client and enclave storage, as shown in Table 5.

Among the three schemes, Bunker-B only requires \(\mathcal{O}(W\log D)\) storage overhead on the client, without requiring enclave storage. In contrast, the proposed scheme and SGX-SE1 maintain persistent data structures for tracing the deleted documents and their mapping information with keywords within the enclave without incurring any storage overhead on the client. Specifically, SGX-SE1 requires \(\mathcal{O}(W\log D+d)\) storage overhead on the enclave for storing the deleted document list \(d\), and the mapping information \(D\) between the keyword and the deleted documents in \(d\). The proposed scheme also requires the same enclave storage overhead as SGX-SE1, but requires additional storage for the frequently retrieved \(K\)-documents, \(FD\), on the enclave. #### 6.2.4 Utility Loss

We evaluate the retrieval rate of our scheme with synthetic and real-world datasets. **Synthetic dataset. ** When generating a search token, we generate it with a probability (true positive rate) \(p\) close to 1. Hence, there should be the possibility of false negatives, leading to utility loss. In order to evaluate the utility loss, we insert \(1\times 10^{5}\) documents, delete 20% of the documents, and query the top 20 most frequent keywords by setting \(p=0.9999\). We then repeat the above experiment 20 times and calculate the average rate of document retrieval. Figure 4(a) illustrates the retrieval rate when querying the \(i\)th most frequent keywords. In the experiment, the 14 th and 1 st most frequent keywords show the lowest and highest rates of 97.46% and 99.54%, respectively. On average, the proposed scheme retrieves 98.98% of the matching documents, showing a 1.02% utility loss. **Real-world dataset. ** We further evaluate the utility loss of the proposed scheme with a real-world Enron [15] email dataset. For the evaluation, we insert \(3.14\times 10^{5}\) documents, and delete 10% of them.