New Constructions of Collapsing Hashes

Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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”.

Original languageAmerican English
Title of host publicationAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
EditorsYevgeniy Dodis, Thomas Shrimpton
PublisherSpringer Science and Business Media Deutschland GmbH
Pages596-624
Number of pages29
ISBN (Print)9783031159817
DOIs
StatePublished - 2022
Event42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, United States
Duration: Aug 15 2022Aug 18 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13509 LNCS

Conference

Conference42nd Annual International Cryptology Conference, CRYPTO 2022
Country/TerritoryUnited States
CitySanta Barbara
Period8/15/228/18/22

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'New Constructions of Collapsing Hashes'. Together they form a unique fingerprint.

Cite this