## 3 Leakage Abuse Attack
### Extraction of Deletion History  
As described in Section 2.3.2, Type-II backward privacy only leaks document identifiers matching the searched keyword \(w\), \(TimeDB(w)\), and \(Updates(w)\). If a scheme leaks \(DelHist(w)\) along with the other Type-II leakages, the adversary is allowed to know which deletion update cancels which add update that previously occurred, downgrading it into Type-III backward privacy. Thus, if a part of deletion history is revealed to an adversary, the privacy level of the scheme may be weakened than the original Type-II backward privacy level. According to our investigation of the existing Type-II backward private schemes, we observed that they may leak \(DelHist(w)\) when an adversary can exploit the access and search pattern leakages together with information leakages allowed in Type-II backward privacy (especially when they are constructed with static data structures or static values for identifying documents matching a specific keyword \(w\)). In order to obtain it, specifically, the adversary should be able to (1) distinguish whether the update operation is addition or deletion, and (2) distinguish whether two separate queries are on the same keyword \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Scheme** & **BP-Type** & **Prone to Attack** & **SGX** \\ \hline Fides & Type-II & X & - \\ \hline Mitra & Type-II & X & - \\ \hline Bunker-B & Type-II & X & O \\ \hline SGX-SE1 & Type-II & O & O \\ \hline SGX-SE2 & Type-II & O & O \\ \hline Aura & Type-II & O & - \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Classification of existing Type-II DSSE schemes. (search pattern leakage). When an addition operation is executed, the adversary is able to observe the added document identifier \(id\) from the update query (but not the keyword \(w\)). Thus, the adversary learns \((u,add,(w,id))\), where \(u\) refers to the timestamp of the operation. According to the definition of Type-II backward privacy, \(DelHist(w)\) should be hidden from the view of the server. Next, during the search protocol for a specific keyword, the server is able to observe the query tokens and memory access of the EDB (i.e., the access pattern). Note that each query token refers to a single document. If the query token or the search index is encrypted, the adversary may observe the following search query consisting of the encrypted \(i\) query tokens \(Q=\{qt_{1}^{up},qt_{2}^{up},...,qt_{l}^{up}\}\), where \(qt_{j}^{up}\) refers to the \(j\)-th query token for keyword \(w\) for \(1\leq j\leq i\). The adversary then observes and learns the search result \(Res=\{id_{1},id_{2},...,id_{i}\}\), directly indicating the access pattern of the EDB for the documents in \(Res\). When a client sends a search query \(Q^{\prime}\) consisting of \(k\) query tokens later, the adversary would observe \(Q^{\prime}=\{qt_{1}^{up},qt_{2}^{up},...,qt_{k}^{up}\}\), and learn \(Res^{\prime}=\{id_{1}^{\prime},id_{2}^{\prime},...,id_{k}^{\prime}\}\), for the search result of \(Q^{\prime}\). If the value of query token \(qt\) is encrypted in a deterministic manner and is bound to a specific keyword, then the adversary can identify whether two different search queries are linked to the same keyword \(w\) by simply comparing the values of the query tokens (When the query token is generated in a non-deterministic manner, such as re-encryption, as in Bunker-B [8], for example, our extraction of deletion history might not work due to the indistinguishability in the adversary's view.). When observing \(i>k\), the adversary may learn the deletion updates are performed between two searches of \(Q\) and \(Q^{\prime}\) on the same keyword \(w\). Further, by comparing the search results \(Res\) and \(Res^{\prime}\), the adversary can learn which document \(id\) was deleted. Consequently, the probability that the adversary can determine which delete updates are related to \(w\) is \(P_{Del(w)}=\frac{i-k}{Nd_{del}}\), where \(Nd_{del}\) is the number of possible deletion operations performed in the period.