Abstract
We build new RSA-based encryption schemes secure against adaptive chosen-ciphertext attack (CCA-secure) without random oracles. To do this, we first define a new general RSA-related assumption, the Oracle RSA-type assumption, and give two specific instances of this assumption. Secondly, we express RSA-based encryption schemes as tag-based encryption schemes (TBE), where the public exponent is the tag. We define selective-tag weak chosen-ciphertext security for the special RSA-based case and call it selective-exponent weak chosen-ciphertext security. RSA-based schemes secure in this sense can be used as a building block for the construction of chosen-ciphertext secure encryption schemes using a previous technique. We build two concrete CCA-secure encryption schemes whose security is based on the two concrete Oracle RSA-type assumptions respectively, and whose efficiency is comparable to the most efficient CCA-secure schemes known.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdalla, M., Bellare, M., Rogaway, P.: DHIES: An Encryption Scheme Based on the Diffie-Hellman Problem (2001), http://www.cs.ucsd.edu/users/mihir/papers/dhaes.pdf
Abdalla, M., Bellare, M., Rogaway, P.: The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 143–158. Springer, Heidelberg (2001)
Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption - How to Encrypt with RSA. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)
Boneh, D., Boyen, X.: Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Boneh, D., Boyen, X., Shacham, H.: Short Group Signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-Ciphertext Security from Identity-Based Encryption, Journal submission (2005), http://crypto.stanford.edu/~dabo/papers/ccaibejour.pdf
Boneh, D., Katz, J.: Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 87–103. Springer, Heidelberg (2005)
Canetti, R., Halevi, S., Katz, J.: Chosen-Ciphertext Security from Identity-Based Encryption. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004)
Carter, J.L., Wegman, M.N.: Universal Classes of Hash Functions. JCSS 18(2), 143–154 (1979)
Catalano, D., Gennaro, R., Howgrave-Graham, N., Nguyen, P.Q.: Paillier’s cryptosystem revisited. In: CCS, pp. 206–214. ACM Press, New York (2001)
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, pp. 13–25. Springer, Heidelberg (1998)
Cramer, R., Shoup, V.: Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
Dodis, Y., Gennaro, R., Håstad, J., Krawczyk, H., Rabin, T.: Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 494–510. Springer, Heidelberg (2004)
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: STOC. ACM Press, New York (1991)
Elkind, E., Sahai, A.: A Unified Methodology For Constructing Public-Key Encryption Schemes Secure Against Adaptive Chosen-Ciphertext Attack. Cryptology ePrint Archive, Report 2002/042 (2002), http://eprint.iacr.org/
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random Generation from One-Way Functions. In: STOC, pp. 12–24. ACM Press, New York (1989)
Kiltz, E.: Chosen-Ciphertext Security from Tag-Based Encryption. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 581–600. Springer, Heidelberg (2006)
Kurosawa, K., Desmedt, Y.: A New Paradigm of Hybrid Encryption Scheme. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 426–442. Springer, Heidelberg (2004)
MacKenzie, P.D., Reiter, M.K., Yang, K.: Alternatives to Non-malleability: Definitions, Constructions, and Applications (Extended Abstract). In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 171–190. Springer, Heidelberg (2004)
Naor, M., Yung, M.: Universal One-Way Hash Functions and their Cryptographic Applications. In: STOC, pp. 33–43 (1989)
Naor, M., Yung, M.: Public-Key Cryptosystems Provably Secure Against Chosen Ciphertext Attacks. In: STOC, pp. 427–437. ACM Press, New York (1990)
Nevelsteen, W., Preneel, B.: Software Performance of Universal Hash Functions. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 24–41. Springer, Heidelberg (1999)
Pointcheval, D.: New Public Key Cryptosystems Based on the Dependent-RSA Problems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 239–254. Springer, Heidelberg (1999)
Scott, M.: Faster Pairings using an Elliptic Curve with an Efficient Endomorphism. Cryptology ePrint Archive, Report 2005/252 (2005), http://eprint.iacr.org/
Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, Cambridge (2005), Available at: http://shoup.net/ntb/
Stinson, D.R.: Universal Hashing and Authentication Codes. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 74–85. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brown, J., Nieto, J.M.G., Boyd, C. (2006). Efficient CCA-Secure Public-Key Encryption Schemes from RSA-Related Assumptions. In: Barua, R., Lange, T. (eds) Progress in Cryptology - INDOCRYPT 2006. INDOCRYPT 2006. Lecture Notes in Computer Science, vol 4329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11941378_13
Download citation
DOI: https://doi.org/10.1007/11941378_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49767-7
Online ISBN: 978-3-540-49769-1
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science