# Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology

## Ueli Maurer and Renato Renner and Clemens Holenstein

```
```The goals of this paper are two-fold. First we introduce and
motivate a generalization of the fundamental concept of the
indistinguishability of two systems, called indifferentiability.
This immediately leads to a generalization of the related notion of
reducibility of one system to another. In contrast to the
conventional notion of indistinguishability, indifferentiability is
applicable in settings where a possible adversary is assumed to have
access to additional information about the internal state of the
involved systems, for instance the public parameter selecting a
member from a family of hash functions.
Second, we state an easily verifiable criterion for a system $\sU$
not to be reducible (according to our generalized definition) to
another system $\sV$ and, as an application, prove that a random
oracle is not reducible to a weaker primitive, called asynchronous
beacon, and also that an asynchronous beacon is not reducible to a
finite-length random string. Each of these irreducibility results
alone implies the main theorem of Canetti, Goldreich, and Halevi
stating that there exist cryptosystems that are secure in the random
oracle model but for which replacing the random oracle by any
implementation leads to an insecure cryptosystem.