Welcome to the resource topic for
**2002/023**

**Title:**

Almost Optimal Hash Sequence Traversal

**Authors:**
Don Coppersmith, Markus Jakobsson

**Abstract:**

We introduce a novel technique for computation of

consecutive preimages of hash chains. Whereas traditional

techniques have a memory-times-computation complexity of

O(n) per output generated, the complexity of our technique

is only O(log^2 \, n), where n is the length of the chain.

Our solution is based on the same principal amortization principle

as \cite{J01}, and has the same asymptotic behavior as this solution.

However, our solution decreases the real complexity by approximately

a factor of two. Thus, the computational costs of our solution are approximately {1 \over 2} log_2 \, n hash function applications, using only a little more than log_2 \, n storage cells.

A result of independent interest is the lower

bounds we provide for the optimal (but to us unknown)

solution to the problem we study. The bounds show that

our proposed solution is very close to optimal. In particular,

we show that there exists no improvement on our scheme that reduces

the complexity by more than an approximate factor of two.

**ePrint:**
https://eprint.iacr.org/2002/023

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .