Cryptology ePrint Archive: Report 2002/001

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.

Category / Keywords: foundations / amortization, authentication, hash chain, smart dust

Date: received 2 Jan 2002, last revised 16 Mar 2002

Contact author: mjakobsson at rsasecurity com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Version: 20020316:222224 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]