Paper 2003/173
Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration
Palash Sarkar
Abstract
We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG based hashing, this technique gives a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general \MD algorithm. Lastly, we describe the design of a new parallel hash algorithm.
Note: Added a section indicating the non-triviality of domain extension to arbitrary length messages under the assumption that the compression function is only collision resistant.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- hash functioncollision resistancecompression functioncomposition principledirected acyclic graph
- Contact author(s)
- palash @ isical ac in
- History
- 2005-12-30: last of 6 revisions
- 2003-08-18: received
- See all versions
- Short URL
- https://ia.cr/2003/173
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/173,
author = {Palash Sarkar},
title = {Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration},
howpublished = {Cryptology {ePrint} Archive, Paper 2003/173},
year = {2003},
url = {https://eprint.iacr.org/2003/173}
}
