Paper 2012/613

Resource-Restricted Indifferentiability

Grégory Demay, Peter Gaźi, Martin Hirt, and Ueli Maurer


A major general paradigm in cryptography is the following argument: Whatever an adversary could do in the real world, it could just as well do in the ideal world. The standard interpretation of ``just as well'' is that the translation from the real to the ideal world, usually called a simulator, is achieved by a probabilistic polynomial-time algorithm. This means that a polynomial blow-up of the adversary's time and memory requirements is considered acceptable. In certain contexts this interpretation of ``just as well'' is inadequate, for example if the concrete amount of memory used by the adversary is relevant. The example of Ristenpart et al. (Eurocrypt 2011), for which the original indifferentiability notion introduced by Maurer et al. (Eurocrypt 2004) is shown to be insufficient, turns out to be exactly of this type. It requires a fine-grained statement about the adversary's memory capacity, calling for a generalized treatment of indifferentiability where specific resource requirements can be taken into account by modeling them explicitly. We provide such treatment and employ the new indifferentiability notion to prove lower bounds on the memory required by any simulator in a domain extension construction of a public random function. In particular, for simulators without memory, even domain extension by a single bit turns out to be impossible. Moreover, for the construction of a random oracle from an ideal compression function, memory roughly linear in the length of the longest query is required. This also implies the impossibility of such domain extension in any multi-party setting with potential individual misbehavior by parties (i.e., no central adversary).

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Indifferentiabilitycomposabilityhash functions.
Contact author(s)
peter gazi @ inf ethz ch
2013-03-14: revised
2012-11-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Grégory Demay and Peter Gaźi and Martin Hirt and Ueli Maurer},
      title = {Resource-Restricted Indifferentiability},
      howpublished = {Cryptology ePrint Archive, Paper 2012/613},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.