Optimal Trade-Off for Merkle Tree Traversal

Piotr Berman, Marek Karpinski, Yakov Nekrich

    Research output: Chapter in Book/Report/Conference proceedingConference 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(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.

    Original languageEnglish (US)
    Title of host publicationE-business and Telecommunication Networks - 2nd International Conference, ICETE 2005, Selected Papers
    PublisherSpringer Verlag
    Pages150-162
    Number of pages13
    ISBN (Print)9783540759928
    DOIs
    StatePublished - 2007
    Event2nd International Conference on E-business and Telecommunication Networks, ICETE 2005 - Reading, United Kingdom
    Duration: Oct 3 2005Oct 7 2005

    Publication series

    NameCommunications in Computer and Information Science
    Volume3 CCIS
    ISSN (Print)1865-0929

    Other

    Other2nd International Conference on E-business and Telecommunication Networks, ICETE 2005
    Country/TerritoryUnited Kingdom
    CityReading
    Period10/3/0510/7/05

    All Science Journal Classification (ASJC) codes

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint

    Dive into the research topics of 'Optimal Trade-Off for Merkle Tree Traversal'. Together they form a unique fingerprint.

    Cite this