Paper 2022/678

New Constructions of Collapsing Hashes

Mark Zhandry, NTT Research, Princeton University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.