Paper 2003/077
An Uninstantiable Random-Oracle-Model Scheme for a Hybrid Encryption Problem
Mihir Bellare, 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.
Metadata
- Available format(s)
-
PDF PS
- Publication info
- Published elsewhere. Extended abstract appears in Eurocrypt 2004. This is the full version.
- Keywords
- Random oracle modelencryption
- Contact author(s)
- mihir @ cs ucsd edu
- History
- 2004-03-09: last of 3 revisions
- 2003-04-25: received
- See all versions
- Short URL
- https://ia.cr/2003/077
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/077,
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},
url = {https://eprint.iacr.org/2003/077}
}