Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance

Yevgeniy Dodis, Niels Ferguson, Eli Goldin, Peter Hall, Krzysztof Pietrzak

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

Abstract

Suppose we have two hash functions h1 and h2, but we trust the security of only one of them. To mitigate this worry, we wish to build a hash combiner Ch1,h2 which is secure so long as one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash function outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO’06; Pietrzak, Eurocrypt’07; Pietrzak, CRYPTO’08) showed no (noticeably) shorter combiner for collision resistance is possible. In this work, we revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many interesting applications of cryptographic hash functions anyway. We argue the right formulation of the “hash combiner” is to build what we call random oracle (RO) combiners, utilizing stronger assumptions for stronger constructions. Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner C~Z1,Z2h1,h2(M)=h1(M,Z1)⊕h2(M,Z2), where Z1, Z2 are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound. On the negative side, we show that one cannot generically apply the composition theorem to further replace “monolithic” hash functions h1 and h2 by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Finally, despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where h1 and h2 are replaced by iterative Merkle-Damgård hashes applied to a fixed-length compression function. Thus, we can still subvert the concatenation barrier for collision-resistance combiners while utilizing practically small fixed-length components underneath.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II
EditorsHelena Handschuh, Anna Lysyanskaya
PublisherSpringer Science and Business Media Deutschland GmbH
Pages514-546
Number of pages33
ISBN (Print)9783031385445
DOIs
StatePublished - 2023
EventAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings - Santa Barbara, United States
Duration: Aug 20 2023Aug 24 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14082 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings
Country/TerritoryUnited States
CitySanta Barbara
Period8/20/238/24/23

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance'. Together they form a unique fingerprint.

Cite this