Paper 2019/686

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

Nir Bitansky and Akshay Degwekar


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Collision ResistanceStatistical Zero KnowledgeBlack box separations
Contact author(s)
nirbitan @ tau ac il
degwekarakshay @ gmail com
2019-09-23: last of 2 revisions
2019-06-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Akshay Degwekar},
      title = {On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/686},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.