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
-
CC BY
BibTeX
@misc{cryptoeprint:2019/686,
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},
url = {https://eprint.iacr.org/2019/686}
}
