Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases
Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases
复制标题
DOI：
10.56553/popets-2022-0128
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Zachary Espiritu;Evangelia Anna Markatou;R. Tamassia
中科院分区：
文献类型：
--
作者：
Zachary Espiritu;Evangelia Anna Markatou;R. Tamassia
我们提出了ARQ，一个系统的框架，用于创建加密方案，处理范围聚合查询（总和，最小值，中位数和模式）加密数据集。我们的框架不依赖于可信的硬件或专门的密码原语，如财产保护或同态加密。相反，ARQ将来自明文数据管理社区的结构与现有的结构化加密原语统一起来。我们证明了这样的组合如何产生有效的（和安全的）加密设置中的建设。我们还提出了一系列的域减少技术，可以提高我们的计划对稀疏数据集的空间效率，在小泄漏的成本。作为这项工作的一部分，我们设计和实现了一个新的，开源的，加密的搜索库称为Arca和实现ARQ框架使用这个库，以评估ARQ的实用性。我们在真实世界的数据集上的实验表明，与以前的工作相比，来自ARQ的方案的效率。
We present ARQ, a systematic framework for creating cryptographic schemes that handle range aggregate queries (sum, minimum, median, and mode) over encrypted datasets. Our framework does not rely on trusted hardware or specialized cryptographic primitives such as property-preserving or homomorphic encryption. Instead, ARQ unifies structures from the plaintext data management community with existing structured encryption primitives. We prove how such combinations yield efficient (and secure) constructions in the encrypted setting. We also propose a series of domain reduction techniques that can improve the space efficiency of our schemes against sparse datasets at the cost of small leakage. As part of this work, we designed and implemented a new, open-source, encrypted search library called Arca and implemented the ARQ framework using this library in order to evaluate ARQ’s practicality. Our experiments on real-world datasets demonstrate the efficiency of the schemes derived from ARQ in comparison to prior work.