**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.

**Category / Keywords: **foundations / hash function, parallel algorithm

**Publication Info: **earlier version appeared in the proceedings of Indocrypt 2001.

**Date: **received 12 Mar 2002, last revised 2 Aug 2002

**Contact author: **palash at isical ac in

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

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

**Version: **20020802:112007 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]