We introduce a novel amortization technique for computation of consecutive preimages of hash chains from a common 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 ''helper values'' associated with points on the hash chain. The locations of these helper values are modified over time. Like fractals, where images can be found within images, the helper values move within intervals and sub-intervals according to a highly symmetric pattern.
Gates 400, or possibly Gates 4B (opposite 490), Monday 2/18/02, 4:30 PM