## 3 Leakage Abuse Attack
### Feasibility of Deletion History Extraction  
We evaluate the feasibility of deletion history extraction by conducting a simulation on its probability in diverse distribution models of data upload, delete, and keyword search in the cloud storage. In the simulation, we randomly generate queries and analyze the probability of deletion history extraction.  
According to the distribution models for file transfer [22] and search query [23], we assume that the document upload follows a Poisson distribution with rate \(\tilde{\lambda}\), the data lifespan follows an exponential distribution with a mean duration \(\frac{1}{\mu}\), and the search request on the same keyword follows an exponential distribution with a mean duration \(\frac{1}{\mu^{\prime}}\). Also, the keyword frequency of the documents follows a Zipf distribution.  
Based on the aforementioned distribution models, we evaluate the feasibility of deletion history extraction by measuring its probability under various simulation settings. Figure 1 shows the evaluation results in each case. In the figure, the horizontal axis represents the time in hours, and the vertical axis represents the probability of successful extraction \(P_{Del(w)}\), which is the probability of identifying which document is deleted. When simulating for 100 h with \(\tilde{\lambda}=3\), \(\frac{1}{\mu}=40\), and \(\frac{1}{\mu^{\prime}}=1\), we have observed a total of 11 time instances that enable our extraction with non-negligible probabilities. As shown in Figure 1a, for example, there exists a time instance when the extraction succeeds with 100% (between 56 and 57 h), leading to the violation of Type-II backward privacy. As another example, one can observe that \(P_{Del(w)}\) reaches 0.5 two times between 20 and 70 h, meaning that the deleted document can be identified with probability \(\frac{1}{2}\), violating Type-II backward privacy in a probabilistic (but still pragmatically meaningful) way in those periods. Figure 1b shows the evaluation results when search requests are performed on average four times more frequently than in Figure 1a. As a result, we could observe that there are two time instances showing \(P_{Del(w)}=1\) (between 33 and 34; 61 and 62 h) and five time instances showing \(P_{Del(w)}=0.5\).  
In Figure 1a,b, on average, 53 update queries (consisting of 41 addition and 10 deletion queries) were generated for the target keyword. When considering all of the update queries in the above simulations, the adversary could extract 1.6% and 3.2% of actual deletion history for the target keyword, respectively. For deletion queries for the target keyword, the adversary could extract 10% and 20% of deletion queries. When considering the attack success rate above \(P_{Del(w)}=0.5\), the probability of possible deletion history extraction non-negligibly increases.  
The aforementioned simulations indicate that the extraction probability increases as the number of search requests on the same keyword increases (compare Figure 1a,b) When calculating \(P_{Del(w)}\), the total number of deletions that occurred between two searches on the same keyword, \(N_{del}\), affects the probability. It is clear that if the search requests are sent more frequently, \(N_{del}\) would be smaller with high probability, leading to an increase in \(P_{Del(w)}\).