Volume-Hiding Range Searchable Symmetric Encryption for Large-Scale Datasets
Feng Liu, Kaiping Xue, Jinjiang Yang, Jing Zhang, Zixuan Huang, Jian Li, David S. L. Wei
Abstract
Searchable Symmetric Encryption (SSE) is a valuable cryptographic tool that allows a client to retrieve its outsourced data from an untrusted server via keyword search. Initially, SSE research primarily focused on the efficiency-security trade-off. However, in recent years, attention has shifted towards range queries instead of exact keyword searches, resulting in significant developments in the SSE field. Despite the advancements in SSE schemes supporting range queries, many are susceptible to leakage-abuse attacks due to volumetric profile leakage. Although several schemes exist to prevent volume leakage, these solutions prove inefficient when dealing with large-scale datasets. In this paper, we highlight the efficiency-security trade-off for range queries in SSE. Subsequently, we propose a volume-hiding range SSE scheme that ensures efficient operations on extensive datasets. Leveraging the order-weighted inverted index and bitmap structure, our scheme achieves high search efficiency while maintaining the confidentiality of the volumetric profile. To facilitate searching within large-scale datasets, we introduce a partitioning strategy that divides a broad range into disjoint partitions and stores the information in a local binary tree. Through an analysis of the leakage function, we demonstrate the security of our proposed scheme within the ideal/real model simulation paradigm. Our experimental results further validate the practicality of our scheme with real-life large-scale datasets.