Full Database Reconstruction: Leakage-Abuse Attacks Based on Expected Distributions

Searchable encryption enables processes on encrypted databases, making it widely used in the field of cloud database storage. However, encrypted search also faces security issues. Recent studies have shown that curious servers may obtain hidden attributes of data after a large number of queries and responses. In this paper, we propose a leakage-abuse attack exploiting access pattern leakage, where the order of records is determined by calculating the difference set between sets containing edge domains and introducing frequency trends as the expected distribution for analysis, dynamically match the sorted data with the expected distribution data through a sliding window, accurately locating the features and patterns of the database. Additionally, we attack common databases that have been supplemented with false responses, by exploiting additional leakage of volume patterns, hidden attributes can be recovered. Finally, our work prove the effectiveness on real-world medical data through extensive experimentation, showing that the attack always achieves full order reconstruction and completes full database reconstruction with high probability.