Tree-based multi-dimensional range search on encrypted data with enhanced privacy

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

Research output: Chapter in Book/Report/Conference proceedingChapter

6 Scopus citations

Abstract

With searchable encryption, a data user is able to perform meaningful search on encrypted data stored in the public cloud without revealing data privacy. Besides handling simple queries (e.g., keyword queries), complex search functions, such as multi-dimensional (conjunctive) range queries, have also been studied in several approaches to provide search functionalities over multi-dimensional data. However, current works supporting multi-dimensional range queries either only achieve linear search complexity or reveal additional private information to the public cloud. In this paper, we propose a tree-based symmetric-key searchable encryption to support multi-dimensional range queries on encrypted data. Besides protecting data privacy, our proposed scheme is able to achieve faster-than-linear search, query privacy and single-dimensional privacy simultaneously compared to previous solutions. More specifically, we formally define the security of our proposed scheme, prove that it is selectively secure, and demonstrate its faster-than-linear efficiency with experiments over a real-world dataset.

Original languageEnglish (US)
Title of host publicationLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
PublisherSpringer-Verlag
Pages374-394
Number of pages21
DOIs
StatePublished - 2015
Externally publishedYes

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume152
ISSN (Print)1867-8211

Keywords

  • Encrypted data
  • Multi-dimensional range search

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Tree-based multi-dimensional range search on encrypted data with enhanced privacy'. Together they form a unique fingerprint.

Cite this