New Constructions of Collapsing Hashes

Mark Zhandry

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: 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},
      note = {\url{https://eprint.iacr.org/2022/678}},
      url = {https://eprint.iacr.org/2022/678}
}