Securing multi-client range queries over encrypted data

Jae Hwan Park

doi:10.1007/s10586-024-04472-w

Return

Securing multi-client range queries over encrypted data

2024-04-26

PRE

Jae Hwan Park

Zeinab Rezaeifar

Changhee Hahn *

DOI：10.1007/s10586-024-04472-w

Original

Original request for help

Save

Abstract

En 中文

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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n<^>2)$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n)$$\end{document}, 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.

Keywords:

Order-revealing encryption

Property-preserving hash

Secure query

Multi-client searchable encryption