Cryptology ePrint Archive: Report 2022/090

Attacks on Encrypted Range Search Schemes in Multiple Dimensions

Francesca Falzon and Evangelia Anna Markatou and Zachary Espiritu and 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.

Category / Keywords: applications / Encrypted Database, Database Reconstruction, Attack

Date: received 24 Jan 2022

Contact author: francesca_falzon at brown edu, markatou at brown edu, zachary_espiritu at brown edu, roberto at tamassia net

Available format(s): PDF | BibTeX Citation

Version: 20220125:072429 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]