Paper 2022/1076
Range Search over Encrypted Multi-Attribute Data
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. VLDB 2023
- Keywords
- encrypted databases range queries searchable encryption
- Contact author(s)
-
francesca_falzon @ brown edu
markatou @ brown edu
zesp @ brown edu
roberto @ tamassia net - History
- 2022-12-12: last of 2 revisions
- 2022-08-18: received
- See all versions
- Short URL
- https://ia.cr/2022/1076
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1076,
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},
url = {https://eprint.iacr.org/2022/1076}
}
