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. 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, M., Saxena, N., Kayal, N.: PRIMES is in P. Preprint. August 6 (2002), Available at http://www.cse.iitk.ac.in/news/primality.html
Baek, J., Lee, B., Kim, K.: Secure length-saving ElGamal encryption under the Computational Diffie-Hellman assumption. In: Dawson, E., Clark, A., Boyd, C. (eds.) ACISP 2000. LNCS, vol. 1841, Springer, Heidelberg (2000)
Bellare, M., Boldyreva, A., Palacio, A.: An Uninstantiable Random- Oracle-Model Scheme for a Hybrid-Encryption Problem. Full version of this paper, Available at http://www-cse.ucsd.edu/users/mihir/
Baek, J., Lee, B., Kim, K.: Provably secure length-saving public-key encryption scheme under the computational Diffie-Hellman assumption. ETRI Journal 22(4) (2000)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption: Analysis of the DES modes of operation. In: Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, Los Alamitos (1997)
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: First ACM Conference on Computer and Communications Security, ACM, New York (1993)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multiparty computation. In: Proceedings of the 28th Annual Symposium on the Theory of Computing, ACM, New York (1996)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: Proceedings of the 30th Annual Symposium on the Theory of Computing, ACM, New York (1998)
Coron, J.-S., Handschuh, H., Joye, M., Paillier, P., Pointcheval, D., Tymen, C.: GEM: A Generic Chosen-Ciphertext Secure Encryption Method. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, p. 263. Springer, Heidelberg (2002)
Coron, J.-S., Handschuh, H., Joye, M., Paillier, P., Pointcheval, D., Tymen, C.: Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, p. 17. Springer, Heidelberg (2002)
Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998)
Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. IACR ePrint archive, record 2001/108 (2001), http://eprint.iacr.org/
ElGamal, T.: A public key cryptosystem and signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (1985)
Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Fujisaki, E., Okamoto, T.: Secure Integration of Asymmetric and Symmetric Encryption Schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 537. Springer, Heidelberg (1999)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Science 28, 270–299 (1984)
Goldwasser, S., Taumann, Y.: On the (in)security of the Fiat-Shamir paradigm. In: Proceedings of the 44th Symposium on Foundations of Computer Science, IEEE, Los Alamitos (2003)
Micali, S.: Computationally sound proofs. SIAM Journal on Computing 30(4), 1253–1298 (2000)
Nielsen, J.B.: Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 111. Springer, Heidelberg (2002)
Okamoto, T., Pointcheval, D.: REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, p. 159. Springer, Heidelberg (2001)
Shoup, V.: A proposal for an ISO standard for public key encryption. IACR ePrint archive, record 2001/112 (2001), http://eprint.iacr.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellare, M., Boldyreva, A., Palacio, A. (2004). An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive