## 4 Our Construction
### Scheme Construction
\(p\), \(Q_{w}\leftarrow\{(u,k_{id})\}\cup Q_{w}\)
23:endfor
24:send \(Q_{w}\) to Server
25:receive \(Q_{docId}\) from Server
26:foreach\(id_{i}\)in\(Q_{docId}\)do
27:if\(sc=\bot\)then\(sc=1\)
28:else
29:\(sc\leftarrow\text{SC}[id_{i}]\)
30:\(SC[id_{i}]\gets sc+1\)
31:endif
32:endif
33:endif
34:endif
35:endfor
36:endfor
37:endfor
38:endfor
39:endfor
40:receive \(Q_{docId}\) from Enclave
41:foreach\((u_{i},k_{id_{i}})\)in\(Q_{w}\)do
42:\(id_{i}\leftarrow\text{Dec}(k_{id_{i}},M_{I}[u_{i}])\)
43:\(Q_{docId}\leftarrow\{id_{i}\}\cup Q_{docId}\)
44:endfor
45:send \(Q_{docId}\) to Enclave
```  
**Algorithm 4**\(Search(w)\)  
**Client**:  
**Client**:  
``` Client:
1: Send \(w\) to Enclave
2:\(st_{w_{c}}\leftarrow\{\emptyset\}\), \(Q_{w}\leftarrow\{\emptyset\}\)
3:\(k_{w}\|k_{c}\gets F(k_{\Sigma},w)\)
4:foreach\(id_{i}\)in\(d\)do
5:\(f_{i}\gets R[id_{i}]\)
6:\(doc_{i}\leftarrow\text{Dec}(k_{f_{i}},f_{i})\)
7:if\(w\)in\(doc_{i}\)then
8:\(D[w]\gets id_{i}\cup D[w]\)
9:endif
10:endifIn the _Search_ algorithm, when the client sends a query containing a keyword \(w\) to the enclave through a secure channel, the enclave begins with checking deleted documents in the list \(d\). Specifically, all of the documents in \(d\) are loaded into the enclave. The enclave then decrypts them using \(k_{f}\), and checks if the queried keyword \(w\) is included in any of them. If \(w\) exists in some documents, their document identifiers are updated to \(D[w]\). After that, each \(id\) in \(D[w]\) allows retrieval of the state list \(st_{w_{c}}^{del}\supset\{c_{id}\}\), where \(c_{id}\) refers to the state used when the document \(id\) is added for keyword \(w\). By excluding the states in \(st_{w_{c}}^{del}\) from the set of \(\{0,...,ST[w]\}\), the enclave obtains a state list \(st_{w_{c}}\) for the non-deleted documents. The enclave computes \(|st_{w_{c}}|\) number of encrypted index pairs \((u,k_{id})\)s to form search query \(Q_{w}\). Note that each pair \((u,k_{id})\) is added to \(Q_{w}\) with probability \(p\) (typically, \(p\) will be close to 1), aiming to retrieve matching documents with false negatives of a small probability \((1-p)\). Therefore, it holds

\[Q_{w}[i]\sim\mathbf{Bern}(p),\;\textit{where}\;i\leq|st_{w_{c}}|. \tag{1}\]

The enclave sends \(Q_{w}\) to the server. The server decrypts \(M_{t}[u_{i}]\) with \(k_{id_{i}}\), stores obtained document identifiers in \(Q_{\textit{docId}}\), and sends \(Q_{\textit{docId}}\) to the enclave. After that, the enclave increments the search counter \(SC[id_{i}]\) of each matching document \(id_{i}\). When retrieving them, the enclave adds the corresponding encrypted documents to the search result \(\textit{Res}\) without accessing the untrusted area if they are stored in the frequently matched document map \(FD\) to minimize the possibility of access pattern leakage to the server, or they are retrieved from the repository \(R\) located in the untrusted area, otherwise. Finally, the enclave sends \(\textit{Res}\) to the client and updates \(FD\) based on the updated \(SC\). ## 5 Security Analysis

In this section, we analyze the security of the proposed scheme, and prove that it guarantees forward and Type-II backward privacy. _Setup_ leaks nothing to the server by leveraging a secure channel established by remote attestation. However, because the adversary can observe the interactions between its memory and the enclave during the search and update procedures, we consider the communications between them as information leakage in the proposed scheme. For addition, _Update_ leaks timestamp and memory access patterns when inserting new entries to the data structures \(M_{I}\), \(M_{c}\), and \(R\). For deletion, _Update_ does not reveal any information to the server because there is no interaction between the enclave and the server. In _Search_, the access patterns on \(M_{I}\), \(M_{c}\), and \(R\) are revealed to the server. **Definition 1** (Obfuscated Search Pattern).