The State of the Uniform - Attacks on Encrypted Databases Beyond the Uniform Query Distribution

Explore a 17-minute IEEE conference talk on advanced attacks on encrypted databases that go beyond the uniform query distribution assumption. Delve into novel value reconstruction techniques utilizing search-pattern leakage, a feature present in all known structured encryption schemes. Discover how the presented distribution-agnostic reconstruction attacks for range queries and k-nearest-neighbor (k-NN) queries outperform previous approaches, even under skewed query distributions. Learn about the core support size estimator technique, which enables distance estimation between encrypted values without prior knowledge of the underlying distribution. Examine the effectiveness of these attacks through experimental testing across various query distributions and database densities, providing insights into potential vulnerabilities in encrypted database systems.