Cryptology ePrint Archive: Report 2021/1035

Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data

Seny Kamara and Abdelkarim Kati and Tarik Moataz and Thomas Schneider and Amos Treiber and Michael Yonli

Abstract: An encrypted search algorithm (ESA) allows a user to encrypt its data while preserving the ability to search over it. As all practical solutions leak some information, cryptanalysis plays an important role in the area of encrypted search. Starting with the work by Islam et al. (NDSS'12), many attacks have been proposed that exploit different leakage profiles under various assumptions. While they aim to improve our common understanding of leakage, it is difficult to draw definite conclusions about their practical risk. This uncertainty stems from many limitations including a lack of reproducibility due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. Particularly, assumptions made about the query distribution do not have any empirical basis because datasets containing users' queries are hard to find.

In this work, we address the main limitations of leakage cryptanalysis. First, we design and implement an open-source framework called LEAKER that can evaluate the major leakage attacks against a given dataset and can serve as a common leakage analysis reference for the community. We identify new real-world datasets that capture different use cases for ESAs and, for the first time, include real-world user queries. Finally, we use LEAKER to evaluate known attacks on our datasets to assess their practical risks and gain insights about the properties that increase or diminish their accuracy.

Category / Keywords: Encrypted Search, Cryptanalysis, Leakage Attacks

Date: received 9 Aug 2021

Contact author: treiber at encrypto cs tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20210816:130623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]