Abstract
This paper proposes two new public-key cryptosystems semantically secure against adaptive chosen-ciphertext attacks. Inspired from a recently discovered trapdoor technique based on composite-degree residues, our converted encryption schemes are proven, in the random oracle model, secure against active adversaries (NM-CCA2) under the assumptions that the Decision Composite Residuosity and Decision Partial Discrete Logarithms problems are intractable. We make use of specific techniques that differ from Bellare-Rogaway or Fujisaki-Okamoto conversion methods. Our second scheme is specifically designed to be efficient for decryption and could provide an elegant alternative to OAEP.
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
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations Among Notions of Security for Public-Key Encryption Schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: Proc. of the First ACM CCCS, pp. 62–73. ACM Press, New York (1993)
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)
Bleichenbacher, D.: A Chosen Ciphertext Attack against Protocols based on the RSA Encryption Standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998)
Coron, J.S., Naccache, D., Stern, J.: A New Signature Forgery Strategy. In: Crypto 1999, Springer, Heidelberg (1999)
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)
Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Transactions on Information Theory IT–22(6), 644–654 (1976)
Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. In: Proc. of the 23rd STOC. ACM Press, New York (1991)
El Gamal, T.: A PublicKey Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory IT–31(4), 469–472 (1985)
Fujisaki, E., Okamoto, T.: How to Enhance the Security of Public-Key Encryption at Minimum Cost. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 53–68. Springer, Heidelberg (1999)
Goldwasser, S., Micali, S.: Probabilistic Encryption. Journal of Computer and System Sciences 28, 270–299 (1984)
Naccache, D., Stern, J.: A New Cryptosystem based on Higher Residues. In: Proc. of the 5th CCCS, pp. 59–66. ACM Press, New York (1998)
Naor, M., Yung, M.: Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In: Proc. of the 22nd STOC, pp. 427–437. ACM Press, New York (1990)
Okamoto, T., Uchiyama, S.: A New Public Key Cryptosystem as Secure as Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998)
Paillier, P.: Public-Key Cryptosystems Based on Discrete Logarithms Residues. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. 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)
Rackoff, C., Simon, D.R.: Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 433–444. Springer, Heidelberg (1992)
Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
RSA Data Security, Inc. Public Key Cryptography Standards – PKCS, Available from http://www.rsa.com/rsalabs/pubs/PKCS/
Shoup, V., Gennaro, R.: Securing Threshold Cryptosystems against Chosen Ciphertext Attack. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 1–16. Springer, Heidelberg (1998)
Takagi, T.: Fast RSA-Type Cryptosystems Using N-adic Expansion. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 372–384. Springer, Heidelberg (1997)
Tsiounis, Y., Yung, M.: On the Security of El Gamal based Encryption. In: PKC 1998. LNCS. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paillier, P., Pointcheval, D. (1999). Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries. In: Lam, KY., Okamoto, E., Xing, C. (eds) Advances in Cryptology - ASIACRYPT’99. ASIACRYPT 1999. Lecture Notes in Computer Science, vol 1716. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-48000-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66666-0
Online ISBN: 978-3-540-48000-6
eBook Packages: Springer Book Archive