[Resource Topic] 2006/281: Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys

Welcome to the resource topic for 2006/281

Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys

Authors: Phillip Rogaway


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.

ePrint: https://eprint.iacr.org/2006/281

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .