Paper 2017/461

Security Definitions For Hash Functions: Combining UCE and Indifferentiability

Daniel Jost and Ueli Maurer


Hash functions are one of the most important cryptographic primitives, but their desired security properties have proven to be remarkably hard to formalize. To prove the security of a protocol using a hash function, nowadays often the random oracle model (ROM) is used due to its simplicity and its strong security guarantees. Moreover, hash function constructions are commonly proven to be secure by showing them to be indifferentiable from a random oracle when using an ideal compression function. However, it is well known that no hash function realizes a random oracle and no real compression function realizes an ideal one. As an alternative to the ROM, Bellare et al. recently proposed the notion of universal computational extractors (UCE). This notion formalizes that a family of functions ``behaves like a random oracle'' for ``real-world'' protocols while avoiding the general impossibility results. However, in contrast to the indifferentiability framework, UCE is formalized as a multi-stage game without clear composition guarantees. As a first contribution, we introduce context-restricted indifferentiability (CRI), a generalization of indifferentiability that allows us to model that the random oracle does not compose generally but can only be used within a well-specified set of protocols run by the honest parties, thereby making the provided composition guarantees explicit. We then show that UCE and its variants can be phrased as a special case of CRI. Moreover, we show how our notion of CRI leads to generalizations of UCE. As a second contribution, we prove that the hash function constructed by Merkle-Damgard satisfies one of the well-known UCE variants, if we assume that the compression function satisfies one of our generalizations of UCE, basing the overall security on a plausible assumption. This result further validates the Merkle-Damgard construction and shows that UCE-like assumptions can serve both as a valid reference point for modular protocol analyses, as well as for the design of hash functions, linking those two aspects in a framework with explicit composition guarantees.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.SCN 2018
IndifferentiabilityUCEhash functionsMerkle-Damgard construction
Contact author(s)
daniel jost @ inf ethz ch
2018-07-11: revised
2017-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Jost and Ueli Maurer},
      title = {Security Definitions For Hash Functions: Combining UCE and Indifferentiability},
      howpublished = {Cryptology ePrint Archive, Paper 2017/461},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.