Authenticated Query Processing

PhD Thesis Proposal Defence


Title: "Authenticated Query Processing"

by

Mr. Stavros Papadopoulos


Abstract:

Under the database outsourcing paradigm, a data owner (e.g., a company or
corporate organization) delegates the administration of its database to a
third-party service provider. Clients direct their queries to the
provider, without contacting the owner. The provider is considered
untrustworthy and may tamper with the results. Authenticated query
processing allows the owner to cryptographically ??mark?? its dataset
through a public-key cryptosystem, and the provider to associate a proof
of correctness with the returned results. This proof is usually generated
by authenticated data structures (ADSs), which are similar to traditional
indices, but they are augmented with cryptographic information. The
clients can efficiently verify the proof using the public key of the
owner.

In this proposal we study two important problems in database outsourcing:
(i) spatial authentication, and (ii) continuous authentication on
relational streams. Regarding the first topic, we introduce the MR-tree, a
space-efficient ADS that supports fast processing and verification of
spatial queries (e.g., ranges, nearest neighbor queries, etc.). The
MR-Tree outperforms the existing solutions on all performance metrics. We
then design the MR*-tree, a modified version of the MR-tree, which
significantly reduces the proof size through a novel embedding technique.
Finally, whereas most ADSs must be constructed and maintained also by the
owner, we outsource the MR- and MR*-tree construction and maintenance to
the server, thus relieving the owner from this computationally intensive
task.

Concerning the second problem, we first address the challenges posed by
stream environments, such as the need for fast structure updating, support
for continuous query processing and authentication, and provision for
temporal completeness. Specifically, in addition to the correctness of
individual results, the client must be able to verify that there are no
missing results in between data updates. Then we present a comprehensive
set of methods covering relational streams, including the following: (i)
We describe REF, a technique that provides result correctness and temporal
completeness but incurs false transmissions, i.e., the server has to
inform the clients whenever there is a data update, even if their results
are not affected. (ii) We propose CADS, which minimizes the processing and
transmission overhead through an elaborate indexing scheme and a virtual
caching mechanism. (iii) We include an analytical study to determine the
optimal indexing granularity. (iv) We extend CADS for the case that the
data distribution changes over time. Finally, we evaluate the
effectiveness of our techniques through extensive experiments.


Date:     		Monday, 22 June 2009

Time:                   3:00pm-5:00pm

Venue:                  Room 3501
 			lifts 25-26

Committee Members:      Prof. Dimitris Papadias (Supervisor)
 			Prof. Mounir Hamdi (Chairperson)
 			Dr. Lei Chen
 			Prof. Dik-Lun Lee


**** ALL are Welcome ****