Paper 2002/124

On Optimal Hash Tree Traversal for Interval Time-Stamping

Helger Lipmaa

Abstract

Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science.

Note: More information available at http://www.tcs.hut.fi/~helger/papers/lip02a/.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Accepted to ISC 2002.
Keywords
analysis of algorithmsimplementation complexityinterval time-stampingLaplace's method for integralstree traversal
Contact author(s)
helger @ tcs hut fi
History
2002-08-22: received
Short URL
https://ia.cr/2002/124
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/124,
      author = {Helger Lipmaa},
      title = {On Optimal Hash Tree Traversal for Interval Time-Stamping},
      howpublished = {Cryptology ePrint Archive, Paper 2002/124},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/124}},
      url = {https://eprint.iacr.org/2002/124}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.