International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Parallelizable Design Principle for Cryptographic Hash Functions

Authors:
Palash Sarkar
Paul J. Schellenberg
Download:
URL: http://eprint.iacr.org/2002/031
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2002-11555,
  title={A Parallelizable Design Principle for Cryptographic Hash Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / hash function, parallel algorithm},
  url={http://eprint.iacr.org/2002/031},
  note={earlier version appeared in the proceedings of Indocrypt 2001. palash@isical.ac.in 11901 received 12 Mar 2002, last revised 2 Aug 2002},
  author={Palash Sarkar and Paul J. Schellenberg},
  year=2002
}