Paper 2022/894

Toward Full Accounting for Leakage Exploitation and Mitigation in Dynamic Encrypted Databases

Lei Xu, Nanjing University of Science and Technology
Anxin Zhou, City University of Hong Kong
Huayi Duan, City University of Hong Kong
Cong Wang, City University of Hong Kong
Qian Wang, Wuhan University
Xiaohua Jia, City University of Hong Kong

Encrypted database draws much attention as it provides privacy-protection services for sensitive data outsourced to a third party. Recent studies show that the security guarantee of encrypted databases are challenged by several leakage-abuse attacks on its search module, and corresponding countermeasures are also proposed. Most of these studies focus on static databases, yet the case for dynamic has not been well investigated. To fill this gap, in this paper, we focus on exploring privacy risks in dynamic encrypted databases and devising effective mitigation techniques. To begin with, we systematically study the exploitable information disclosed during the database querying process, and consider two types of attacks that can recover encrypted queries. The first active attack works by injecting encoded files and correlating file volume information. The second passive attack works by identifying queries’ unique relational characteristics across updates, assuming certain background knowledge of plaintext databases. To mitigate these attacks, we propose a two-layer encrypted database hardening approach, which obfuscates both search indexes and files in a continuous way. As a result, the unique characteristics emerging after data updates can be eliminated constantly. We conduct a series of experiments to confirm the severity of our attacks and the effectiveness of our countermeasures.

Available format(s)
Publication info
Encrypted search Cryptographic databases Leakage abuse attack Defenses
Contact author(s)
xuleicrypto @ gmail com
2022-07-08: approved
2022-07-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lei Xu and Anxin Zhou and Huayi Duan and Cong Wang and Qian Wang and Xiaohua Jia},
      title = {Toward Full Accounting for Leakage Exploitation and Mitigation in Dynamic Encrypted Databases},
      howpublished = {Cryptology ePrint Archive, Paper 2022/894},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.