A Framework for the Implementation and Comparison of Authenticated Data Structures

Master thesis (2016)

Authors

Contributors

Z. Erkin (mentor)
T. Veugen (mentor)
Department
Cyber Security (EEMCS) (TU Delft)
Copyright: © 2016 Mast, D.E.
Performance Comparison Verification Integrity Authenticated data structures Seqhash Skip list Merkle hash tree
More Info
expand_more

Published Date

08-04-2016

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Cyber Security

Abstract

We present the design and implementation of a general framework that enables implementation and performance comparison of Authenticated Data Structures (ADSs). The framework guarantees that an ADS supports initialization, updates, and verification of queries. In the framework, we implemented the hash tree, skip list, and state-of-the-art SeqHash, and extended their functionality to enable insertion and deletion of a list of entries. We alleviate the task of a programmer by reducing insertion and deletion from three core methods: create, merge, and split. We present the results of the performance comparison. Our implementation of the skip list proves to outperform SeqHash, while supporting the same operations, being more intuitive and easier to implement, and is therefore a good alternative for practical use.