Privacy-Preserving Multi-Range Queries for Secure Data Outsourcing Services

Authors：Guo, Yu; Xie, Hongcheng; Wang, Mingyue^*; Jia, Xiaohua

Source：IEEE Transactions on Cloud Computing, 2023, 11(3): 2431-2444.

DOI：10.1109/TCC.2022.3208711

• Searchable encryption
• encrypted multi-range search
• privacy-preserving data outsourcing

Encrypted range query schemes that enable range-based searches over encrypted data have become an effective solution for secure data outsourcing services. However, existing schemes are still inadequate on desired functionality and security. Specifically, supporting efficient multi-range queries while hiding the data ordering leakage remains a challenging research problem. Existing works on order-hiding query schemes only work for encrypted single-range search and incur significant computational overhead due to the protection of the ordering information. In this article, we present a privacy-preserving multi-range query scheme that can address the above problems simultaneously. It not only enables efficient multi-range queries over encrypted data but also guarantees the privacy of ordering information. To protect the ordering leakage, our design adopts an Order-hiding Encoding (OHE) scheme to support multi-range obfuscation. In addition, a novel order-hiding K-Dimensional tree (KD-tree) index structure is designed as the core technique underlying our scheme, which accelerates efficient multi-range queries and obfuscates ordering information of encrypted values. Finally, the formal security analysis confirms that our proposed multi-range query scheme is secure in the random oracle model. The extensive experimental results conducted on real-world datasets demonstrate the practicality of our design.