Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2004 Copyright 2004 Universität Bonn, Institut für Informatik, Abt. V


Optimal Trade-Off for Merkle Tree Traversal
Piotr Berman, Marek Karpinski, Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals along with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali and Szydlo (2003) and Szydlo (2004). In particular we show that our algorithm requires 2 log n/log(3) n hash function evaluations and storage for less than (log n/log(3) n)log log n + 2 log n hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than \Theta(log n/log t) time and less than \Theta(t log n/ log t) space for any choice of parameter t. Our algorithm could be of special use in the case when both time and space are simultaneously limited.

Last Change: 04/05/04 at 13:49:13
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope