Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys

Author: Phillip Rogaway

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.