Implementation of an authenticated dictionary with skip lists and commutative hashing

We present the software architecture and implementation of an efficient data structure for dynamically maintaining an authenticated dictionary. The building blocks of the data structure are skip lists and one-way commutative hash functions. We also present the results of a preliminary experiment on the performance of the data structure. Applications of our work include certificate revocation in a public key infrastructure and the publication of data collections on the Internet.