Paper 2022/1076

Range Search over Encrypted Multi-Attribute Data

Francesca Falzon, Brown University, University of Chicago
Evangelia Anna Markatou, Brown University
Zachary Espiritu, Brown University
Roberto Tamassia, Brown University

This work addresses expressive queries over encrypted data by presenting the first systematic study of multi-attribute range search on a symmetrically encrypted database outsourced to an honest-but-curious server. Prior work includes a thorough analysis of single-attribute range search schemes (e.g. Demertzis et al. 2016) and a proposed high-level approach for multi-attribute schemes (De Capitani di Vimercati et al. 2021). We first introduce a flexible framework for building secure range search schemes over multiple attributes (dimensions) by adapting a broad class of geometric search data structures to operate on encrypted data. Our framework encompasses widely used data structures such as multi-dimensional range trees and quadtrees, and has strong security properties that we formally prove. We then develop six concrete highly parallelizable range search schemes within our framework that offer a sliding scale of efficiency and security tradeoffs to suit the needs of the application. We evaluate our schemes with a formal complexity and security analysis, a prototype implementation, and an experimental evaluation on real-world datasets.

Note: Full version with proofs.

Available format(s)
Publication info
Published elsewhere. VLDB 2023
encrypted databases range queries searchable encryption
Contact author(s)
francesca_falzon @ brown edu
markatou @ brown edu
zesp @ brown edu
roberto @ tamassia net
2022-12-12: last of 2 revisions
2022-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Francesca Falzon and Evangelia Anna Markatou and Zachary Espiritu and Roberto Tamassia},
      title = {Range Search over Encrypted Multi-Attribute Data},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1076},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.