---
_id: '14428'
abstract:
- lang: eng
  text: "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.\r\nIn 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.\r\nIndeed, we circumvent the previous
    lower bounds for collision resistance by constructing a simple length-preserving
    RO combiner C˜h1,h2Z1,Z2(M)=h1(M,Z1)⊕h2(M,Z2),where Z1,Z2\r\n 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.\r\nOn
    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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Yevgeniy
  full_name: Dodis, Yevgeniy
  last_name: Dodis
- first_name: Niels
  full_name: Ferguson, Niels
  last_name: Ferguson
- first_name: Eli
  full_name: Goldin, Eli
  last_name: Goldin
- first_name: Peter
  full_name: Hall, Peter
  last_name: Hall
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. Random oracle combiners:
    Breaking the concatenation barrier for collision-resistance. In: <i>43rd Annual
    International Cryptology Conference</i>. Vol 14082. Springer Nature; 2023:514-546.
    doi:<a href="https://doi.org/10.1007/978-3-031-38545-2_17">10.1007/978-3-031-38545-2_17</a>'
  apa: 'Dodis, Y., Ferguson, N., Goldin, E., Hall, P., &#38; Pietrzak, K. Z. (2023).
    Random oracle combiners: Breaking the concatenation barrier for collision-resistance.
    In <i>43rd Annual International Cryptology Conference</i> (Vol. 14082, pp. 514–546).
    Santa Barbara, CA, United States: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-38545-2_17">https://doi.org/10.1007/978-3-031-38545-2_17</a>'
  chicago: 'Dodis, Yevgeniy, Niels Ferguson, Eli Goldin, Peter Hall, and Krzysztof
    Z Pietrzak. “Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance.”
    In <i>43rd Annual International Cryptology Conference</i>, 14082:514–46. Springer
    Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-38545-2_17">https://doi.org/10.1007/978-3-031-38545-2_17</a>.'
  ieee: 'Y. Dodis, N. Ferguson, E. Goldin, P. Hall, and K. Z. Pietrzak, “Random oracle
    combiners: Breaking the concatenation barrier for collision-resistance,” in <i>43rd
    Annual International Cryptology Conference</i>, Santa Barbara, CA, United States,
    2023, vol. 14082, pp. 514–546.'
  ista: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. 2023. Random oracle combiners:
    Breaking the concatenation barrier for collision-resistance. 43rd Annual International
    Cryptology Conference. CRYPTO: Advances in Cryptology, LNCS, vol. 14082, 514–546.'
  mla: 'Dodis, Yevgeniy, et al. “Random Oracle Combiners: Breaking the Concatenation
    Barrier for Collision-Resistance.” <i>43rd Annual International Cryptology Conference</i>,
    vol. 14082, Springer Nature, 2023, pp. 514–46, doi:<a href="https://doi.org/10.1007/978-3-031-38545-2_17">10.1007/978-3-031-38545-2_17</a>.'
  short: Y. Dodis, N. Ferguson, E. Goldin, P. Hall, K.Z. Pietrzak, in:, 43rd Annual
    International Cryptology Conference, Springer Nature, 2023, pp. 514–546.
conference:
  end_date: 2023-08-24
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: Advances in Cryptology'
  start_date: 2023-08-20
date_created: 2023-10-15T22:01:11Z
date_published: 2023-08-09T00:00:00Z
date_updated: 2023-10-16T08:02:11Z
day: '09'
department:
- _id: KrPi
doi: 10.1007/978-3-031-38545-2_17
intvolume: '     14082'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2023/1041
month: '08'
oa: 1
oa_version: Preprint
page: 514-546
publication: 43rd Annual International Cryptology Conference
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031385445'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Random oracle combiners: Breaking the concatenation barrier for collision-resistance'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14082
year: '2023'
...