Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks

Paul Grubbs 1 Marie-Sarah Lacharité 2 Brice Minaud 3 Kenneth G. Paterson 2
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses. As an introduction to this viewpoint, we first present a general reduction from reconstruction with known queries to PAC learning. Then, we directly address the problem of ϵ-approximate database reconstruction (ϵ-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error ϵ, and is independent of the size of the database, or the number N of possible values of data items. This already goes significantly beyond the state of the art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharité et al. (IEEE S&P 2018). We also study the new problem of ϵ-approximate order reconstruction (ϵ-AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as O(ϵ^-1 log ϵ^-1) uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints. We then show that when an auxiliary distribution is available, ϵ-AOR can be enhanced to achieve ϵ-ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction. Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries. We illustrate this with both concrete attacks for prefix queries and with a general lower bound for all query classes.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01974962
Contributor : Minaud Brice <>
Submitted on : Wednesday, January 9, 2019 - 1:30:52 PM
Last modification on : Thursday, February 7, 2019 - 3:49:12 PM

File

2019-011.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01974962, version 1

Collections

Citation

Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, Kenneth G. Paterson. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. IEEE Symposium on Security and Privacy (S&P) 2019, May 2019, San Francisco, United States. ⟨hal-01974962⟩

Share

Metrics

Record views

341

Files downloads

276