Paper 2018/965
Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries
Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and 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.
Note: full version
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Published elsewhere. Major revision. ACM CCS 2018
- DOI
- 10.1145/3243734.3243864
- Keywords
- encrypted databasevolumeleakageattacksearchable encryption
- Contact author(s)
- marie-sarah lacharite 2015 @ rhul ac uk
- History
- 2018-10-14: received
- Short URL
- https://ia.cr/2018/965
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/965, author = {Paul Grubbs and Marie-Sarah Lacharité and Brice Minaud and Kenny Paterson}, title = {Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/965}, year = {2018}, doi = {10.1145/3243734.3243864}, url = {https://eprint.iacr.org/2018/965} }