Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t⩾2t⩾2, our algorithm extends the domain from the set of all n  -bit strings to the set of all ((2t-1)(n-m)+m)((2t-1)(n-m)+m)-bit strings, where m   is the length of the message digest. The associated increase in key length is 2m2m bits for t=2t=2; m(t+1)m(t+1) bits for 3⩽t⩽63⩽t⩽6 and m×(t+⌊log2(t-1)⌋)m×(t+⌊log2(t-1)⌋) bits for t⩾7t⩾7.