Paper 2003/161

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

Ueli Maurer, Renato Renner, and Clemens Holenstein


The goals of this paper are three-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. Second, we prove that indifferentiability is the necessary and sufficient condition on two systems S and T such that the security of any cryptosystem using T as a component is not affected when T is substituted by S. In contrast to 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. Third, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Random-oracle model
Contact author(s)
renner @ inf ethz ch
2003-08-08: received
Short URL
Creative Commons Attribution


      author = {Ueli Maurer and Renato Renner and Clemens Holenstein},
      title = {Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology},
      howpublished = {Cryptology ePrint Archive, Paper 2003/161},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.