Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases
Authors: Zachary Espiritu (Brown University), Evangelia Anna Markatou (Brown University), Roberto Tamassia (Brown University)
Volume: 2022
Issue: 4
Pages: 684–704
DOI: https://doi.org/10.56553/popets-2022-0128
Abstract: 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.
Keywords: structured encryption, encrypted search algorithms, aggregate queries, range queries
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
