Scalable Hash Chain Traversal for Mobile Devices

摘要

Yaron Sella recently proposed a scalable version of Jakobs-son's algorithm to traverse a hash chain of size n. Given the hash chain and a computation limit m (k = m + 1 and b = n~(1/k)), Sella's algorithm traverses the hash chain using a total of kb memory. We improve the memory usage to k(b - 1). Because efficient hash chain traversal algorithms are aimed at devices with severely restricted computation and memory requirements, a reduction by a factor of (b-1)/b is considered to be important. Further, our algorithm matches the memory requirements of Jakobsson's algorithm while still remaining scalable. Sella's algorithm, when scaled to the case of Jakobsson's algorithm, has a memory requirement of about twice that of Jakobsson's.