Implementation of an authenticated dictionary with skip lists and commutative hashing

Author

Goodrich, Michael T. ; Tamassia, Roberto ; Schwerin, Andrew

Author_Institution

Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA

Volume

2

fYear

2001

fDate

2001

Firstpage

68

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

Keywords

Internet; certification; data structures; dictionaries; electronic publishing; list processing; message authentication; public key cryptography; software architecture; Internet; authenticated dictionary; certificate revocation; data collection publication; dynamic dictionary maintenance; efficient data structure; one-way commutative hash functions; performance; public key infrastructure; skip lists; software architecture; Algorithm design and analysis; Application software; Authentication; Computer science; Data structures; Dictionaries; High performance computing; Internet; Public key; Software architecture;

fLanguage

English

Publisher

ieee

Conference_Titel

DARPA Information Survivability Conference & Exposition II, 2001. DISCEX '01. Proceedings

Conference_Location

Anaheim, CA

Print_ISBN

0-7695-1212-7

Type

conf

DOI

10.1109/DISCEX.2001.932160

Filename

932160