Dynamic authenticated index structures for outsourced databases

TLDR

Outsourced database systems publish data on remote servers to enable efficient client queries, but untrusted servers necessitate query authentication, and current solutions largely address static scenarios with idealized cryptographic assumptions. The study defines practical cost metrics for ODB systems and explores query freshness as a novel authentication dimension. The authors analytically evaluate and experimentally validate multiple authentication approaches, emphasizing dynamic updates and optimization of the defined cost metrics. The proposed solutions substantially outperform existing methods in both static and dynamic settings.

Abstract

In outsourced database (ODB)systems the database owner publishes its data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or can be compromised, query authentication becomes an essential component of ODB systems. Existing solutions for this problem concentrate mostly on static scenarios and are based on idealistic properties for certain cryptographic primitives. In this work, first we define a variety of essential and practical cost metrics associated with ODB systems. Then, we analytically evaluate a number of different approaches, in search for a solution that best leverages all metrics. Most importantly, we look at solutions that can handle dynamic scenarios, where owners periodically update the data residing at the servers. Finally, we discuss query freshness, a new dimension in data authentication that has not been explored before. A comprehensive experimental evaluation of the proposed and existing approaches is used to validate the analytical models and verify our claims. Our findings exhibit that the proposed solutions improve performance substantially over existing approaches, both for static and dynamic environments.