Maple: Scalable multi-dimensional range search over encrypted cloud data with tree-based index

Boyang Wang, Yantian Hou, Ming Li, Haitao Wang, Hui Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

61 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationASIA CCS 2014 - Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security
PublisherAssociation for Computing Machinery, Inc
Pages111-122
Number of pages12
ISBN (Electronic)9781450328005
DOIs
StatePublished - Jun 4 2014
Externally publishedYes
Event9th ACM Symposium on Information, Computer and Communications Security, ASIA CCS 2014 - Kyoto, Japan
Duration: Jun 4 2014Jun 6 2014

Publication series

NameASIA CCS 2014 - Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security

Conference

Conference9th ACM Symposium on Information, Computer and Communications Security, ASIA CCS 2014
Country/TerritoryJapan
CityKyoto
Period6/4/146/6/14

Keywords

  • Encrypted cloud data
  • Multiple dimension
  • Range search
  • Tree structures

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems

Fingerprint

Dive into the research topics of 'Maple: Scalable multi-dimensional range search over encrypted cloud data with tree-based index'. Together they form a unique fingerprint.

Cite this