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.
Category / Keywords: applications / Searchable Encryption, Encrypted Databases, Leakage-Abuse Attacks, Mitigation Date: received 15 Apr 2019, last revised 18 Sep 2019 Contact author: markatou at brown edu Available format(s): PDF | BibTeX Citation Version: 20190918:131707 (All versions of this report) Short URL: ia.cr/2019/396