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
-
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},
url = {https://eprint.iacr.org/2006/281}
}
