Paper 2018/887

Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions

Serge Fehr


Hash functions are of fundamental importance in theoretical and in practical cryptography, and with the threat of quantum computers possibly emerging in the future, it is an urgent objective to understand the security of hash functions in the light of potential future quantum attacks. To this end, we reconsider the collapsing property of hash functions, as introduced by Unruh, which replaces the notion of collision resistance when considering quantum attacks. Our contribution is a formalism and a framework that offers significantly simpler proofs for the collapsing property of hash functions. With our framework, we can prove the collapsing property for hash domain extension constructions entirely by means of decomposing the iteration function into suitable elementary composition operations. In particular, given our framework, one can argue purely classically about the quantum-security of hash functions; this is in contrast to previous proofs which are in terms of sophisticated quantum-information-theoretic and quantum-algorithmic reasoning.

Available format(s)
Publication info
Published by the IACR in TCC 2018
hash functionsquantum attacks
Contact author(s)
serge fehr @ cwi nl
2018-09-23: received
Short URL
Creative Commons Attribution


      author = {Serge Fehr},
      title = {Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/887},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.