Cryptology ePrint Archive: Report 2003/173
Domain Extender for Collision Resistant Hash Functions: Improving Upon Merkle-Damgaard Iteration
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.
Category / Keywords: foundations / hash function, collision resistance, compression function, composition principle, directed acyclic graph
Date: received 18 Aug 2003, last revised 29 Dec 2005
Contact author: palash at isical ac in
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
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.
Version: 20051230:060827 (All versions of this report)
Short URL: ia.cr/2003/173
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]