Cryptology ePrint Archive: Report 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.

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