Cryptology ePrint Archive: Report 2019/011

Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks

Paul Grubbs and Marie-Sarah Lacharité and Brice Minaud and Kenneth G. Paterson

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 $\epsilon$-approximate database reconstruction ($\epsilon$-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error $\epsilon$, 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 $\epsilon$-approximate order reconstruction ($\epsilon$-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 ${\mathcal{O}}(\epsilon^{-1} \log \epsilon^{-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, $\epsilon$-AOR can be enhanced to achieve $\epsilon$-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.

Category / Keywords: applications /

Original Publication (with major differences): IEEE Security and Privacy 2019

Date: received 4 Jan 2019, last revised 5 Jan 2019

Contact author: kenny paterson at rhul ac uk

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2019/011

[ Cryptology ePrint archive ]