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 retaining 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. Using this new viewpoint, I will present attacks that approximately reconstruct the contents of an entire database using only the access pattern leakage of range queries, a minimal type of leakage present in all practical constructions today.