## 4 Our Construction
### Scheme Construction
The transcript obtained by \(\mathcal{S}(\mathcal{L}^{Srch}(w))\) is returned by the challenger. Finally, \(\mathcal{A}\) returns a bit \(b\). For all probabilistic polynomial time algorithms \(\mathcal{A}\), if there exists a PPT simulator such that

\[|\Pr[\mathbf{Real}_{\mathcal{A}}(\lambda)=1]-\Pr[\mathbf{Ideal}_{\mathcal{A}, \mathcal{S}}(\lambda)=1]|\leq\mathbf{negl}(\lambda),\]

then \(\mathcal{D}\) is \(\mathcal{L}\)-secure against adaptive chosen-keyword attacks. **Definition 3** (\(\mathcal{L}\)-security). : _Scheme \(\mathcal{D}\) consists of three protocols: \(Setup\), \(Update\), and \(Search\). \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) are probabilistic experiments, where \(\mathcal{A}\) is a stateful adversary and \(\mathcal{S}\) is a stateful simulator that gets the leakage function \(\mathcal{L}\). \(\mathcal{D}\) is \(\mathcal{L}\)-secure if \(\mathcal{A}\) can distinguish \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) with negligible probability._

The scheme \(\mathcal{D}\) is secure if it achieves both forward and Type-II backward privacy. Since the client issues a query on keyword \(w\) to the enclave through the secure channel, \(\mathcal{A}\) has to generate a query token by itself in the game presented in Definition 3. Forward privacy is guaranteed because state \(ST[w]\) increases when a new document containing \(w\) is inserted. The increase in state value constrains \(\mathcal{A}\) to generate a query token to retrieve newly added documents. Regarding backward privacy, \(\mathcal{A}\) can learn the timestamps indicating when the deleted states of \(w\) were added in \(M_{c}\), when the enclave requests the server to access \(M_{c}\) during \(Search\), but \(\mathcal{A}\) cannot know when they were actually requested for deletion. Scheme \(\mathcal{D}\) caches deletion requests in the enclave and only accesses them during \(Search\). Due to the obfuscation technique in the scheme, during the search on \(w\), the enclave generates the query tokens and includes them with probability \(p\). In other words, a false negative occurs with probability \(1-p\), which probabilistically omits the query tokens in the result. Therefore, \(\mathcal{A}\) is unable to identify whether the tokens are omitted due to deletion operations or false negatives. In addition, the enclave stores the most frequently retrieved document. Thus, if the matching document exists within the map \(FD\), the enclave does not request the server to access \(R\) for those documents. As a result, \(\mathcal{A}\) does not know which delete updates are conducted for specific document identifiers. Theorem 3.1: _Scheme \(\mathcal{D}\) is \(\mathcal{L}\)-secure according to Definition 3._

Proof: We now prove Theorem 3.1 by illustrating a PPT simulator \(\mathcal{S}\) for which \(\mathcal{A}\), a PPT adversary, can distinguish \(\textbf{Real}_{\mathcal{A}}(\lambda)\) and \(\textbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) with negligible probability. * \(Setup:\mathcal{S}\) performs a random key generation \(\tilde{R}=(\tilde{k}_{\sigma},\tilde{k}_{f})\) to simulate the key components provisioned inside the enclave. * \(Simulate:\mathcal{S}\) executes \(Update\) on a random keyword \(w\) and obtains a query token \(q\). Then, \(\mathcal{S}\) performs an addition update for \(w\) based on \(\tilde{R}\) and \(\mathcal{L}^{hw}(M_{I},M_{c},R)\), and passes them to the enclave to receive the new update of \((M_{I},M_{c},R)\). However, \(\mathcal{A}\) cannot classify which update tokens match \(q\) because the enclave keeps increasing the state \(ST[w]\). Thus, \(\mathcal{S}\) is unable to distinguish between the output of \(\textbf{Real}_{\mathcal{A}}(\lambda)\) and the simulated output in \(Update\) and \(Search\), guaranteeing forward privacy. * \(Simulate:\mathcal{S}\) executes \(Search\) on a random keyword \(w\). The encrypted documents in the deleted document list \(d\) stored in the enclave are only requested during \(Search\).