An increasing number of enterprizes outsource database functionality to third-party service providers, which answer queries received from clients. These providers may be untrustworthy and 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 establish...[ Read more ]

An increasing number of enterprizes outsource database functionality to third-party service providers, which answer queries received from clients. These providers may be untrustworthy and 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.