Efficient Privacy-preserving Multi-Dimensional Range Query with Hierarchical Hilbert Code-based Tree
Yingru Lu, Xiuxia Tian · 2023
With the development of cloud computing, more enterprises choose the cloud to manage data. However, the issue of privacy has been a stumbling block to cloud computing. Encrypting data, as a powerful way to figure out the problem, masks the semantic information, limiting query performance. This paper presents a multi-dimensional index structure (Hierarchical Hilbert Counting Bloom Filter Tree, HHCBtree) based on hierarchical Hilbert coding system, which supports efficient privacy-preserving multi-dimensional range query. On the one hand, Hierarchical Hilbert coding is used to divide the multi-dimensional space into fine-grained partitions to reduce the redundant data contained in the query results, and then the multi-dimensional data in the partitioned space is converted into hierarchical coding to avoid the disclosure of data order characteristics. On the other hand, the index structure is built on the encoded data, and the traditional tree type index node structure is replaced by the Counting Bronn Filter (Counting Bloom Filter, CBF) to implement secure query over encrypted data. Moreover, an index optimization is proposed to upgrade the efficiency of index traversal. Theoretical analysis shows that the scheme meets the IND-CKA security model, and the experimental results show that the proposed scheme has significantly improved the query efficiency compared with the existing scheme.