| Title | The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution |
| Publication Type | Conference Paper |
| Year of Publication | 2020 |
| Authors | Kornaropoulos, E. M., Papamanthou, C., Tamassia, R. |
| Conference Name | 2020 IEEE Symposium on Security and Privacy (SP) |
| Keywords | Approximation algorithms, cryptography, data distribution, database management systems, Databases, distribution-agnostic reconstruction attacks, encrypted databases, Encryption, Estimation, first value reconstruction attacks, Histograms, k-nearest-neighbor queries, k-NN attack, known structured encryption schemes, known value reconstruction attacks, leakage-abuse attacks, Measurement, nearest neighbor search, nearest neighbour methods, plaintext values, Predictive Metrics, pubcrawl, query processing, range attack, range queries, search tokens, search-pattern leakage, Servers, skewed query distributions, support size estimator, uniform query distribution, uniformly distributed queries |
| Abstract | Recent foundational work on leakage-abuse attacks on encrypted databases has broadened our understanding of what an adversary can accomplish with a standard leakage profile. Nevertheless, all known value reconstruction attacks succeed under strong assumptions that may not hold in the real world. The most prevalent assumption is that queries are issued uniformly at random by the client. We present the first value reconstruction attacks that succeed without any knowledge about the query or data distribution. Our approach uses the search-pattern leakage, which exists in all known structured encryption schemes but has not been fully exploited so far. At the core of our method lies a support size estimator, a technique that utilizes the repetition of search tokens with the same response to estimate distances between encrypted values without any assumptions about the underlying distribution. We develop distribution-agnostic reconstruction attacks for both range queries and k-nearest-neighbor (k-NN) queries based on information extracted from the search-pattern leakage. Our new range attack follows a different algorithmic approach than state-of-the-art attacks, which are fine-tuned to succeed under the uniformly distributed queries. Instead, we reconstruct plaintext values under a variety of skewed query distributions and even outperform the accuracy of previous approaches under the uniform query distribution. Our new k-NN attack succeeds with far fewer samples than previous attacks and scales to much larger values of k. We demonstrate the effectiveness of our attacks by experimentally testing them on a wide range of query distributions and database densities, both unknown to the adversary. |
| DOI | 10.1109/SP40000.2020.00029 |
| Citation Key | kornaropoulos_state_2020 |
The State of the Uniform: Attacks on Encrypted Databases Beyond the Uniform Query Distribution