# Helger Lipmaa's Graph Algorithms Page

While I work in cryptography, I also fancy fast algorithms. In particular, I have done some work on graph algorithms.
The next collection will have actual code for some of them.

## Graph traversal for time-stamping

In the setting of cryptographic time-stamping, one is usually given a prefixed rooted acyclic digraph *G* with
leaves ordered (from left to right) as *1*, *n*. At *i*th round, the value *x*_{i} will
arrive to the database maintainer (usually the time-stamping authority, TSA), whose task is to output the hash value of
graph's root at the end of *n*th round. Here, the hash value of a vertex *i* is equal to *H(j)*, where
*j* is the ordered set of the predecessors of vertex *j*. Of course, the TSA wishes to do that as efficiently as
possible: in particular, she does not want to store all inputs *x*_{i} until end of the round. Another task of
the authority is, durin the *i*th round, to output a list of hash values that has been variously called the head of the
*i*th time-stamp or the *i*th freshness token: this value consists of the minimal number of hash values that are
necessary to verify the dependency between *x*_{i} and the root hash, that were known to the TSA after the
arrival of the *i*th value, *x*_{i}. For example, when *G* is a tree then this freshness token
will be equal to the list of hash values of left siblings of the root path that starts from *i*.

### Interval Time-stamping

A specific family of trees that are optimal for interval time-stamping was lately constructed by Jan Willemson. I published thereafter a paper that described an ``optimal'' tree
traversal algorithm for his trees. The publication together with pseudocode is available from here.

## Fractal graph traversal

In fractal traversal, the setting is somewhat opposite to the time-stamping setting: you still get a prefixed rooted acyclic digraph *G* with leaves ordered (from left to right) as
*1*, *n*, but all *n* values *x*_{i} are precomputed, with *x*_{i} being a hash of some previous values of *x*_{j}'s,
*j≤i*. The value *x*_{1} is published. An authority must then output the values *x*_{n}, *x*_{n-1}, ..., *x*_{1}, in
this order, with one value output by round. The task is to optimize both the (maximum or average) memory usage and amount of work done every round.

This model is explained in some recent papers, like M. Jakobsson, "Fractal Hash Sequence Representation and Traversal", ISIT '02, and D. Coppersmith, M. Jakobsson, "Almost Optimal Hash
Sequence Traversal", FC '02. Both papers are available from Markus's homepage here.

I have implemented the algorithm that was described in ISIT 2002 paper, and it is available here. This code is optimized, but should be treated with a grain of
salt. Especially, it does not use a real implementation of a hash function.

If you want more information, just email me.

This page is maintained by Helger Lipmaa.