Paper 2019/396

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

Evangelia Anna Markatou and Roberto Tamassia

Abstract

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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Searchable EncryptionEncrypted DatabasesLeakage-Abuse AttacksMitigation
Contact author(s)
markatou @ brown edu
History
2019-09-18: revised
2019-04-18: received
See all versions
Short URL
https://ia.cr/2019/396
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/396,
      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{https://eprint.iacr.org/2019/396}},
      url = {https://eprint.iacr.org/2019/396}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.