Generalized Hash Chain Traversal with Selective Output

Abstract

A hash chain H for a one-way hash function h(.) is a sequence of hash values (v(0), v(1),..., v(n)), where v(0) is a public value, v,, a secret value, and v, = h(vi+i). A hash chain traversal algorithm T computes and outputs the hash chain H, returning v, in time period (called round) i for 1 <= i <= n. While previous hash chain traversal algorithms were designed to output all hash values v(i) (1 <= i <= n) in order, there are applications where every,n-th hash value (i.e., v(m), v(2m), v(3m,)...,) is required to be output. We introduce a hash chain traversal algorithm that selectively outputs every m-th hash value efficiently. The main technique is a transformation from a hash chain traversal algorithm outputting every hash value into that outputting every m-th hash value. Compared with the direct use of previous hash chain traversal algorithms, our proposed method requires less memory storages and computatibnal costs.