Breaking Beyond One: Mirage Attacks for Highly Accurate Multi-Keyword Query Recovery With Partial Similar Data Against SE

Searchable encryption (SE) allows users to perform private queries on encrypted databases. Although SE schemes can protect data privacy, some often pursue high performance while allowing certain leakages, such as search and access patterns. Exploiting such leakage together with other knowledge similar to the user’s database, an attacker can recover queries. State-of-the-art attacks (Nie et al., USENIX’ 24) on single-keyword queries achieve accuracies exceeding 90%. More recently, the community has focused on the more challenging attack of recovering multikeyword queries, with the most advanced attacks (Liu et al., TIFS’ 25) achieving over 80% accuracy. Although these attacks can effectively recover queries, they all rely on a large amount of similar document, requiring the attacker to possess documents equivalent in volume to the database. This naturally raises a question: Can we achieve higher-accuracy attacks using less similar data? Less information makes attacks easier to implement. Motivated by this, we present Mirage, an attack that recovers both single-keyword and multi-keyword queries while requiring only partial similar data. Our core idea is to first identify some special queries and design a series of novel algorithms to recover them. Then, partially reconstruct the database index and recover the remaining queries. Extensive experiments conducted across various real-world datasets demonstrate the effectiveness of our attack. The results show that when the attacker observes 51 time intervals and obtains only 0.5% of similar documents in each interval, Mirage achieves 91.6% and 95.4% accuracy on the Enron and Lucene datasets for single-keyword queries, respectively. For multi-keyword queries, Mirage achieves up to 90.7% and 93.5% recovery accuracy, respectively.