International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations

Authors:
Nir Bitansky
Akshay Degwekar
Download:
DOI: 10.1007/978-3-030-36030-6_17
Search ePrint
Search Google
Abstract: The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions.We make two contributions to this study: 1.A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way.2.New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.
BibTeX
@article{tcc-2019-29981,
  title={On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={422-450},
  doi={10.1007/978-3-030-36030-6_17},
  author={Nir Bitansky and Akshay Degwekar},
  year=2019
}