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

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Vietcrypt 2006
Keywords
collision freecollision resistanthash function
Contact author(s)
rogaway @ cs ucdavis edu
History
2007-02-01: last of 7 revisions
2006-08-19: received
See all versions
Short URL
https://ia.cr/2006/281
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/281,
      author = {Phillip Rogaway},
      title = {Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2006/281},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/281}},
      url = {https://eprint.iacr.org/2006/281}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.