### Fractal Hash Sequence Representation and Traversal

Markus Jakobsson

##### Abstract

We introduce a novel amortization technique for computation of consecutive preimages of hash chains, given knowledge of the seed. While all previously known techniques have a memory-times-computational complexity of $O(n)$ per chain element, the complexity of our technique can be upper bounded at $O(log^2 n)$, making it a useful primitive for low-cost applications such as authentication, signatures and micro-payments. Our technique uses a logarithmic number of {\em pebbles} associated with points on the hash chain. The locations of these pebbles are modified over time. Like fractals, where images can be found within images, the pebbles move within intervals and sub-intervals according to a highly symmetric pattern.

Note: A more recent version (with one extra remark, and updated acknowledgements) is available on the author's homepage, www-markus-jakobsson.com

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
amortizationauthenticationhash chainsmart dust
Contact author(s)
mjakobsson @ rsasecurity com
History
2002-03-16: revised
See all versions
Short URL
https://ia.cr/2002/001

CC BY

BibTeX

@misc{cryptoeprint:2002/001,
author = {Markus Jakobsson},
title = {Fractal Hash Sequence Representation and Traversal},
howpublished = {Cryptology ePrint Archive, Paper 2002/001},
year = {2002},
note = {\url{https://eprint.iacr.org/2002/001}},
url = {https://eprint.iacr.org/2002/001}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.