TY - GEN
T1 - Optimal Trade-Off for Merkle Tree Traversal
AU - Berman, Piotr
AU - Karpinski, Marek
AU - Nekrich, Yakov
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali, and Szydlo (Jakobsson et al., 03) and Szydlo (Szydlo, 04). In particular, we show that our algorithm requires 2 logn/log(3) n hash function computations and storage for less than (logn/log(3) n + 1)loglogn + 2 logn 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 O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t ≥ 2. Our algorithm could be of special use in the case when both time and space are limited.
AB - In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali, and Szydlo (Jakobsson et al., 03) and Szydlo (Szydlo, 04). In particular, we show that our algorithm requires 2 logn/log(3) n hash function computations and storage for less than (logn/log(3) n + 1)loglogn + 2 logn 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 O(logn/logt) time and less than O(tlogn/logt) space for any choice of parameter t ≥ 2. Our algorithm could be of special use in the case when both time and space are limited.
UR - http://www.scopus.com/inward/record.url?scp=84904915723&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904915723&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-75993-5_13
DO - 10.1007/978-3-540-75993-5_13
M3 - Conference contribution
AN - SCOPUS:84904915723
SN - 9783540759928
T3 - Communications in Computer and Information Science
SP - 150
EP - 162
BT - E-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers
PB - Springer Verlag
T2 - 2nd International Conference on E-business and Telecommunication Networks, ICETE 2005
Y2 - 3 October 2005 through 7 October 2005
ER -