Paper 2014/863

A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation

Matthew D. Green, Jonathan Katz, Alex J. Malozemoff, and Hong-Sheng Zhou


It is well known that the random oracle model is not sound in the sense that there exist cryptographic systems that are secure in the random oracle model but when instantiated by any family of hash functions become insecure. However, all known separation results require the attacker to send an appropriately crafted message to the challenger in order to break security. Thus, this leaves open the possibility that some cryptographic schemes, such as bit-encryption, are still sound in the random oracle model. In this work we refute this possibility, assuming the existence of indistinguishability obfuscation. We do so in the following way. First, we present a random oracle separation for bit-encryption; namely, we show that there exists a bit-encryption protocol secure in the random oracle model but \emph{completely insecure} when the random oracle is instantiated by any concrete function. Second, we show how to adapt this separation to work for most natural simulation-based and game-based definitions. Our techniques can easily be adapted to other idealized models, and thus we present a \emph{unified approach} to showing separations for most protocols of interest in most idealized models.

Note: - Updated Acknowledgments.

Available format(s)
Publication info
Preprint. MINOR revision.
random oracle modelidealized modelsindistinguishability obfuscation
Contact author(s)
amaloz @ cs umd edu
2014-10-27: last of 2 revisions
2014-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matthew D.  Green and Jonathan Katz and Alex J.  Malozemoff and Hong-Sheng Zhou},
      title = {A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/863},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.