Paper 2020/1531

Reconstructing with Less: Leakage Abuse Attacks in Two-Dimensions

Evangelia Anna Markatou, Francesca Falzon, William Schor, and Roberto Tamassia


Access and search pattern leakage from range queries are detrimental to the security of encrypted databases, as evidenced by a large body of work on efficient attacks that reconstruct one-dimensional databases. Recently, the first attack from 2D range queries showed that higher-dimensional databases are also in danger. This attack requires complete information for reconstruction. In this paper, we develop reconstructions that require less information. We present an order reconstruction attack that only depends on access pattern leakage, and empirically show that the order allows the attacker to infer the geometry of the underlying data. Notably, this attack also achieves full database reconstruction when the 1D horizontal and vertical projections of the points are dense. We also give an approximate database reconstruction attack that is distribution-agnostic and works with any subset of the possible search pattern, given the order of the database. Finally, we show how knowledge of auxiliary information such as the centroid of a related dataset allows to improve the reconstruction. We support our results with formal analysis and experiments on real-world databases and queries drawn from various distributions.

Available format(s)
Publication info
Preprint. MINOR revision.
Leakage Abuse AttacksRange QueriesSearchable Encryption
Contact author(s)
markatou @ brown edu
ffalzon @ uchicago edu
wschor @ cs brown edu
rt @ cs brown edu
2021-05-20: revised
2020-12-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Evangelia Anna Markatou and Francesca Falzon and William Schor and Roberto Tamassia},
      title = {Reconstructing with Less: Leakage Abuse Attacks in Two-Dimensions},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1531},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.