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^{nm}$ 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.
Metadata
 Available format(s)
 PS
 Category
 Foundations
 Publication info
 Published elsewhere. earlier version appeared in the proceedings of Indocrypt 2001.
 Keywords
 hash functionparallel algorithm
 Contact author(s)
 palash @ isical ac in
 History
 20020802: revised
 20020312: received
 See all versions
 Short URL
 https://ia.cr/2002/031
 License

CC BY
BibTeX
@misc{cryptoeprint:2002/031, author = {Palash Sarkar and Paul J. Schellenberg}, title = {A Parallelizable Design Principle for Cryptographic Hash Functions}, howpublished = {Cryptology ePrint Archive, Paper 2002/031}, year = {2002}, note = {\url{https://eprint.iacr.org/2002/031}}, url = {https://eprint.iacr.org/2002/031} }