Construction of universal one-way hash functions: tree hashing revisited (Q2384401)

A parallel algorithm for extending the domain of a universal one-way hash function is presented. This algorithm is based on a binary tree. For \(t\geq 2\), it extends the domain from the set of all \(n\)-bit strings to the set of all \(((2^t- 1)(n- m)+ m)\)-bit strings, where \(m\) is the length of the message digest. The associated increase in key length is \(2m\) bits for \(t= 2\); \(m(t+ 1)\) bits for \(3\leq t\leq 6\) and \(m(t+ \lfloor\log_2(t- 1)\rfloor)\) bits for \(t\geq 7\).