Cryptology ePrint Archive: Report 2014/863

A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation

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

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

Category / Keywords: foundations / random oracle model, idealized models, indistinguishability obfuscation

Date: received 20 Oct 2014, last revised 27 Oct 2014

Contact author: amaloz at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: - Updated Acknowledgments.

Version: 20141027:155040 (All versions of this report)

Short URL: ia.cr/2014/863

Discussion forum: Show discussion | Start new discussion