Paper Info
Title
HybrIDX: New Hybrid Index for Volume-hiding Range Queries in Data Outsourcing Services
Abstract
An encrypted index is a data structure that assisting untrusted servers to provide various query functionalities in the ciphertext domain. Although traditional index designs can prevent 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 challenging 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 volume 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 results outside the enclave in an encrypted multimaps manner. Apart from this novel hybrid index design, we further customize a bulk refresh mechanism to enable accesspattern obfuscation. We formally analyze the security strengths and complete the prototype implementation. Evaluation results demonstrate the feasibility and practicability of our designs.
Year
DOI
Venue
2020
10.1109/ICDCS47774.2020.00014
2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS)
Keywords
DocType
ISSN
volume-hiding range queries,data outsourcing services,encrypted index,data structure,untrusted server,query functionalities,outsourced data,volume-pattern leakage,secure indexes,volume-hiding property,encrypted keyword search,unpredictable range query results,encrypted data,hybrid index framework,query processing,volume-hiding data retrieval,encrypted multimaps manner,hybrid index design,ciphertext domain
Conference
1063-6927
ISBN
Citations 
PageRank 
978-1-7281-7003-9
1
0.35
References 
Authors
0
9
Name
Order
Citations
PageRank
Kui Ren17927355.27
Yu Guo2153.26
Jiaqi Li310.35
Xiaohua Jia44609303.30
Cong Wang54463204.50
Yajin Zhou62382127.03
Sheng Wang7857.78
Ning Cao810.35
Feifei Li92242120.05