[Resource Topic] 2003/077: An Uninstantiable Random-Oracle-Model Scheme for a Hybrid Encryption Problem

Welcome to the resource topic for 2003/077

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

Authors: Mihir Bellare, Alexandra Boldyreva, 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.

ePrint: https://eprint.iacr.org/2003/077

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .