Domain extender for collision resistant hash functions: Improving upon MerkleDamgrd iteration
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 yields 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 MerkleDamgrd algorithm.
collision resistance hash function compression function directed acyclic graph composition principle