Cryptology ePrint Archive: Report 2020/284

Database Reconstruction Attacks in Two Dimensions

Evangelia Anna Markatou and Roberto Tamassia

Abstract: Access and search pattern leakage have been shown to be detrimental to the security of encrypted databases that allow for range queries, as shown by an extensive body of work on efficient attacks that reconstruct one-dimensional databases. We are the first to go beyond one dimension, exploring the threat of access and search pattern leakage in two dimensions. First, we unveil an intrinsic limitation of reconstruction attacks by showing that there can be an exponential number of distinct databases that produce the same access and search pattern leakage. Next, we present attacks that reconstruct (1) the horizontal and vertical order of the points from the access pattern leakage, and (2) the coordinates of the points from the access and search pattern leakage. Our algorithms run in polynomial time and return a linear-size encoding of all databases consistent with the given leakage profile.

Category / Keywords: applications / Searchable Encryption, Encrypted Databases, Leakage-Abuse Attacks

Date: received 3 Mar 2020

Contact author: evangelia-anna_markatou at brown edu

Available format(s): PDF | BibTeX Citation

Version: 20200304:081418 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]