## 4 Our Construction
### Scheme Construction
: _The obfuscated search pattern \(\tilde{\Phi}_{\overrightarrow{w}}^{\rightarrow}\) is the vector characterized by Equation (2)_

\[\tilde{\Phi}_{\overrightarrow{w}}=(u_{1},...,u_{|i|}),\textnormal{where}\;i \leq|st_{w}|, \tag{2}\]

_where \(u\) refers to the encrypted index or query token generated during the search._

**Definition 2** (Obfuscated Access Pattern). : _The obfuscated access pattern \(\tilde{\Pi}_{\overrightarrow{w}}^{\rightarrow}\) is the vector_

\[\tilde{\Pi}_{\overrightarrow{w}}^{\rightarrow}=(id_{1},id_{2},...,id_{|i-|fd |}), \tag{3}\]

_where \(|fd|\) refers to the number of documents retrieved from cached map \(FD\)._

We formulate the leakage function, and define \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) games for an adaptive adversary \(\mathcal{A}\) and a polynomial time simulator \(\mathcal{S}\). \(\mathcal{D}\) denotes the proposed scheme, and the leakage function of \(\mathcal{D}\) is

\[\mathcal{L}=(\mathcal{L}^{Stp},\mathcal{L}^{Updt},\mathcal{L}^{\textit{Srch} },\mathcal{L}^{\textit{hw}}).\]Note that the first three leakage functions define the information exposed in \(Setup\), \(Update\), and \(Search\), respectively. \(\mathcal{L}^{hw}\) refers to the inherent leakage of the enclave exposed during the interaction between the enclave and the server. \(Setup\) leaks nothing to the server, but the data structures of \(M_{I}\), \(M_{c}\), and \(R\) are revealed to the server during the initialization. \(Update\) leaks information to the server only when \(\text{op}=add\). The access pattern of encrypted entries is observed by the server when they are inserted to \(M_{I}\), \(M_{c}\), and \(R\). When \(op=del\), \(\mathcal{D}\) leaks nothing to the server because there is no interaction between the enclave and the server. Therefore,

\(\mathcal{L}^{Updt}(\text{op},\text{in})=(T_{1},T_{2},R[id_{i}])\). \(T_{1}\) is a tuple of \(\{(u,v)\}\) that is inserted to \(M_{I}\) (i.e., encrypted index), and \(T_{2}\) is a tuple of \(\{(u^{\prime},v^{\prime})\}\) that is inserted to \(M_{c}\) (i.e., encrypted map of keyword states). \(R[id_{i}]\) refers to the encrypted document inserted with document identifier \(id_{i}\). \(Search\) leaks obfuscated search pattern \(\hat{\Phi}_{\widetilde{w}}\) when the enclave sends query tokens to the server, obfuscated access pattern \(\hat{\Pi}_{\widetilde{w}}\) when it retrieves the encrypted documents from the server, and the patterns on the deleted documents' list \(d_{w}\). \(\mathcal{L}^{Srch}\) is defined as

\(\mathcal{L}^{Srch}=(\hat{\Phi}_{w},\hat{\Pi}_{w},d_{w})\). \(\mathcal{L}^{hw}\) includes hardware leakages observed during \(Update\) and \(Search\), such as memory access patterns, locations, timestamps, and manipulated memory areas for \(M_{I}\), \(M_{c}\), and \(R\). \(\mathcal{L}^{hw}\) is defined as

\(\mathcal{L}^{hw}=((M_{I},M_{c},R)^{Updt},(M_{I},M_{c},R)^{Srch})\). \(\mathbf{Real}_{\mathcal{A}}(\lambda)\): As presented in Algorithm 1, the challenger performs \(Setup(1^{\lambda})\) to initialize data structures used by the client, the server, and the enclave. \(\mathcal{A}\) selects a database \(DB=\{doc_{i}\}_{i\in\mathbb{N}}\) and performs a polynomial number of updates, where \(\mathbb{N}\) is a natural number of documents. When the challenger runs \(Update(\text{op},in)\), \((M_{I},M_{c},R)^{Updt}\) is returned to \(\mathcal{A}\). After that, \(\mathcal{A}\) selects a keyword \(w\) and performs \(Search\). As a result of \(Search(w)\), the challenger returns the transcript of each operation and outputs \((M_{I},M_{c},R)^{Srch}\) to \(\mathcal{A}\). Finally, \(\mathcal{A}\) outputs a bit \(b\). \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\): \(\mathcal{A}\) selects a \(DB=\{doc_{i}\}_{i\in\mathbb{N}}\). \(\mathcal{S}\) generates a tuple of \((M_{I},M_{c},R)\) by using \(\mathcal{L}^{Updt}\) and \((M_{I},M_{c},R)^{Updt}\). Then, \(\mathcal{S}\) sends the generated tuple to \(\mathcal{A}\). \(\mathcal{A}\) adaptively selects the keyword \(w\) to search.