Paper 2003/077

An Uninstantiable Random-Oracle-Model Scheme for a Hybrid Encryption Problem

Mihir Bellare, Alexandra Boldyreva, and Adriana Palacio


We present a simple, natural random-oracle (RO) model scheme, for a practical goal, that is uninstantiable, meaning is proven in the RO model to meet its goal yet admits NO standard-model instantiation that meets this goal. The goal in question is IND-CCA-preserving asymmetric encryption which formally captures security of the most common practical usage of asymmetric encryption, namely to transport a symmetric key in such a way that symmetric encryption under the latter remains secure. The scheme is an ElGamal variant, called Hash ElGamal, that resembles numerous existing RO-model schemes, and on the surface shows no evidence of its anomalous properties. More generally, we show that a certain goal, that we call key-verifiable, ciphertext-verifiable IND-CCA-preserving asymmetric encryption, is achievable in the RO model (by Hash ElGamal in particular) but unachievable in the standard model. This helps us better understand the source of the anomalies in Hash ElGamal and also lifts our uninstantiability result from being about a specific scheme to being about a primitive or goal. These results extend our understanding of the gap between the standard and RO models, and bring concerns raised by previous work closer to practice by indicating that the problem of RO-model schemes admitting no secure instantiation can arise in domains where RO schemes are commonly designed.

Available format(s)
Publication info
Published elsewhere. Extended abstract appears in Eurocrypt 2004. This is the full version.
Random oracle modelencryption
Contact author(s)
mihir @ cs ucsd edu
2004-03-09: last of 3 revisions
2003-04-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Alexandra Boldyreva and Adriana Palacio},
      title = {An Uninstantiable Random-Oracle-Model Scheme for a Hybrid Encryption Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2003/077},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.