CryptoDB
A Parallelizable Design Principle for Cryptographic Hash Functions
| Authors: | |
|---|---|
| Download: | |
| 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
}