研究成果

Searchable encryption (SE) enables efficient search over encrypted databases by allowing a predetermined amount of information leakage during operations. While this leakage is typically considered “inconsequential,” its real-world impact on security remains unclear and must be carefully analyzed. Leakage abuse attacks aim to exploit such leakage to recover sensitive information, such as search queries or database contents. In this paper, we revisit one of the most powerful leakage abuse attacks to date, the Subgraph attack (NDSS 2020), and examine two critical aspects: its experimental evaluation methodology and its core algorithm. Although empirical evaluation is essential for understanding the effectiveness of these attacks, we show that prior studies often rely on unrealistic experimental assumptions. We identify and analyze this issue and present a sound and realistic evaluation framework for the Subgraph attack. Our results show that its previously reported effectiveness was indeed overestimated. In addition, we propose two improved variants of the Subgraph attacks, Subgraph+^ID and SimGraph^VL, that exploit allowable leakage commonly considered acceptable in the SE literature. Under our sound experimental setting, these improved attacks achieve up to twice the query recovery performance of the original Subgraph attacks.