## 4 Our Construction
### Scheme Construction
The received \((id,f)\) is stored in repository \(R\), located in the server area. Then, the enclave parses the received doc to retrieve a list of \(\{(w,id)\}\). For each keyword \(w\), the enclave uses \(k_{\Sigma}\) to generate \(k_{w}\) and \(k_{c}\), and retrieves the latest state \(c\). Then, \(k_{id}\) is generated from \(c\) by executing the hash function as \(k_{id}=H_{1}(k_{w},c)\); and two encrypted entries \((u,v)\) and \((u^{\prime},v^{\prime})\) are generated using \(k_{w}\), \(k_{c}\), and \(k_{id}\) as follows:  
\[(u,v)=(H_{2}(k_{w},c),\)Enc(\(k_{id},id)),\]  
where the values of \((u,v)\) contain the mapping information between \(c\) and \(id\) that is retrieved based on \(u\) and \(k_{id}\). \[(u^{\prime},v^{\prime})=(H_{3}(k_{w},id),\)Enc(\(k_{c},c\)),\]where \((u^{\prime},v^{\prime})\) holds the encrypted state of the document with identifier \(id\), and allows the client to check the states of deleted documents by sending \(u^{\prime}\) in the _Search_ algorithm. The enclave adds each \((u,v)\) and \((u^{\prime},v^{\prime})\) to tuples \(T_{1}\) and \(T_{2}\), respectively, and sends \((T_{1},T_{2})\) to the server for updating \(M_{I}\) and \(M_{c}\). When a deletion update is invoked (i.e., \(\text{op}=del\)), the client simply sends \(id\) to the enclave. On receipt of it, the enclave updates the list \(d\) by adding the received \(d\) to the list, and does not require further computations or communications with the server. ```
Client:
1: Send \(w\) to Enclave
2:
3:\(st_{w_{c}}\leftarrow\{\emptyset\}\), \(Q_{w}\leftarrow\{\emptyset\}\)
4:\(k_{w}\|k_{c}\gets F(k_{\Sigma},w)\)
5:foreach\(id_{i}\)in\(d\)do
6:\(f_{i}\gets R[id_{i}]\)
7:\(doc_{i}\leftarrow\text{Dec}(k_{f_{i}},f_{i})\)
8:if\(w\)in\(doc_{i}\)then
9:\(D[w]\gets id_{i}\cup D[w]\)
10:endif
11:endfor
12:foreach\(id\)in\(D[w]\)do
13:\(u^{\prime}\gets H_{3}(k_{w},id)\)
14:\(v^{\prime}\gets M_{c}[u^{\prime}]\)
15:\(c\leftarrow\text{Dec}(k_{c},v^{\prime})\)
16:\(st_{w_{c}}^{del}\leftarrow\{c\}\cup st_{w_{c}}^{del}\)
17:endfor
18:\(st_{w_{c}}\leftarrow\{0,...,ST[w]\}\setminus st_{w_{c}}^{del}\)
19:foreach\(c\)in\(st_{w_{c}}\)do
20:\(u\gets H_{2}(k_{w},c)\)
21:\(k_{id}\gets H_{1}(k_{w},c)\)
22: with prob. \(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:\(\text{SC}[id_{i}]\gets sc+1\)
31:endif
32:if\(id\)in\(FD\)then
33:\(doc_{i}\gets FD[id_{i}]\)
34:else
35:\(doc_{i}\gets R[id_{i}]\)
36:endif
37:add\(doc_{i}\) to Res
38:endfor
39:Send\(Res\) to Client
40:Update \(FD\) Server:
41:receive \(Q_{w}\) from Enclave
42:foreach\((u_{i},k_{id_{i}})\)in\(Q_{w}\)do
43:\(id_{i}\leftarrow\text{Dec}(k_{id_{i}},M_{I}[u_{i}])\)
44:\(Q_{docId}\leftarrow\{id_{i}\}\cup Q_{docId}\)
45:endfor
46:send \(Q_{docId}\) to Enclave
```  
**Algorithm 3**\(Search(w)\)  
**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:endfor
11:foreach\(id\)in\(D[w]\)do
12:\(u^{\prime}\gets H_{3}(k_{w},id)\)
13:\(v^{\prime}\gets M_{c}[u^{\prime}]\)
14:\(c\leftarrow\text{Dec}(k_{c},v^{\prime})\)
15:\(st_{w_{c}}^{del}\leftarrow\{c\}\cup st_{w_{c}}^{del}\)
16:endfor
17:\(st_{w_{c}}\leftarrow\{0,...,ST[w]\}\setminus st_{w_{c}}^{del}\)
18:foreach\(c\)in\(st_{w_{c}}\)do
19:\(u\gets H_{2}(k_{w},c)\)
20:\(k_{id}\gets H_{1}(k_{w},c)\)
21:\(k_{id}\gets H_{1}(k_{w},c)\)
22: with prob.