Paper 2020/284

Database Reconstruction Attacks in Two Dimensions

Evangelia Anna Markatou and Roberto Tamassia


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Searchable EncryptionEncrypted DatabasesLeakage-Abuse Attacks
Contact author(s)
evangelia-anna_markatou @ brown edu
2020-03-04: received
Short URL
Creative Commons Attribution


      author = {Evangelia Anna Markatou and Roberto Tamassia},
      title = {Database Reconstruction Attacks in Two Dimensions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/284},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.