Paper 2022/678
New Constructions of Collapsing Hashes
Abstract
Collapsing is a post-quantum strengthening of collision resistance, needed to lift many classical results to the quantum setting. Unfortunately, the only existing standard-model proofs of collapsing hashes require LWE. We construct the first collapsing hashes from the quantum hardness of any one of the following problems: - LPN in a variety of low noise or high-hardness regimes, essentially matching what is known for collision resistance from LPN. - Finding cycles on exponentially-large expander graphs, such as those arising from isogenies on elliptic curves. - The "optimal" hardness of finding collisions in *any* hash function. - The *polynomial* hardness of finding collisions, assuming a certain plausible regularity condition on the hash. As an immediate corollary, we obtain the first statistically hiding post-quantum commitments and post-quantum succinct arguments (of knowledge) under the same assumptions. Our results are obtained by a general theorem which shows how to construct a collapsing hash $H'$ from a post-quantum collision-resistant hash function $H$, regardless of whether or not $H$ itself is collapsing, assuming $H$ satisfies a certain regularity condition we call "semi-regularity."
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Published by the IACR in CRYPTO 2022
- Keywords
- hash function quantum collapsing collision resistance
- Contact author(s)
- mzhandry @ gmail com
- History
- 2022-05-31: approved
- 2022-05-30: received
- See all versions
- Short URL
- https://ia.cr/2022/678
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/678, author = {Mark Zhandry}, title = {New Constructions of Collapsing Hashes}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/678}, year = {2022}, url = {https://eprint.iacr.org/2022/678} }