Cryptology ePrint Archive: Report 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.

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)

Short URL:

[ Cryptology ePrint archive ]