Reconstructing with Less: Leakage Abuse Attacks in Two Dimensions

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 attacks that reconstruct one-dimensional databases. Recently, the first attack from 2D range queries showed that higher-dimensional databases are also in danger (Falzon et al. CCS 2020). Their attack requires the access and search pattern of all possible queries. 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 sample of queries, given the search pattern and access pattern leakage of those queries, and the order of the database records. Finally, we show how to improve the reconstruction given knowledge of auxiliary information (e.g., the centroid of a related dataset). We support our results with formal analysis and experiments on real-world databases with queries drawn from various distributions.