New Constructions of Collapsing Hashes

Mark Zhandry

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

2 Scopus citations

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 languageEnglish (US)
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

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

All Science Journal Classification (ASJC) codes

  • 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