Welcome to the resource topic for 2022/090
Title:
Attacks on Encrypted Range Search Schemes in Multiple Dimensions
Authors: Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, Roberto Tamassia
Abstract: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.
ePrint: https://eprint.iacr.org/2022/090
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .