Files and links (1)
Published, Version of Record (VoR)Open Access (License Unspecified), Open
Conference proceeding
Taking Authenticated Range Queries to Arbitrary Dimensions
CCS'14: PROCEEDINGS OF THE 21ST ACM CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, pp 819-830
01 Jan 2014
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.
Metrics
Details
- Title
- Taking Authenticated Range Queries to Arbitrary Dimensions
- Creators
- Dimitrios Papadopoulos - Boston UniversityStavros Papadopoulos - IntelNikos Triandopoulos - Boston UniversityACM
- Publication Details
- CCS'14: PROCEEDINGS OF THE 21ST ACM CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, pp 819-830
- Publisher
- Assoc Computing Machinery
- Number of pages
- 12
- Grant note
- CNS-1012798; CNS-1012910 / NSF; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000482446400068
- Scopus ID
- 2-s2.0-84910646818
- Other Identifier
- 991020531840504721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Industry collaboration
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Engineering, Electrical & Electronic
- Telecommunications