You are looking at a specific version 20190923:004156 of this paper. See the latest version.

Paper 2019/686

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

Nir Bitansky and Akshay Degwekar

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Collision ResistanceStatistical Zero KnowledgeBlack box separations
Contact author(s)
nirbitan @ tau ac il
degwekarakshay @ gmail com
History
2019-09-23: last of 2 revisions
2019-06-11: received
See all versions
Short URL
https://ia.cr/2019/686
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.