Taking authenticated range queries to arbitrary dimensions

Dimitrios Papadopoulos, Stavros Papadopoulos, Nikos Triandopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

36 Scopus citations

Abstract

We study the problem of authenticated multi-dimensional range queries over outsourced databases, where an owner outsources its database to an untrusted server, which maintains it and answers queries to clients. Previous schemes either scale exponentially in the number of query dimensions, or rely on heuristic data structures without provable bounds. Most importantly, existing work requires an exponential, in the database attributes, number of structures to support queries on every possible combination of dimensions in the database. In this paper, we propose the first schemes that (i) scale linearly with the number of dimensions, and (ii) support queries on any set of dimensions with linear in the number of attributes setup cost and storage. We achieve this through an elaborate fusion of novel and existing set-operation sub-protocols. We prove the security of our solutions relying on the q-Strong Bilinear Diffie-Hellman assumption, and experimentally confirm their feasibility.

Original languageEnglish
Title of host publicationProceedings of the ACM Conference on Computer and Communications Security
Pages819-830
Number of pages12
DOIs
StatePublished - 3 Nov 2014
Event21st ACM Conference on Computer and Communications Security, CCS 2014 - Scottsdale, United States
Duration: 3 Nov 20147 Nov 2014

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference21st ACM Conference on Computer and Communications Security, CCS 2014
Country/TerritoryUnited States
CityScottsdale
Period3/11/147/11/14

Keywords

  • Authenticated data structures
  • Authenticated range queries
  • Database outsourcing
  • Delegation of computation

Fingerprint

Dive into the research topics of 'Taking authenticated range queries to arbitrary dimensions'. Together they form a unique fingerprint.

Cite this