TY - GEN
T1 - Maple
T2 - 9th ACM Symposium on Information, Computer and Communications Security, ASIA CCS 2014
AU - Wang, Boyang
AU - Hou, Yantian
AU - Li, Ming
AU - Wang, Haitao
AU - Li, Hui
N1 - Funding Information:
We would like to thank the anonymous reviewers for providing useful suggestions and pointing out the insecurity of our preliminary version based on kd-trees. This work was supported in part by the US National Science Foundation under grant CNS-1218085, NSF of China 61272457, National Project 2012ZX03002003-002, 863 Project 2012AA013102, 111 Project B08038, IRT 1078, FRF K50511010001 and NSF of China 61170251.
Publisher Copyright:
Copyright 2014 ACM.
PY - 2014/6/4
Y1 - 2014/6/4
N2 - Cloud computing promises users massive scale outsourced data storage services with much lower costs than traditional methods. However, privacy concerns compel sensitive data to be stored on the cloud server in an encrypted form. This posts a great challenge for effectively utilizing cloud data, such as executing common SQL queries. A variety of searchable encryption techniques have been proposed to solve this issue; yet efficiency and scalability are still the two main obstacles for their adoptions in real-world datasets, which are multi-dimensional in general. In this paper, we propose a tree-based public-key Multi-Dimensional Range Searchable Encryption (MDRSE) to overcome the above limitations. Specifically, we first formally define the leakage function and security of a tree-based MDRSE. Then, by leveraging an existing predicate encryption in a novel way, our tree-based MDRSE efficiently indexes and searches over encrypted cloud data with multi-dimensional tree structures (i.e., R-trees). Moreover, our scheme is able to protect single-dimensional privacy while previous efficient solutions fail to achieve. Our scheme is selectively secure, and through extensive experimental evaluation on a large-scale real-world dataset, we show the efficiency and scalability of our scheme.
AB - Cloud computing promises users massive scale outsourced data storage services with much lower costs than traditional methods. However, privacy concerns compel sensitive data to be stored on the cloud server in an encrypted form. This posts a great challenge for effectively utilizing cloud data, such as executing common SQL queries. A variety of searchable encryption techniques have been proposed to solve this issue; yet efficiency and scalability are still the two main obstacles for their adoptions in real-world datasets, which are multi-dimensional in general. In this paper, we propose a tree-based public-key Multi-Dimensional Range Searchable Encryption (MDRSE) to overcome the above limitations. Specifically, we first formally define the leakage function and security of a tree-based MDRSE. Then, by leveraging an existing predicate encryption in a novel way, our tree-based MDRSE efficiently indexes and searches over encrypted cloud data with multi-dimensional tree structures (i.e., R-trees). Moreover, our scheme is able to protect single-dimensional privacy while previous efficient solutions fail to achieve. Our scheme is selectively secure, and through extensive experimental evaluation on a large-scale real-world dataset, we show the efficiency and scalability of our scheme.
KW - Encrypted cloud data
KW - Multiple dimension
KW - Range search
KW - Tree structures
UR - http://www.scopus.com/inward/record.url?scp=84984889346&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84984889346&partnerID=8YFLogxK
U2 - 10.1145/2590296.2590305
DO - 10.1145/2590296.2590305
M3 - Conference contribution
AN - SCOPUS:84984889346
T3 - ASIA CCS 2014 - Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security
SP - 111
EP - 122
BT - ASIA CCS 2014 - Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security
PB - Association for Computing Machinery, Inc
Y2 - 4 June 2014 through 6 June 2014
ER -