TY - GEN
T1 - New Constructions of Collapsing Hashes
AU - Zhandry, Mark
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - 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”.
AB - 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”.
UR - http://www.scopus.com/inward/record.url?scp=85141695929&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85141695929&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-15982-4_20
DO - 10.1007/978-3-031-15982-4_20
M3 - Conference contribution
AN - SCOPUS:85141695929
SN - 9783031159817
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 596
EP - 624
BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
A2 - Dodis, Yevgeniy
A2 - Shrimpton, Thomas
PB - Springer Science and Business Media Deutschland GmbH
T2 - 42nd Annual International Cryptology Conference, CRYPTO 2022
Y2 - 15 August 2022 through 18 August 2022
ER -