Paper 2019/396

Mitigation Techniques for Attacks on 1-Dimensional Databases that Support Range Queries

Evangelia Anna Markatou and Roberto Tamassia


In recent years, a number of attacks have been developed that can reconstruct encrypted one-dimensional databases that support range queries under the persistent passive adversary model. These attacks allow an (honest but curious) adversary (such as the cloud provider) to find the order of the elements in the database and, in some cases, to even reconstruct the database itself. In this paper we present two mitigation techniques to make it harder for the adversary to reconstruct the database. The first technique makes it impossible for an adversary to reconstruct the values stored in the database with an error smaller than $k/2$, for $k$ chosen by the client. By fine-tuning $k$, the user can increase the adversary's error at will. The second technique is targeted towards adversaries who have managed to learn the distribution of the queries issued. Such adversaries may be able to reconstruct most of the database after seeing a very small (i.e. poly-logarithmic) number of queries. To neutralize such adversaries, our technique turns the database to a circular buffer. All known techniques that exploit knowledge of distribution fail, and no technique can determine which record is first (or last) based on access pattern leakage.

Available format(s)
Publication info
Preprint. MINOR revision.
Searchable EncryptionEncrypted DatabasesLeakage-Abuse AttacksMitigation
Contact author(s)
markatou @ brown edu
2019-09-18: revised
2019-04-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Evangelia Anna Markatou and Roberto Tamassia},
      title = {Mitigation Techniques for Attacks on 1-Dimensional Databases that Support Range Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2019/396},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.