Authenticated datastructure

Introduction

Goodrich et al 's work on authenticated datastructure provides an interesting tool for designing new and interesting security applications. Authenticated datastructure proves useful in such scenarios that a trusted source wishes to rely on an untrusted party to distribute and manage its data. In addition to responding to normal queries, such datastructure also generates certified "proofs" that ensures the authenticity of the responses, as if they are generated directly from the trusted source.

Model

In more detail, the model of a system using authenticated datastructure is depicted as on the right. It consists of three main components. A source is trusted and is the owner of the data. A third party is untrusted and responsible for managing (storing) data of the source, as well as answering queries from clients. A client sends queries to the third party instead of directly to the source (dotted line). It receives a proof along with the response and verify that this response is in fact authentic, i.e. would be the same response if it queries the source directly.

Normally, the verification process is done as follows. Firstly, the source signs (with its private key) the hash value of the datastructure. Computing such hash values differs among datastructures. Such value along with the source's signature is published and easily obtained by the client. Next, a client issues a query towards the third party. Along with a response is a proof, with which the client performs simple operations to compute hash value of the datastructure and compares it with the signed value it obtained from the trusted source. Intuitively, the proof contains a path and combined hash values of elements in this path should yield the global hash value of the datastructure.

The following remarks can be made from this model.

The source is free from answering queries, which is ideal if its resources (bandwidth and storage) are limited. It only needs to maintain the signed hash value of the datastructure
As far as the client is concerned, the services is provided by third parties, which normally offer higher availability and faster responses. In addition, authenticity can be safely verified with a few calculations. If the check failed, there would be either newer updates or it would indicate faulty (or cheating) third parties
If the data stored at the third party were tampered by any means, the verification process at the client side is guaranteed to fail

An example of authenticated datastructure - Skip list

A modified version of Skip list is introduced in [1] as an authenticated dictionary datastructure. The picture on the right illustrates an example of an authenticated Skip list. A search path, starting from the root node at the top, for value 39 is highlighted with bold lines. A node i has a value Vi and a label Xi

Assume that Pi={x1, x2, ..., xm} is the search path for a value i in the datastructure. Denote h as a well-known cryptographic hash function. The hash value of Pi is calculated as follows:

H(i) = ...h(h(x1,x2),x3)...

Interestingly, the Skip list is designed so that H(i)=H(j) for all i and j. They are all equal to the global hash value of the whole datastructure.

All the source has to do is to sign and publish this global hash value. A certified proof is simply the search path. Due to the collision resistance of hash functions, it is impossible for an attacker to tamper with the data (which effectively changes values of the labels x(i)) and still produce the same hash value.

Why useful?

Authenticated datastructures could be used to answer dictionary-based (or membership) queries, as well as more advanced queries such as in relational databases or graph queries. For the former, it has been used to design efficient public-key revocation system. For the latter, graph and geometric searching applications use this datastructure as the fundamental component.

Main advantages of authenticated datastructures over other naive approaches are:

Verifiable absence of data: Even when a query result indicates the absence of data, i.e. not in the datastructure, a proof is returned and can be verified against the global hash value. In order words, the third party can not remove an element of the datastructure without being noticed (the verification will fail). This property is useful for public-key revocation. In the current implementation of such systems, the CA collects a list of revoked keys, signs it and publish the result. It would require the client to download the entire list and therefore inefficient. Alternatively, following the model in the previous Figure, the CA could sign every single revoked keys, publishes it and lets the third party handle queries. That way, very response also contains signature from the CA and can be easily verified. The problem arises when absence of a key from the list indicates that it is still valid. Exploiting that, the third party can return empty/null value to convince the client that a key is still valid. There is no way for the client to verify that the key is actually not included in the list. This is where authenticated datastructure becomes useful, since every response is accompanied with a proof. Thus, even absence of data can be verified.
Generate O(N^2) verified proof from O(N) elements of data: In some applications, more advanced queries such as range queries or graph queries are needed. Consider a set of data with N elements and the response-space could have up to N^2 elements. Having the trusted source to sign all possible responses and publish them to the third party is an inefficient solution and could be prohibitively expensive. Using authenticated datastructures, different proofs are generated by the third party for difference responses, but they are all verifiable by comparing against the global hash value of the datastructure. This solution is very efficient, because the source only has to sign one value and the third party only needs to store O(N) elements.

References

M.T. Goodrich, R. Tamassia, and A. Schwerin, Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing, DARPA Information Survivability Conference & Exposition II (DISCEX II), IEEE Press, 2001, 68-82
Goodrich's homepage