Towards privacy-preserving multi-dimensional range query over attribute missing data

The Internet of Things continues to develop at a rapid pace, enabling Internet Service Providers (ISPs) to accumulate voluminous data. To fully utilize these data, ISPs want to provide range query services to users. However, data are often collected with missing attributes (i.e., incomplete dataset), which can lead to inaccurate data analysis and decision-making. In addition, ISPs are increasingly outsourcing data and range query services to the cloud with the massive computing power. However, in the absence of full trust in the cloud, data must be encrypted prior to outsourcing, inevitably making query services more difficult on incomplete datasets. Existing schemes either fail to handle datasets with missing attributes or overlook privacy concerns. To address this problem, we propose a scheme for privacy-preserving multi-dimensional range queries over incomplete datasets. Firstly, we use the mapping function to complete the records with missing attributes and add bitstrings to identify the corresponding records. Secondly, a Bitstring-augmented R-tree (BR-tree) is constructed for the complemented multi-dimensional data. Then, we design a privacy-preserving multi-dimensional range intersection determination protocol and a privacy-preserving bitstring comparison protocol to achieve a secure range query using a symmetric homomorphic encryption technique. Then, on the basis of BR-tree and protocols, a scheme for privacy-preserving multi-dimensional range queries on incomplete datasets is proposed. At last, we conducted security analysis and performance evaluation. The results indicate that the scheme can provide safety and effective range queries over attributes with missing data.