## Cryptology ePrint Archive: Report 2012/613

**Resource-Restricted Indifferentiability**

*Grégory Demay and Peter Gaži and Martin Hirt and Ueli Maurer*

**Abstract: **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).

**Category / Keywords: **foundations / Indifferentiability, composability, hash functions.

**Date: **received 30 Oct 2012, last revised 14 Mar 2013

**Contact author: **peter gazi at inf ethz ch

**Available format(s): **PDF | BibTeX Citation

**Version: **20130314:103630 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]