Cryptology ePrint Archive: Report 2006/281

Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys

Phillip Rogaway

Abstract: There is a rarely mentioned foundational problem involving collision-resistant hash-functions: common constructions are keyless, but 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 algorithm, it's just that us human beings might be unable to write the program down. We explain a simple way to sidestep this difficulty that avoids having to key our hash functions. The idea is to state theorems in a way that prescribes an explicitly-given reduction, normally a black-box one. We illustrate this approach using well-known examples involving digital signatures, pseudorandom functions, and the Merkle-Damgard construction.

Category / Keywords: foundations / collision free, collision resistant, hash function

Publication Info: Vietcrypt 2006

Date: received 18 Aug 2006, last revised 31 Jan 2007

Contact author: rogaway at cs ucdavis edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20070201:051823 (All versions of this report)

Short URL: ia.cr/2006/281

Discussion forum: Show discussion | Start new discussion