Robust multi-property combiners for hash functions Journal Article


Author(s): Fischlin, Marc; Lehmann, Anja; Pietrzak, Krzysztof
Article Title: Robust multi-property combiners for hash functions
Affiliation IST Austria
Abstract: A robust combiner for hash functions takes two candidate implementations and constructs a hash function which is secure as long as at least one of the candidates is secure. So far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS they are often required to provide several properties simultaneously. We therefore put forward the notion of robust multi-property combiners and elaborate on different definitions for such combiners. We then propose a combiner that provably preserves (target) collision-resistance, pseudorandomness, and being a secure message authentication code. This combiner satisfies the strongest notion we propose, which requires that the combined function satisfies every security property which is satisfied by at least one of the underlying hash function. If the underlying hash functions have output length n, the combiner has output length 2 n. This basically matches a known lower bound for black-box combiners for collision-resistance only, thus the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the property of being indifferentiable from a random oracle, slightly increasing the output length to 2 n+ω(log n). Moreover, we show how to augment our constructions in order to make them also robust for the one-wayness property, but in this case require an a priory upper bound on the input length.
Keywords: Indifferentiability; Combiner; Hash function
Journal Title: Journal of Cryptology
Volume: 27
Issue 3
ISSN: 1432-1378
Publisher: Springer  
Date Published: 2014-07-01
Start Page: 397
End Page: 428
Sponsor: The first and second author were supported by the Emmy Noether Program Fi 940/2-1 of the German Research Foundation (DFG). The first author is also supported by a Heisenberg grant Fi 940/3-1 of the German Research Foundation (DFG).
DOI: 10.1007/s00145-013-9148-7
Notes: We thank the anonymous reviewers for valuable comments. Most of this work was done while the second author was at Darmstadt University of Technology.
Open access: no
IST Austria Authors
Related IST Austria Work