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

Nir Bitansky, Akshay Degwekar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 17th International Conference, TCC 2019, Proceedings
EditorsDennis Hofheinz, Alon Rosen
PublisherSpringer
Pages422-450
Number of pages29
ISBN (Print)9783030360290
DOIs
StatePublished - 2019
Event17th International Conference on Theory of Cryptography, TCC 2019 - Nuremberg, Germany
Duration: Dec 1 2019Dec 5 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11891 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Theory of Cryptography, TCC 2019
Country/TerritoryGermany
CityNuremberg
Period12/1/1912/5/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations'. Together they form a unique fingerprint.

Cite this