(CCS’2021)LEAP: Leakage-Abuse Attack on Efficiently Deployable, Efficiently Searchable Encryption with Partially Known Dataset.

Searchable Encryption (SE) enables private queries on encrypted documents. Most existing SE schemes focus on constructing industrial-ready, practical solutions at the expense of information leakages that are considered acceptable. In particular, ShadowCrypt utilizes a cryptographic approach named “efficiently deployable, efficiently searchable encryption” (EDESE) that reveals the encrypted dataset and the query tokens among other information. However, recent attacks showed that such leakages can be exploited to (partially) recover the underlying keywords of query tokens under certain assumptions on the attacker’s background knowledge. We continue this line of work by presenting LEAP, a new leakage-abuse attack on EDESE schemes that can accurately recover the underlying keywords of query tokens based on partially known documents and the L2 leakage as per defined by Cash et al. (CCS ’15). As an auxiliary function, our attack supports document recovery in the similar setting. To the best of our knowledge, this is the first attack on EDESE schemes that achieves keyword recovery and document recovery without error based on partially known documents and L2 leakage. We conduct extensive experiments to demonstrate the effectiveness of our attack by varying levels of attacker’s background knowledge.