An Efficient and Privacy-Preserving Range Query over Encrypted Cloud Data

The growing power of cloud computing prompts data owners to outsource their databases to the cloud. In order to meet the demand of multi-dimensional data processing in big data era, multi-dimensional range queries, especially over cloud platform, have received extensive attention in recent years. However, since the third-party clouds are not fully trusted, it is popular for the data owners to encrypt sensitive data before outsourcing. It promotes the research of encrypted data retrieval. Nevertheless, most existing works suffer from single-dimensional privacy leakage which would severely put the data at risk. Up to now, although a few existing solutions have been proposed to handle the problem of single-dimensional privacy, they are unsuitable in some practical scenarios due to inefficiency, inaccuracy, and lack of support for diverse data. Aiming at these issues, this paper mainly focuses on the secure range query over encrypted data. We first propose an efficient and private range query scheme for encrypted data based on homomorphic encryption, which can effectively protect data privacy. By using the dual-server model as the framework of the system, we not only achieve multi-dimensional privacy-preserving range query but also innovatively realize similarity search based on MinHash over ciphertext domains. Then we perform formal security analysis and evaluate our scheme on real datasets. The result shows that our proposed scheme is efficient and privacy-preserving. Moreover, we apply our scheme to a shopping website. The low latency demonstrates that our proposed scheme is practical.