Securing multi-client range queries over encrypted data

Park, Jae Hwan; Rezaeifar, Zeinab; Hahn, Changhee

Abstract

Order-revealing encryption (ORE) allows secure range query processing over encrypted databases through a publicly accessible comparison function, while keeping other details concealed. Since parameter-hiding ORE (ASIACRYPT 2018) demonstrated improved privacy preservation at the cost of O(n2) comparison operations, where n is the bit length of plaintexts, Lv et al. (ESORICS 2021) introduced an efficient ORE scheme that reduced the comparison operations to O(n), all while accommodating multiple clients. In this paper, we identify a vulnerability in Lv et al.’s ORE scheme, which we refer to as “Query Reusability.” Exploiting this vulnerability, we develop an optimal query recovery attack. According to our experiment on the real-world datasets, our attack can recover a 64-bit plaintext query within a mere 83ms. We then propose msq-ORE, a multi-client secure range query ORE scheme that effectively mitigates the vulnerability while maintaining computational costs comparable to the state-of-the-art ORE scheme. Lastly, our performance analysis results show that the proposed scheme achieves efficacy.

• Journal Article Type: Article
• Acceptance Date: Mar 26, 2024
• Online Publication Date: Apr 26, 2024
• Publication Date: 2024
• Deposit Date: Jun 20, 2024
• Publicly Available Date: Apr 27, 2025
• Journal: Cluster Computing
• Print ISSN: 1386-7857
• Electronic ISSN: 1573-7543
• Publisher: Springer (part of Springer Nature)
• Peer Reviewed: Peer Reviewed
• Volume: 27
• Pages: 9679–9692
• DOI: https://doi.org/10.1007/s10586-024-04472-w
• Public URL: https://uwe-repository.worktribe.com/output/12077469