Cryptology ePrint Archive: Report 2018/887

Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions

Serge Fehr

Abstract: 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.

Category / Keywords: foundations / hash functions, quantum attacks

Original Publication (in the same form): IACR-TCC-2018

Date: received 21 Sep 2018

Contact author: serge fehr at cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20180923:192906 (All versions of this report)

Short URL: ia.cr/2018/887


[ Cryptology ePrint archive ]