Skip to main content

Research Repository

Advanced Search

Securing multi-client range queries over encrypted data

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


Jae Hwan Park

Zeinab Rezaeifar

Changhee Hahn


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
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
Public URL