Paper Info
Title
Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks
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. First, we 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(ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> log ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-1</sup> ) 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. We also show a very general reduction from reconstruction with known or chosen queries to PAC learning.
Year
DOI
Venue
2019
10.1109/SP.2019.00030
2019 IEEE Symposium on Security and Privacy (SP)
Keywords
Field
DocType
encrypted-databases,cryptanalysis
Statistical learning theory,Approximation algorithm,Computer science,Cryptography,Upper and lower bounds,Range query (data structures),Server,Prefix,Encryption,Database
Journal
Volume
ISSN
ISBN
2019
1081-6011
978-1-5386-6661-6
Citations 
PageRank 
References 
3
0.37
0
Authors
4
Name
Order
Citations
PageRank
Paul Grubbs11728.70
Marie-Sarah Lacharité2162.23
Brice Minaud31477.75
Kenneth G. Paterson42683165.56