Paper 2014/867

Random-Oracle Uninstantiability from Indistinguishability Obfuscation

Chris Brzuska, Pooya Farshim, and Arno Mittelbach


Assuming the existence of indistinguishability obfuscation (iO), we show that a number of prominent transformations in the random-oracle model are uninstantiable in the standard model. We start by showing that the Encrypt-with-Hash transform of Bellare, Boldyreva and O'Neill (CRYPTO 2007) for converting randomized public-key encryption schemes to deterministic ones is not instantiable in the standard model. To this end, we build on the recent work of Brzuska, Farshim and Mittelbach (CRYPTO 2014) and rely on the existence of iO for circuits or iO for Turing machines to derive uninstantiability for hash functions of a priori bounded polynomial size and arbitrary polynomial size, respectively. The techniques that we use to establish this result are flexible and lend themselves to a number of other transformations such as the classical Fujisaki--Okamoto transform (CRYPTO 1998) and transformations akin to those by Bellare and Keelveedhi (CRYPTO 2011) and Douceur et al. (ICDCS 2002) for obtaining KDM-secure encryption and de-duplication schemes respectively. Our results call for a re-assessment of scheme design in the random-oracle model and highlight the need for new transforms that do not suffer from iO-based attacks.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2015
Random oracleuninstantiabilityindistinguishability obfuscationdeterministic PKEhedged PKEmessage-locked encryptionFujisaki-OkamotoKDM securityUCE.
Contact author(s)
arno mittelbach @ cased de
2015-02-15: last of 2 revisions
2014-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Brzuska and Pooya Farshim and Arno Mittelbach},
      title = {Random-Oracle Uninstantiability from Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/867},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.