[Rog06] Formalizing Human Ignorance

Authors: Phillip Rogaway | Venue: VIETCRYPT 2006 | Source

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

@Inproceedings{VIETCRYPT:Rogaway06,
  author = {Phillip Rogaway},
  title = {Formalizing Human Ignorance},
  pages = {211--228},
  editor = {Phong Q. Nguyen},
  booktitle = {Progress in Cryptology - VIETCRYPT 06: 1st International Conference on Cryptology in Vietnam},
  volume = {4341},
  series = {Lecture Notes in Computer Science},
  address = {Hanoi, Vietnam},
  month = {sep~25--28},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2006},
  doi = {10.1007/11958239_14},
}