International Association
for Cryptologic Research

We present the first systematic security evaluation of multi-attribute range search schemes on symmetrically encrypted data. We present four database reconstruction attacks that apply to a broad class of schemes and rely on volume and search pattern leakage. For schemes achieving efficiency by decomposing a query into a small number of subqueries, we further show how to exploit their structure pattern, i.e., co-occurrences of subqueries. We introduce a flexible framework for building secure range search schemes by adapting a broad class of geometric search data structures (including range trees and quadtrees) to operate on encrypted data. We give four concrete range search schemes within our framework that support queries on an arbitrary number of dimensions (attributes) and offer a sliding scale of efficiency and security trade-offs. We provide a security proof for any scheme derived from our framework and a thorough analysis of the leakage of our concrete schemes, characterizing the set of equivalent databases and demonstrating information theoretic limitations on reconstruction attacks. Our attacks are the first that do not require the observation of the access pattern to reconstruct data from range queries in two and higher dimensions. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our schemes and attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.