Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks

Searchable encryption enables a client to encrypt data, and outsource its storage to an untrusted server, while having the ability to issue search queries over the outsourced data. For efficiency reasons, all practical constructions in this area allow for the host server to learn a limited amount of information on the encrypted data as it processes queries, expressed in the security model by a leakage function. In this talk, I will give a short introduction to searchable encryption, and focus on the implications of very general (and seemingly innocuous) leakage functions.

We will see that the problem of reconstructing the contents of the database from leakage information is closely related to statistical learning theory, specifically VC theory. In particular, we will exhibit attacks that are able to approximately reconstruct the contents of the entire database (in a precise sense) from just the access pattern leakage of range queries, a minimal type of leakage present in all practical constructions today. Along the way, I will present some tools from VC theory, and show how these tools can be used to prove in a natural way that the data complexity of our attacks is independent of the size of the database, or the number of possible values of data items.

Joint work with Paul Grubbs, Marie-Sarah Lacharité, and Kenny Paterson, to appear at S&P 2019.