Paper 2002/031

A Parallelizable Design Principle for Cryptographic Hash Functions

Palash Sarkar and Paul J. Schellenberg

Abstract

We describe a parallel design principle for hash functions. Given a secure hash function $h:\{0,1\}^n\rightarrow \{0,1\}^m$ with $n\geq 2m$, and a binary tree of $2^t$ processors we show how to construct a secure hash function $h^{*}$ which can hash messages of lengths less than $2^{n-m}$ and a secure hash function $h^{\infty}$ which can hash messages of arbitrary length. The number of parallel rounds required to hash a message of length $L$ is $\lfloor\frac{L}{2^t}\rfloor+t+2$. Further, our algorithm is incrementally parallelizable in the following sense : given a digest produced using a binary tree of $2^t$ processors, we show that the same digest can also be produced using a binary tree of $2^{t^{\prime}}$ $(0\leq t^{\prime}\leq t)$ processors.

Note: Revision prepared on the basis of comments from an anonymous referee.