Efficient Data Authentication in an Environment of Untrusted Third-Party Distributors

In the third-party model for the distribution of data, the trusted data creator or owner provides an untrusted party V with data and integrity verification (IV) items for that data. When a user U gets a subset of the data at D or is already in possession of that subset, U may request from D the IV items that make it possible for U to verify the integrity of its data: D must then provide U with the (hopefully small) number of needed IVs. Most of the published work in this area uses the Merkle tree or variants thereof. For the problem of 2-dimensional range data, the best published solutions require V to store O(n log n) IV items for a database of n items, and allow a user IA to be sent only O(log n) of those IVs for the purpose of verifying the integrity of the data it receives from D (regardless of the size of lA´s query rectangle). For data that is modeled as a 2-dimensional grid (such as GIS or image data), this paper shows that better bounds are possible: The number of IVs stored at D (and the time it takes to compute them) can be brought down to O(n), and the number of IVs sent to IA for verification can be brought down to a constant.