| Verifying the integrity, authenticity and freshness of remotely stored data requires new, efficient, and scalable solutions. User expectations for ubiquitous and low-latency access to increasingly large amounts of data are forcing an evolution of the data storage and retrieval model. Data are routinely stored at and retrieved from locations that are not controlled by the original data source. New data verification approaches must similarly evolve to offset the risk of accessing data that has been modified in a manner unintended by the originating source.;This work extends data verification to meet the scalability and efficiency requirements of the evolving outsourced data model. First, the Cloud Authenticated Dictionary (CLAD) handles cloud-scale verification using an authenticated dictionary capable of managing billions of objects. Next, the Authenticated PR-Quadtree (APR-Quad) efficiently processes bulk updates and queries for multidimensional data. Finally, the Multi-producer Authenticated PR-Quadtree (MAPR) publicly authenticates data from multiple producers using a single proof.;Each system consolidates data to amortize verification overhead, yet offsets the costs of managing the resulting large data sets with efficient external memory data structures and algorithms. The systems reduce the I/O, cryptographic overhead, and network complexity that have presented obstacles to verifying data in the evolving storage model. Independent performance evaluations of CLAD and APR-Quad demonstrate an order of magnitude improvement over the state of the art for large data environments, whereas MAPR introduces the first multi-source, multidimensional authenticated approach extended to public verifiability. |
