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 }