Welcome to the resource topic for 2018/965
Title:
Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries
Authors: Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, Kenny Paterson
Abstract:We present attacks that use only the volume of responses to range queries to reconstruct databases. Our focus is on practical attacks that work for large-scale databases with many values and records, without requiring assumptions on the data or query distributions. Our work improves on the previous state-of-the-art due to Kellaris \emph{et al.} (CCS 2016) in all of these dimensions. Our main attack targets reconstruction of database counts and involves a novel graph-theoretic approach. It generally succeeds when R, the number of records, exceeds N^2/2, where N is the number of possible values in the database. For a uniform query distribution, we show that it requires volume leakage from only O(N^2 \log N) queries (cf.\ O(N^4 \log N) in prior work). We present two ancillary attacks. The first identifies the value of a new item added to a database using the volume leakage from fresh queries, in the setting where the adversary knows or has previously recovered the database counts. The second shows how to efficiently recover the ranges involved in queries in an online fashion, given an auxiliary distribution describing the database. Our attacks are all backed with mathematical analyses and extensive simulations using real data.
ePrint: https://eprint.iacr.org/2018/965
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .