## 4 Our Construction
### Scheme Construction
Thus, \(\mathcal{S}\) is unable to specify the exact timestamp for deletion updates. When generating query token during \(Search\), false negative occurs with rate \(1-p\), causing probabilistic omission of query token via \(\tilde{\Phi}_{\widetilde{w}}\). In addition, for generated query tokens, if the matching encrypted documents are cached within the enclave, those tokens are omitted from the result sent to \(\mathcal{S}\) via \(\Pi_{\widetilde{w}}\). When \(\mathcal{A}\) compares the matching document identifier lists of the same query, \(\tilde{\Phi}_{\widetilde{w}}\) and \(\tilde{\Pi}_{\widetilde{w}}\) prevents \(\mathcal{A}\) from learning information required for reconstructing the deletion history. However, \(\mathcal{A}\) is able to learn the timestamps of the inserted entries related to specific \(id\) via \(\mathcal{L}^{hw}\). Hence, the scheme \(\mathcal{D}\) guarantees Type-II backward privacy. ## 6 Implementation and Evaluation

In this section, we evaluate our scheme in comparison to those of [PERSON] et al. (Fort, Bunker-A, and Bunker-B) [8] and [PERSON] et al. (SGX-SE1, SGX-SE2, Maiden) [11; 12], which are state-of-the-art SGX-based DSSE schemes. The comparison results related to performance and security are shown in Tables 4 and 5. ### Implementation Setup

We implemented the prototype of our scheme in C++ using Intel SGX SDK 2.15.1 in a system with SGX-enabled Intel i5-8500 3.0 GHz, 16 GB RAM, and Ubuntu 18.04.5 LTS. Also, we used a synthetic dataset [11] consisting of 100,000 documents with a keyword frequency following the Zipf distribution. The prototype utilizes cryptographic primitives in the SGX SDK for supporting cryptographic operations. We also used APIs provided by SDK to create, manage, and access the enclave. Note that the enclave is only allocated 96 MB memory [7], thus using memory more than 96 MB requires the paging mechanism [7]. As paging triggers extra overhead to the system, we leveraged batch processing during the search. In the experiment, we set the batch size to \(1\times 10^{4}\) for all schemes. For large datasets, the size of the query token may be large; thus, by dividing the size of the search query to the multiple batches, we minimize the chances of a paging mechanism. ### Performance

We now evaluate the performance of each scheme. In the evaluation, we compare our scheme mainly with SGX-SE1 and Bunker-B, because they are both designed using Intel SGX with the same assumptions and system environment. Bunker-B provides the same security level as the proposed scheme. Even though SGX-SE1 was originally designed to provide Type-II backward privacy with high efficiency, we prove it guarantees Type-II privacy partially. Although SGX-SE2 also provides the same level of backward privacy as SGX-SE1, it is a simple extension from SGX-SE1 adopting a bloom filter. Thus, SGX-SE2 is not considered in the performance evaluation. #### 6.2.1 Insertion and Deletion Time

We evaluate the time required for insertion and deletion updates. As shown in Table 4, both the computation and communication costs for update (i.e., addition and deletion) are \(\mathcal{O}(1)\) in time complexity. However, when evaluated with real-world implementation using a synthetic dataset, there is a noticeable difference in efficiency. In the experiment, we measured the runtime for adding \(1\times 10^{4}\), \(5\times 10^{4}\), and \(1\times 10^{5}\) documents into the EDB in each scheme. As shown in Figure 3a, Bunker-B takes \(881\) ms, \(4099\) ms, and \(8443\) ms to insert \(1\times 10^{4}\), \(5\times 10^{4}\), \(1\times 10^{5}\) documents, respectively. SGX-SE1 takes \(426\) ms, \(2221\) ms, and \(4340\) ms, and the proposed scheme takes \(341\) ms, \(1667\) ms, and \(3329\) ms for each respective