Cryptology ePrint Archive: Report 2021/1593

Interpreting and Mitigating Leakage-abuse Attacks in Searchable Symmetric Encryption

Lei Xu and Huayi Duan and Anxin Zhou and Xingliang Yuan and Cong Wang

Abstract: Searchable symmetric encryption (SSE) enables users to make confidential queries over always encrypted data while confining information disclosure to pre-defined leakage profiles. Despite the well-understood performance and potentially broad applications of SSE, recent leakage-abuse attacks (LAAs) are questioning its real-world security implications. They show that a passive adversary with certain prior information of a database can recover queries by exploiting the legitimately admitted leakage. While several countermeasures have been proposed, they are insufficient for either security, i.e., handling only specific leakage like query volume, or efficiency, i.e., incurring large storage and bandwidth overhead.

We aim to fill this gap by advancing the understanding of LAAs from a fundamental algebraic perspective. Our investigation starts by revealing that the index matrices of a plaintext database and its encrypted image can be linked by linear transformation. The invariant characteristics preserved under the transformation encompass and surpass the information exploited by previous LAAs. They allow one to unambiguously link encrypted queries with corresponding keywords, even with only partial knowledge of the database. Accordingly, we devise a new powerful attack and conduct a series of experiments to show its effectiveness. In response, we propose a new security notion to thwart LAAs in general, inspired by the principle of local differential privacy (LDP). Under the notion, we further develop a practical countermeasure with tunable privacy and efficiency guarantee. Experiment results on representative real-world datasets show that our countermeasure can reduce the query recovery rate of LAAs, including our own.

Category / Keywords: foundations / Encrypted search, Cryptographic databases, Leakage abuse attack, Linear algebraic

Original Publication (with minor differences): IEEE Transactions on Information Forensics and Security

Date: received 5 Dec 2021

Contact author: xuleicrypto at gmail com, xingliang yuan at monash edu, congwang at cityu edu hk

Available format(s): PDF | BibTeX Citation

Version: 20211206:035407 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]