1. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage 2018 Attacks EncryptedDatabases Oakland
    Marie-Sarah Lacharite, Brice Minaud and Kenneth G. Paterson
    [View PDF on pure.royalholloway.ac.uk]
    [Show BibTex Citation]

    author={M. {Lacharité} and B. {Minaud} and K. G. {Paterson}},
    booktitle={2018 IEEE Symposium on Security and Privacy (SP)},
    title={Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage},
    keywords={cryptography;database management systems;medical administrative data processing;query processing;dense dataset;target dataset;real-world medical data sets;distinct plaintext values;expected number;fully negating encryption;multiple recent encryption schemes;rank information;specific setting;generic setting;persistent adversaries;database encryption schemes;range query leakage;encrypted data;reconstruction attacks;snapshot attacks;Servers;Encryption;Indexes;Image reconstruction;privacy;cryptanalysis;encrypted database},

We analyse the security of database encryption schemes supporting range queries against persistent adversaries. The bulk of our work applies to a generic setting, where the adversary’s view is limited to the set of records matched by each query (known as access pattern leakage). We also consider a more specific setting where rank information is also leaked, which is inherent inherent to multiple recent encryption schemes supporting range queries. We provide three attacks.

First, we consider full reconstruction, which aims to recover the value of every record, fully negating encryption. We show that for dense datasets, full reconstruction is possible within an expected number of queries N log N + O(N), where N is the number of distinct plaintext values. This directly improves on a quadratic bound in the same setting by Kellaris et al. (CCS 2016).

Second, we present an approximate reconstruction attack recovering all plaintext values in a dense dataset within a constant ratio of error, requiring the access pattern leakage of only O(N) queries.

Third, we devise an attack in the common setting where the adversary has access to an auxiliary distribution for the target dataset. This third attack proves highly effective on age data from real-world medical data sets. In our experiments, observing only 25 queries was sufficient to reconstruct a majority of records to within 5 years.

In combination, our attacks show that current approaches to enabling range queries offer little security when the threat model goes beyond snapshot attacks to include a persistent server-side adversary.