Paper 2020/1531
Reconstructing with Less: Leakage Abuse Attacks in Two-Dimensions
Francesca Falzon and Evangelia Anna Markatou and William Schor and Roberto Tamassia
Abstract
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 in two-dimensions 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 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 responses, given the order of the database. We support our results with experiments on real-world databases with queries drawn from various distributions. Our attack is effective, e.g. we achieve good reconstructions with 15% percent of the queries under a Gaussian distribution.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint. MINOR revision.
- Keywords
- Leakage Abuse AttacksRange QueriesSearchable Encryption
- Contact author(s)
- ffalzon @ uchicago edu,markatou @ brown edu,william_schor @ brown edu,rt @ cs brown edu
- History
- 2021-05-20: revised
- 2020-12-08: received
- See all versions
- Short URL
- https://ia.cr/2020/1531
- License
-
CC BY