Implementation of an authenticated dictionary with skip lists and commutative hashing

Michael T. Goodrich, Roberto Tamassia, A. Schwerin

2002 · 181 citations · 18 references

Concepts

Abstract

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.

References

18