Non-trivial black-box combiners for collision-resistant hash-functions don't exist Conference Paper


Author(s): Pietrzak, Krzysztof
Title: Non-trivial black-box combiners for collision-resistant hash-functions don't exist
Title Series: LNCS
Affiliation
Abstract: A (k, ℓ)-robust combiner for collision-resistant hash-functions is a construction which from ℓ hash-functions constructs a hash-function which is collision-resistant if at least k of the components are collision-resistant. One trivially gets a (k, ℓ)-robust combiner by concatenating the output of any ℓ - k + 1 of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box (k, ℓ)-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06).
Keywords: Black box combiners; Collision resistant hash functions; Hash functions
Conference Title: EUROCRYPT: Theory and Applications of Cryptographic Techniques
Volume: 4515
Conference Dates: May 20-24, 2007
Conference Location: Barcelona, Spain
Publisher: Springer  
Date Published: 2007-06-12
Start Page: 23
End Page: 33
Copyright Statement: © International Association for Cryptology Research 2007.
Sponsor: Supported by DIAMANT, the Dutch national mathematics cluster for discrete interactive and algorithmic algebra and number theory.
DOI: 10.1007/978-3-540-72540-4_2
Open access: no
IST Austria Authors
Related IST Austria Work