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 ith round, the value xi 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 nth 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 xi until end of the round. Another task of the authority is, durin the ith round, to output a list of hash values that has been variously called the head of the ith time-stamp or the ith freshness token: this value consists of the minimal number of hash values that are necessary to verify the dependency between xi and the root hash, that were known to the TSA after the arrival of the ith value, xi. 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 xi are precomputed, with xi being a hash of some previous values of xj's, j≤i. The value x1 is published. An authority must then output the values xn, xn-1, ..., x1, 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.

Valid HTML 4.01!