A Parallelizable Design Principle for Cryptographic Hash Functions

Palash Sarkar; Paul J.  Schellenberg

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} \to {0, 1}^{m}$ with $n \geq 2 m$ , 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 is . Further, our algorithm is incrementally parallelizable in the following sense : given a digest produced using a binary tree of processors, we show that the same digest can also be produced using a binary tree of 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 function parallel algorithm
Contact author(s): palash @ isical ac in
History: 2002-08-02: revised; 2002-03-12: 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},
      url = {https://eprint.iacr.org/2002/031}
}