Paper 2019/1198

Encrypted Databases: New Volume Attacks against Range Queries

Zichen Gui, Oliver Johnson, and Bogdan Warinschi


We present a range of novel attacks which exploit information about the volume of answers to range queries in encrypted database. Our attacks rely on a strategy which is simple yet robust and effective. We illustrate the robustness of our strategy in a number of ways. We show how i) to adapt the attack for several variations of a basic usage scenario ii) to defeat countermeasures intended to thwart the premise of our basic attack and iii) to perform partial reconstruction of secret data when unique reconstruction is information theoretically impossible. Furthermore, over the state of the art, our attacks require one order of magnitude fewer queries. We show how to improve the attacks even further, under the assumption that some partial information is known to the adversary. We validate experimentally all of our attacks through extensive experiments on real-world medical data and justify theoretically the effectiveness of our strategy for the basic attack scenario. Our new attacks further underscore the difficulty of striking an appropriate functionality-security trade-off for encrypted databases.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ACM CCS 2019
Encrypted databasesvolume leakage attacks
Contact author(s)
zg13988 @ bristol ac uk
o johnson @ bristol ac uk
csxbw @ bristol ac uk
2019-10-15: received
Short URL
Creative Commons Attribution


      author = {Zichen Gui and Oliver Johnson and Bogdan Warinschi},
      title = {Encrypted Databases: New  Volume Attacks against Range Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1198},
      year = {2019},
      doi = {10.1145/3319535.3363210},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.