A Secure and Fast Range Query Scheme for Encrypted Multi-Dimensional Data

Introduction

Cloud computing has been widely adopted by individuals, organizations, and businesses (Zeng et al., 2020; Mei et al., 2024). Many applications (Wang et al., 2022) have the capacity to leverage cloud servers for outsourcing their data and services, thereby improving the quality of the services they offer. Thus, the cloud often contains a substantial volume of data, which frequently encompasses sensitive information. Therefore, data security in the cloud becomes a popular research area in both academic and business communities (Zeng et al. 2017; Wu et al., 2020; Wu et al., 2021). To tackle these security concerns, one of the most straightforward approaches is to employ data encryption prior to outsourcing. Nevertheless, traditional encryption methods are difficult to support in some basic data operations, such as data retrieval. Although some new encryption schemes can be used to address the problem of ciphertext search, there exist some constraints.

Agrawal et al. (2004) proposed the first order-preserving encryption (OPE), which aims to incorporate order information of plaintexts into the corresponding ciphertexts. As a result, an OPE scheme is very suitable to solve the problem of ciphertext search. However, many OPE schemes (Agrawal et al., 2004; Peng et al., 2017; Popa et al., 2011; Quan et al., 2018) mainly consider ciphertext search for single-dimensional data (Zhan et al., 2022). Moreover, due to the disclosure of order information caused by OPE schemes, this can be used to accurately deduce the plaintexts (David et al., 2004). Therefore, OPE schemes pose potential data security risks.

Bucketization schemes (Wang et al., 2013; Hore et al., 2004; Hore et al., 2012) can protect order information of ciphertexts and enable ciphertext querying. In a bucketization scheme, all the data is partitioned and placed into different buckets. The data in each bucket are treated as a unit and encrypted. Thus, the order information of ciphertexts in the same bucket can be protected well. Suppose is a bucket and is a queried range. If , all the ciphertexts in are as the results for and finally returned to the data user. To enhance the efficiency of bucketization schemes, researchers have proposed bucketization-based index schemes (Wang et al., 2013; Mei et al., 2018). Nevertheless, the scheme devised by Wang et al. (2013) involves many matrix operations, resulting in low efficiency. The scheme of Mei et al. (2018) exhibits suboptimal performance when dealing with datasets that have non-uniform distributions.

In this paper, we propose a secure and fast range query scheme for encrypted multi-dimensional data, namely SFRQ. In our scheme, a normal R-tree, 0-1 encoding (Gupta et al., 2001), and Bloom filter (Bloom et al., 1970) are used to construct a secure R-tree index. 0-1 encoding and a Bloom filter are used to process the minimum bounding rectangle (MBR) corresponding to each node in the R-tree. This allows each processed MBR to be securely and effectively determined whether the query range intersects with it. The data in each bucket are treated as a unit and encrypted. We conducted a large number of simulation experiments, and the results show that the proposed scheme SFRQ exhibits a high search efficiency. The contributions of this paper are as follows.