Attacks on Encrypted Response-Hiding Range Search Schemes in Multiple Dimensions
Authors: Evangelia Anna Markatou (Brown University), Francesca Falzon (Brown University, University of Chicago), Zachary Espiritu (Brown University), Roberto Tamassia (Brown University)
Volume: 2023
Issue: 4
Pages: 204–223
DOI: https://doi.org/10.56553/popets-2023-0106
Abstract: In this work, we present the first database reconstruction attacks against response-hiding private range search schemes on encrypted databases of arbitrary dimensions. Falzon et al. (VLDB 2022) present a number of range-supporting schemes on arbitrary dimensions exhibiting different security and efficiency trade-offs. Additionally, they characterize a form of leakage, structure pattern leakage, also present in many one-dimensional schemes e.g., Demertzis et al. (SIGMOD 2016) and Faber et al. (ESORICS 2015). We present the first systematic study of this leakage and attack a broad collection of schemes, including schemes that allow the responses to contain false-positives (often considered the gold standard in security). We characterize the information theoretic limitations of a passive persistent adversary. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.
Keywords: leakage-abuse attacks, encrypted databases
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
