
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2004  Copyright 2004 Universität Bonn, Institut für Informatik, Abt. V  
85255 19.02.2004 
Optimal TradeOff for Merkle Tree Traversal
Piotr Berman, Marek Karpinski, Yakov Nekrich [Download PostScript] [Download PDF]
In this paper we describe optimal tradeoffs 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 tradeoffs 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 