CryptoDB
New Constructions of Collapsing Hashes
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | CRYPTO 2022 |
| Abstract: | Collapsing is the preferred post-quantum security notion for hash functions, 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 certain 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". |
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32202,
title={New Constructions of Collapsing Hashes},
publisher={Springer-Verlag},
author={Mark Zhandry},
year=2022
}