Range Search over Encrypted Multi-Attribute Data
Range Search over Encrypted Multi-Attribute Data
复制标题
DOI：
10.14778/3574245.3574247
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Francesca Falzon;Evangelia Anna Markatou;Zachary Espiritu;R. Tamassia
中科院分区：
文献类型：
--
作者：
Francesca Falzon;Evangelia Anna Markatou;Zachary Espiritu;R. Tamassia
这项工作通过在对称加密的数据库中，外包到诚实而有趣的服务器上的对称加密的数据库中，对多属性范围搜索进行了首次系统研究来解决对加密数据的表达性查询。先前的工作包括对单属性范围搜索方案的彻底分析（例如Demertzis等人，2016年）以及针对多属性方案的拟议高级方法（de capitani di Vimercati等人，2021年）。我们首先引入一个灵活的框架，以通过调整一类广泛的几何搜索数据结构来在多个属性（维度）上构建安全范围搜索方案，以在加密数据上运行。我们的框架包括广泛使用的数据结构，例如多维范围树和四分之一，并且具有我们正式证明的强大安全性。然后，我们在我们的框架内开发了六个高度可行的范围搜索方案，这些搜索方案提供了效率和安全权衡的滑动规模，以适应应用程序的需求。我们通过正式的复杂性和安全性分析，原型实现以及对现实世界数据集的实验评估来评估我们的方案。
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.