Query execution assurance for outsourced databases

TLDR

The solution supports arbitrary query types, not just simple selection predicates. The paper proposes and analyzes a method for proving actual query execution in outsourced databases. The method introduces cryptographic proofs that verify each batch of read‑only, compute‑intensive queries, with preliminary support for updates, and is demonstrated in a real‑world data‑mining proof of concept. Experimental results show the approach has reasonable overhead, provides over 95 % assurance with less than 25 % execution time increase, and the security benefits outweigh the costs.

Abstract

In this paper we propose and analyze a method for proofs of actual query execution in an outsourced database framework, in which a client outsources its data management needs to a specialized provider. The solution is not limited to simple selection predicate queries but handles arbitrary query types. While this work focuses mainly on read-only, compute-intensive (e.g. data-mining) queries, it also provides preliminary mechanisms for handling data updates (at additional costs). We introduce query execution proofs; for each executed batch of queries the database service provider is required to provide a strong cryptographic proof that provides assurance that the queries were actually executed correctly over their entire target data set. We implement a proof of concept and present experimental results in a real-world data mining application, proving the deployment feasibility of our solution. We analyze the solution and show that its overheads are reasonable and are far outweighed by the added security benefits. For example an assurance level of over 95% can be achieved with less than 25% execution time overhead.