Hash Functions in the Dedicated-Key Setting

Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms

Authors:
Mihir Bellare and Thomas Ristenpart

Abstract:
In the dedicated-key setting, one starts with a compression function f:{0,1}^k x {0,1}^{n+d} -> {0,1}^n and builds a family of hash functions H^f:K x M -> {0,1}^n indexed by a key space K. This is different from the more traditional design approach used to build hash functions such as MD5 or SHA-1, in which compression functions and hash functions do not have dedicated key inputs. We explore the benefits and drawbacks of building hash functions in the dedicated-key setting (as compared to the more traditional approach), highlighting several unique features of the former. Should one choose to build hash functions in the dedicated-key setting, we suggest utilizing multi-property-preserving (MPP) domain extension transforms. We analyze seven existing dedicated-key transforms with regard to the MPP goal and propose two simple new MPP transforms.

References:
A preliminary version of this paper appears in International Colloquim on Automata, Languages, and Progamming – ICALP 07, Lecture Notes in Computer Science Vol. 4596, pp. 399–410, L. Arge et al. ed., Springer-Verlag, 2007.

Full Version:
Full version of the paper is available as a pdf.

List of Updates:
October 18, 2007 - A small error in Theorem 5.2 from the paper "Multi-Property-Preserving Hash Domain Extension and the EMD Transform" meant the bounds in Theorem 5.7 and Lemma 5.8 in this paper needed updating. Corrected version posted.
July 12, 2007 - Put up full version. Note that there was an error in the proceedings version of the paper regarding the Enveloped Shoup transform. The full version includes the correction.