Cryptophia's Short Combiner for Collision-Resistant Hash Functions

Arno Mittelbach

Abstract

A combiner for collision-resistant hash functions takes two functions as input and implements a hash function with the guarantee that it is collision-resistant if one of the functions is. It has been shown that such a combiner cannot have short output (Pietrzak, Crypto 2008); that is, its output length is lower bounded by roughly $2n$ if the ingoing functions output $n$-bit hash values. In this paper, we present two novel definitions for hash function combiners that allow to bypass the lower bound: the first is an extended semi-black-box definition. The second is a new game-based, fully black-box definition which allows to better analyze combiners in idealized settings such as the random-oracle model or indifferentiability framework (Maurer, Renner, and Holenstein, TCC 2004). We then present a new combiner which is robust for pseudorandom functions (in the traditional sense), which does not increase the output length of its underlying functions and which is collision-resistant in the indifferentiability setting. Our combiner is particularly relevant in practical scenarios, where security proofs are often given in idealized models, and our combiner, in the same idealized model, yields strong security guarantees while remaining short.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.11th Conference on Applied Cryptography and Network Security (ACNS 2013)
DOI
10.1007/978-3-642-38980-1_9
Keywords
hash functionscombinerscollision resistancemulti-property combiner
Contact author(s)
arno mittelbach @ cased de
History
2014-06-26: revised
See all versions
Short URL
https://ia.cr/2013/210

CC BY

BibTeX

@misc{cryptoeprint:2013/210,
author = {Arno Mittelbach},
title = {Cryptophia's Short Combiner for Collision-Resistant Hash Functions},
howpublished = {Cryptology ePrint Archive, Paper 2013/210},
year = {2013},
doi = {10.1007/978-3-642-38980-1_9},
note = {\url{https://eprint.iacr.org/2013/210}},
url = {https://eprint.iacr.org/2013/210}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.