Cryptology ePrint Archive: Report 2003/077

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

Mihir Bellare and Alexandra Boldyreva and Adriana Palacio

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

Category / Keywords: Random oracle model, encryption

Publication Info: Extended abstract appears in Eurocrypt 2004. This is the full version.

Date: received 24 Apr 2003, last revised 9 Mar 2004

Contact author: mihir at cs ucsd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040309:183558 (All versions of this report)

Short URL: ia.cr/2003/077

Discussion forum: Show discussion | Start new discussion