Optimal Trade-Off for Merkle Tree Traversal

Piotr Berman; Marek Karpinski; Yakov Nekrich

doi:10.1007/978-3-540-75993-5_13

Optimal Trade-Off for Merkle Tree Traversal

Piotr Berman, Marek Karpinski, Yakov Nekrich

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

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⁽³⁾ n hash function computations and storage for less than (logn/log⁽³⁾ 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.

Original language	English (US)
Title of host publication	E-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers
Publisher	Springer Verlag
Pages	150-162
Number of pages	13
ISBN (Print)	9783540759928
DOIs	https://doi.org/10.1007/978-3-540-75993-5_13
State	Published - 2007
Event	2nd International Conference on E-business and Telecommunication Networks, ICETE 2005 - Reading, United Kingdom Duration: Oct 3 2005 → Oct 7 2005

Publication series

Name	Communications in Computer and Information Science
Volume	3 CCIS
ISSN (Print)	1865-0929

Other

Other	2nd International Conference on E-business and Telecommunication Networks, ICETE 2005
Country/Territory	United Kingdom
City	Reading
Period	10/3/05 → 10/7/05

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1007/978-3-540-75993-5_13

Cite this

@inproceedings{76fd92617f1042eeaf0e930d86625ad1,

title = "Optimal Trade-Off for Merkle Tree Traversal",

abstract = "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.",

author = "Piotr Berman and Marek Karpinski and Yakov Nekrich",

note = "Copyright: Copyright 2014 Elsevier B.V., All rights reserved.; 2nd International Conference on E-business and Telecommunication Networks, ICETE 2005 ; Conference date: 03-10-2005 Through 07-10-2005",

year = "2007",

doi = "10.1007/978-3-540-75993-5_13",

language = "English (US)",

isbn = "9783540759928",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "150--162",

booktitle = "E-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers",

address = "Germany",

}

Berman, P, Karpinski, M & Nekrich, Y 2007, Optimal Trade-Off for Merkle Tree Traversal. in E-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers. Communications in Computer and Information Science, vol. 3 CCIS, Springer Verlag, pp. 150-162, 2nd International Conference on E-business and Telecommunication Networks, ICETE 2005, Reading, United Kingdom, 10/3/05. https://doi.org/10.1007/978-3-540-75993-5_13

Optimal Trade-Off for Merkle Tree Traversal. / Berman, Piotr; Karpinski, Marek; Nekrich, Yakov.
E-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers. Springer Verlag, 2007. p. 150-162 (Communications in Computer and Information Science; Vol. 3 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimal Trade-Off for Merkle Tree Traversal

AU - Berman, Piotr

AU - Karpinski, Marek

AU - Nekrich, Yakov

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 -

Optimal Trade-Off for Merkle Tree Traversal

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this