Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Collision Resistance, Statistical Zero Knowledge, Black box separations

Date: received 10 Jun 2019, last revised 22 Sep 2019

Contact author: nirbitan at tau ac il, degwekarakshay@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190923:004156 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]