** 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.

** Availability: **
pdf or
ps

Rogaway's home page.