Toward Practical Verification of Analytic Queries: New Authenticated Data Structures and Cloud-Assisted Techniques

This thesis investigates the problem of enabling users to verify the correctness of analytic query results returned by a cloud, where results may be incorrect (e.g., missing data items that satisfy query conditions) due to various reasons, including malicious behavior by the cloud, unintentional faults (e.g., system compromise or software bugs), or errors during network transmission. Authenticated Data Structures (ADS) have been shown to be a promising solution to this challenge, allowing a cloud service to construct a verification object (VO) that clients can use to validate query results. However, existing approaches largely overlook the computational overhead associated with ADS construction, and they typically assume that the data owner has sufficient resources to build the ADS—an assumption that is often unrealistic in cloud outsourcing scenarios.

To address these limitations, this thesis makes two key contributions. First, we propose a novel ADS called the Intersection and Function Merkle Hash-tree (IFMH-tree), which integrates the Intersection tree (I-tree) and the Merkle hash-tree (MH-tree). We develop both one-signature and multi-signature variants of the IFMH-tree and evaluate their effectiveness in supporting representative analytic queries, including top-k, range, and k-nearest neighbor (kNN) queries. Our results show that the IFMH-tree significantly reduces verification and construction costs compared to existing methods.

Second, we introduce the concept of a Verifiable ADS (V-ADS), which shifts the bulk of ADS construction to the cloud while allowing the data owner to efficiently verify and authorize the structure with minimal computational effort. We present two V-ADS designs—baseline and advanced—and demonstrate through theoretical analysis and experimental evaluation that they substantially reduce the resource burden on data owners without compromising security guarantees.

Together, these contributions advance the state of the art in verifiable query processing by improving both efficiency and practicality, making secure outsourcing of analytic queries more accessible to resource-constrained data owners.

Committee: Ying Cai (major professor), Qi Li, Wallapak Tavanapong, Shawn Dorius and Cassandra Dorius