## 3 Leakage Abuse Attack
### Attacks on Prior Works
#### 3.3.1 [PERSON] et al. Scheme  
[PERSON] et al. [11] proposed SGX-based forward and Type-II backward private dynamic searchable encryption schemes, named SGX-SE1 and SGX-SE2. In this paper, we focus only on SGX-SE1 because it is the baseline scheme upon which SGX-SE2 is built. When a client uploads a new document in SGX-SE1, the document is sent to the SGX enclave in the server through the addition operation in the update protocol. The enclave then parses all the keywords within the document, and uses the latest state \(ST[w]\), which infers the number of documents containing \(w\). Specifically, for each keyword \(w\), \(ST[w]\) increases by 1 whenever a document containing \(w\) is added. The encrypted index \(u\) is a deterministic value generated by \(H(k_{w},\epsilon)\), where \(H\) refers to a hash function that hashes \(k_{w}\), which is a key value bound to \(w\), and the count value \(c\) of \(ST[w]\). A map of the encrypted index \(M_{I}[u]\) stores the encrypted document identifier. When deleting a document, the client transfers the corresponding document identifier \(id\) to the enclave. On receipt of it, the enclave stores the \(id\) within a deleted document list \(d\), and the actual deletion of it from the EDB is conducted during the search protocol. In the search protocol, when the enclave receives a keyword \(w\) from the client, it first fetches the document identifiers from the deleted document list \(d\). Next, the enclave loads the corresponding documents and checks whether the keyword \(w\) exists within each document. The enclave retrieves \(ST[w]\) of the deleted documents, which were used when they were added, and excludes these values from \(\{0,...,ST[w]\}\). The remaining values in the set are then used to generate query token \(u\) for the non-deleted documents. The list of query tokens \(u\) is transferred to the server. Finally, the server computes the \(id\) by decrypting \(M_{I}[u]\), and returns the corresponding encrypted documents to the client. **Extraction Scenario. ** Table 2 shows the example flow of SGX-SE1 protocol [11], along with the leakage information and its type. When searching on keyword \(w\) in SGX-SE1, the enclave sends a search query \(Q_{w}\) containing a list of \((u,k_{id})\) pairs to the server, where \(k_{id}\) refers to the key value bound to the document identifier. The adversary can observe and trace from \(Q_{w}\) the deterministic values of \(u\)'s, which are bound to the specific keyword. Therefore, by comparing the values of \(u\) from the past search, the adversary learns if two different queries are on the same keyword, leading to the search pattern leakage. Because the document identifiers and encrypted documents are retrieved in the untrusted area, the adversary can observe the access pattern of the matching result as well as the accessed document identifiers. The adversary compares the matching results of the two queries and learns that deletion update on \(id_{3}\) occurred in the period between the two searches (as shown in Table 2). Among the three delete updates that occurred between the two searches, one of them must correspond to the deletion of \(id_{3}\), thus the probability of making a correct guess is \(\frac{1}{3}\). Since the adversary has the knowledge of the timestamps of all updates and when each document is added with their identifier values, the aforementioned leakage information allows the adversary to learn \(DelHist(w)\).