An encrypted index is a data structure that assists untrusted servers to provide various query functionalities in the ciphertext domain. Although traditional index designs can pre- vent servers from directly obtaining plaintexts, the confidentiality of outsourced data could still be compromised by observing the volume of different queries. Recent volume attacks have demonstrated the importance of sealing volume-pattern leakage. To this end, several works are made to design secure indexes with the volume-hiding property. However, prior designs only work for encrypted keyword search. Due to the unpredictable range query results, it is difficult to protect the volume-pattern leakage while achieving efficient range queries.
In this paper, for the first time, we define and solve the chal- lenging problem of volume-hiding range queries over encrypted data. Our proposed hybrid index framework, called HybrIDX, allows an untrusted server to efficiently search encrypted data based on order conditions without revealing the exact result size. It resorts to the trusted hardware techniques to assist range query processing by moving the comparison algorithm to trusted SGX enclaves. To enable volume-hiding data retrieval, we propose to host encrypted file blocks outside the enclave in an encrypted volume-hiding structure. Apart from this novel hybrid index framework, we further customize a result caching method to obfuscate the results co-occurrence among different queries. We formally analyze the security strengths and complete the prototype implementation. Evaluation results demonstrate the feasibility and practicability of our designs.