Reference: Vietcrypt 2006. LNCS vol. 4341, Springer, pp. 211-228, 2006.
Abstract:
There is a rarely mentioned foundational problem
involving collision-resistant hash-functions:
common constructions are keyless, while formal definitions
are keyed. The discrepancy stems from the fact
that a function H: {0,1}* -> {0,1}n always admits
an efficient collision-finding adversary -- it's just that us humans might
be unable to write it down. We explain a simple way to sidestep
this difficulty that avoids having to key our hash function.
The idea is to state theorems in a way that prescribes
an explicitly given reduction, normally a black-box one.
We illustrate this "constructive-reduction approach"
to collision-resistant hashing using well-known
examples involving digital signatures, pseudorandom
functions, and the Merkle-Damgard construction.
History: First released: 18 Aug 2006. This version: 18 Oct 2006.
Rogaway's home page.