TY - GEN
T1 - Taking authenticated range queries to arbitrary dimensions
AU - Papadopoulos, Dimitrios
AU - Papadopoulos, Stavros
AU - Triandopoulos, Nikos
PY - 2014/11/3
Y1 - 2014/11/3
N2 - 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.
AB - 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.
KW - Authenticated data structures
KW - Authenticated range queries
KW - Database outsourcing
KW - Delegation of computation
UR - http://www.scopus.com/inward/record.url?scp=84910646818&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84910646818&partnerID=8YFLogxK
U2 - 10.1145/2660267.2660373
DO - 10.1145/2660267.2660373
M3 - Conference contribution
AN - SCOPUS:84910646818
SN - 9781450329576
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 819
EP - 830
BT - Proceedings of the ACM Conference on Computer and Communications Security
T2 - 21st ACM Conference on Computer and Communications Security, CCS 2014
Y2 - 3 November 2014 through 7 November 2014
ER -