Construction of UOWHF: Tree Hashing Revisited.
Palash Sarkar · 2002
We present a binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is 2m bits for t = 2; m(t+1) bits for 3 t 6 and m(t+blog 2 (t 1)c) bits for t 7, where m is the length of the message digest and t 2 is the height of the binary tree. The previously best known binary tree algorithm required a key length expansion of m 2(t 1) bits. We also obtain the lower bound that any binary tree based algorithm must make a key length expansion of 2m bits if t = 2 and a key length expansion of m (t + 1) bits for t 3. Hence for 2 t 6 our algorithm makes optimal key length expansion and for practical sized processor trees the key length expansion is close to the lower bound.