## 4 Our Construction
### Scheme Construction  
To facilitate searches, our scheme lets the enclave store the following information: (1) the map \(ST\) storing the pairs of a keyword and its latest state, (2) the deleted document list \(d\), (3) the map \(D\) storing the pairs of a keyword and a deleted document's \(id\) in \(d\) associated with the keyword, (4) the map \(SC\) storing the pairs of a document \(id\) and the number of searches over the document, and (5) the map \(FD\) storing the pairs of a document \(id\) and its encrypted data in the EDB. Each notation is defined in Table 3.  
The proposed scheme consists of three algorithms: _Setup_ (Algorithm 1), _Update_ (Algorithm 2), and _Search_ (Algorithm 3). In the algorithms, \(H_{1}\), \(H_{2}\), and \(H_{3}\) denote the cryptographic hash functions, and \(\mathsf{Enc}(a,b)\) is the encryption of \(b\) under a key \(a\). ```
Client:
1:\(k_{\Sigma},k_{f}\leftrightarrow\{0,1\}^{\lambda}\)
2: Launch Remote Attestation \(\triangleright\) Establish secure channel
3: Send \(K=(k_{\Sigma},k_{f})\) to Enclave:
4: Initialize maps \(ST\), \(D\), \(SC\), \(FD\); tuples \(T_{1}\), \(T_{2}\); a list \(d\)
5: Receive \(K=(k_{\Sigma},k_{f})\) Server:
6: Initialize maps \(M_{I}\) and \(M_{c}\)
7: Initialize Repository \(R\)
```  
**Algorithm 1**\(Setup(1^{\lambda})\)  
In the _Setup_ algorithm, the client communicates with the enclave and provisions a secret key \(K\) containing a key pair \((k_{\Sigma},k_{f})\) through the secure channel established by the attestation service provided by Intel [7]. The enclave uses \(k_{\Sigma}\) to generate update and query tokens and a symmetric key \(k_{f}\) to encrypt/decrypt a document. The enclave initializes the maps \(ST\) and \(D\) and the list \(d\). The server initializes the maps \(M_{I}\) and \(M_{c}\), where \(M_{I}\) and \(M_{c}\) refer to the encrypted index and the encrypted state, respectively. Also, the repository \(R\) stores the encrypted document with its document identifier \(id\). \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline \(K\) & Secret key \\ \hline \(ST\) & Latest state of keywords \\ \hline \(d\) & List of deleted documents \\ \hline \(D\) & A map for keyword and deleted documents \\ \hline \(SC\) & Number of times each document searched \\ \hline \(FD\) & \(k\)-frequent documents \\ \hline \(R\) & Repository (EDB) \\ \hline \(M_{I}\) & Encrypted index \\ \hline \(M_{c}\) & Encrypted state \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Notations of data structures. ```
1:Client:
2:ifop = \(add\)then
3:\(f\leftarrow\)Enc(\(k_{f}\), doc)
4:send (op, \(id,f\)) to Enclave \(\triangleright\) when op = \(del\)
5:else
6: send (op, \(id\)) to Enclave
7:endif
8:Enclave:
9:ifop = \(add\)then
10: send (\(id,f\)) to Server
11:\(\{(w,id)\}\leftarrow Parse(\)Dec(\(k_{f},f\)))
12:foreach \((w,id)\)do
13:\(k_{w}\|k_{c}\gets F(k_{\Sigma},w)\)
14:\(c\gets ST[w]\)
15:if\(c=\bot\)then\(c=-1\)
16:endif
17:\(c\gets c+1\)
18:\(k_{id}\gets H_{1}(k_{w},c)\)
19:\((u,v)\leftarrow(H_{2}(k_{w},c),\)Enc(\(k_{id},id\)))
20:add (\(u,v\)) to \(T_{1}\)
21:\((u^{\prime},v^{\prime})\leftarrow(H_{3}(k_{w},id),\)Enc(\(k_{c},c\)))
22:add (\(u^{\prime},v^{\prime}\)) to \(T_{2}\)
23:endfor
24:send (\(T_{1},T_{2}\)) to Server \(\triangleright\) when op = \(del\)
25:else
26:add \(id\) to \(d\)
27:endif
28:Server:
29:\(R[id]\gets f\)
30:receive \((T_{1},T_{2})\) from Enclave
31:foreach \((u,v)\)in \(T_{1}\)do
32:\(M_{1}[u]=v\)
33:endfor
34:foreach \((u^{\prime},v^{\prime})\)in \(T_{2}\)do
35:\(M_{c}[u^{\prime}]=v^{\prime}\)
36:endfor
```  
**Algorithm 2**\(Update(\)op, in\()\)  
The \(Update\) algorithm takes as an input (op,in), where op can be either \(add\) or \(del\), and \(in\) would be (doc, \(id\)) if op = \(add\), or \(id\) if op = \(del\). When an add update is invoked (i.e., op = \(add\)) in the algorithm, the client generates an encrypted document \(f\) by encrypting the doc under a key \(k_{f}\). The enclave receives \((\text{op},f,id)\) from the client.