Paper 2021/1593

Interpreting and Mitigating Leakage-abuse Attacks in Searchable Symmetric Encryption

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


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.

Available format(s)
Publication info
Published elsewhere. MINOR revision.IEEE Transactions on Information Forensics and Security
Encrypted searchCryptographic databasesLeakage abuse attackLinear algebraic
Contact author(s)
xuleicrypto @ gmail com
xingliang yuan @ monash edu
congwang @ cityu edu hk
2021-12-06: received
Short URL
Creative Commons Attribution


      author = {Lei Xu and Huayi Duan and Anxin Zhou and Xingliang Yuan and Cong Wang},
      title = {Interpreting and Mitigating Leakage-abuse Attacks in Searchable Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1593},
      year = {2021},
      doi = {10.1109/TIFS.2021.3128823},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.