CryptoDB
Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys
| Authors: | |
|---|---|
| Download: | |
| 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
}