Time- and Space-Efficient Aggregate Range Queries over Encrypted Databases
Zachary Espiritu, Evangelia Anna Markatou, Roberto Tamassia · Proceedings on Privacy Enhancing Technologies · 2022
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.