Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2018
- Keywords
- hash functionsquantum attacks
- Contact author(s)
- serge fehr @ cwi nl
- History
- 2018-09-23: received
- Short URL
- https://ia.cr/2018/887
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/887,
author = {Serge Fehr},
title = {Classical Proofs for the Quantum Collapsing Property of Classical Hash Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/887},
year = {2018},
url = {https://eprint.iacr.org/2018/887}
}
