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 memorytimes-computational complexity of O(n) per chain element, the complexity of our technique can be up-per bounded at O(log^2 n), making it a useful primitive for low-cost applications such as authentication, signatures and micro-payments.