International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys

Authors:
Phillip Rogaway
Download:
URL: http://eprint.iacr.org/2006/281
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21773,
  title={Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys},
  booktitle={IACR Eprint archive},
  keywords={foundations / collision free, collision resistant, hash function},
  url={http://eprint.iacr.org/2006/281},
  note={Vietcrypt 2006 rogaway@cs.ucdavis.edu 13545 received 18 Aug 2006, last revised 31 Jan 2007},
  author={Phillip Rogaway},
  year=2006
}