Authenticated Query Processing

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Authenticated Query Processing"

by

Mr. Stavros PAPADOPOULOS


Abstract:

An increasing number of enterprizes outsource database
functionality to third-party service providers, which answer
queries received from clients. These providers are untrustworthy
and may possibly tamper with the results. Authenticated
query processing enables the clients to verify that the results
indeed originate from the data owner (authenticity), and
include all data satisfying the query (completeness). The
most popular database outsourcing model requires that the data
owner and the service provider construct identical copies of an
authenticated data structure (ADS) on the outsourced data.
The ADS is cryptographically signed by the owner. The service
provider uses the ADS to answer the queries and generate a
verification object, which includes cryptographic
information for establishing the authenticity and completeness of
the results.

In this thesis we present methods for authenticated query
processing in several challenging scenarios. Initially, we devise
efficient solutions for authentication on relational data
streams, where the highly dynamic nature of the data motivates
the need for efficient continuous query processing, fast ADS
updating, and provision for temporal completeness that
allows the clients to verify that there are no missing results in
between updates. Subsequently, we propose sophisticated ADSs for
authenticating spatial queries, such as ranges, nearest
neighbor (NN) queries, etc. Finally, we design the
authenticated multi-step NN framework, which enables
efficient verification of NN query results, in settings where the
distance function is expensive and/or the data dimensionality is
high. We demonstrate the performance superiority of our solutions
against our competitors through extensive analytical and
experimental evaluations.


Date:                   Monday, 22 March 2010

Time:                   3:00pm - 5:00pm

Venue:                  Room 3501
                        lift 25/26

Chairperson:		Prof. Tongyi Zhang (MECH)

Committee Members:      Prof. Dimitris Papadias (Supervisor)
                        Prof. Frederick Lochovsky
                        Prof. Lei Chen
			Prof. Ajay Joneja (IELM)
			Prof. Ada Wai-Chee Fu (CSE, CUHK)


**** ALL are Welcome ****