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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.