Skip to main content
Springer Nature Link
Log in

Practical Security in Public-Key Cryptography

  • Conference paper
  • First Online:
Information Security and Cryptology — ICISC 2001 (ICISC 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2288))

Included in the following conference series:

Abstract

Since the appearance of public-key cryptography in Diffie- Hellman seminal paper, many schemes have been proposed, but many have been broken. Indeed, for many people, the simple fact that a cryptographic algorithm withstands cryptanalytic attacks for several years is considered as a kind of validation. But some schemes took a long time before being widely studied, and maybe thereafter being broken. A much more convincing line of research has tried to provide “provable” security for cryptographic protocols, in a complexity theory sense: if one can break the cryptographic protocol, one can “efficiently” solve the underlying problem. Unfortunately, very few practical schemes can be proven in this so-called “standard model” because such a security level rarely meets with efficiency. Moreover, for a long time the security proofs have only been performed in an asymptotic framework, which provides some confidence in the scheme but for very huge parameters only, and thus for unpractical schemes.

A recent trend consists in providing very efficient reductions, with a practical meaning: with usual parameters (such as 1024-bit RSA moduli) the computational cost of any attack is actually 272, given the state of the art about classical problems (e.g. integer factoring).

In this paper, we focus on practical schemes together with their “reductionist” security proofs. We cover the two main goals that public-key cryptography is devoted to solve: authentication with digital signatures and confidentiality with public-key encryption schemes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. Abdalla, M. Bellare, and P. Rogaway. The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES. In CT-RSA’ 01, LNCS 2020, pages 143–158. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  2. American National Standards Institute. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm. ANSI X9.62-1998. January 1999.

    Google Scholar 

  3. M. Bellare. Practice-Oriented Provable Security. In ISW’ 97, LNCS 1396. Springer-Verlag, Berlin, 1997.

    Google Scholar 

  4. M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations among Notions of Security for Public-Key Encryption Schemes. In Crypto’ 98, LNCS 1462, pages 26–45. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  5. M. Bellare and P. Rogaway. Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols. In Proc. of the 1st CCS, pages 62–73. ACM Press, New York, 1993.

    Google Scholar 

  6. M. Bellare and P. Rogaway. Optimal Asymmetric Encryption-How to Encrypt with RSA. In Eurocrypt’ 94, LNCS 950, pages 92–111. Springer-Verlag, Berlin, 1995.

    Chapter  Google Scholar 

  7. M. Bellare and P. Rogaway. The Exact Security of Digital Signatures-How to Sign with RSA and Rabin. In Eurocrypt’ 96, LNCS 1070, pages 399–416. Springer-Verlag, Berlin, 1996.

    Google Scholar 

  8. D. Bleichenbacher. A Chosen Ciphertext Attack against Protocols based on the RSA Encryption Standard PKCS #1. In Crypto’ 98, LNCS 1462, pages 1–12. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  9. D. R. L. Brown. The Exact Security of ECDSA. January 2001. Available from http://grouper.ieee.org/groups/1363/.

  10. B. Chor and R. L. Rivest. A Knapsack Type Public Key Cryptosystem based on Arithmetic in Finite Fields. In Crypto’ 84, LNCS 196, pages 54–65. Springer-Verlag, Berlin, 1985.

    Google Scholar 

  11. J.-S. Coron. On the Exact Security of Full-Domain-Hash. In Crypto’ 00, LNCS 1880, pages 229–235. Springer-Verlag, Berlin, 2000.

    Google Scholar 

  12. R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Crypto’ 98, LNCS 1462, pages 13–25. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  13. R. Cramer and V. Shoup. Signature Scheme based on the Strong RSA Assumption. In Proc. of the 6th CCS, pages 46–51. ACM Press, New York, 1999.

    Google Scholar 

  14. W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22(6):644–654, November 1976.

    Article  MathSciNet  Google Scholar 

  15. D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. SIAM Journal on Computing, 30(2):391–437, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  16. T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT-31(4):469–472, July 1985.

    Google Scholar 

  17. A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions of Identification and Signature Problems. In Crypto’ 86, LNCS 263, pages 186–194. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  18. E. Fujisaki and T. Okamoto. How to Enhance the Security of Public-Key Encryption at Minimum Cost. In PKC’ 99, LNCS 1560, pages 53–68. Springer-Verlag, Berlin, 1999.

    Google Scholar 

  19. E. Fujisaki and T. Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Crypto’ 99, LNCS 1666, pages 537–554. Springer-Verlag, Berlin, 1999.

    Google Scholar 

  20. E. Fujisaki, T. Okamoto, D. Pointcheval, and J. Stern. RSA-OAEP is Secure under the RSA Assumption. In Crypto’ 01, LNCS 2139, pages 260–274. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  21. C. Hall, I. Goldberg, and B. Schneier. Reaction Attacks Against Several Public-Key Cryptosystems. In Proc. of ICICS’99, LNCS, pages 2–12. Springer-Verlag, 1999.

    Google Scholar 

  22. S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28:270–299, 1984.

    Article  MATH  MathSciNet  Google Scholar 

  23. S. Goldwasser, S. Micali, and C. Racko.. The Knowledge Complexity of Interactive Proof Systems. In Proc. of the 17th STOC, pages 291–304. ACM Press, New York, 1985.

    Google Scholar 

  24. S. Goldwasser, S. Micali, and R. Rivest. A Digital Signature Scheme Secure Against Adaptative Chosen-Message Attacks. SIAM Journal of Computing, 17(2):281–308, April 1988.

    Article  MATH  MathSciNet  Google Scholar 

  25. KCDSA Task Force Team. The Korean Certificate-based Digital Signature Algorithm. August 1998. Available from http://grouper.ieee.org/groups/1363/.

  26. A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring Polynomials with Rational Coefficients. Mathematische Annalen, 261(4):515–534, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  27. M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In Proc. of the 22nd STOC, pages 427–437. ACM Press, New York, 1990.

    Google Scholar 

  28. V. I. Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm. Mathematical Notes, 55(2):165–172, 1994.

    Article  MathSciNet  Google Scholar 

  29. NIST. Digital Signature Standard (DSS). Federal Information Processing Standards PUBlication 186, November 1994.

    Google Scholar 

  30. NIST. Secure Hash Standard (SHS). Federal Information Processing Standards PUBlication 180–1, April 1995.

    Google Scholar 

  31. K. Ohta and T. Okamoto. On Concrete Security Treatment of Signatures Derived from Identification. In Crypto’ 98, LNCS 1462, pages 354–369. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  32. T. Okamoto and D. Pointcheval. REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In CT-RSA’ 01, LNCS 2020, pages 159–175. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  33. T. Okamoto and D. Pointcheval. The Gap-Problems: a New Class of Problems for the Security of Cryptographic Schemes. In PKC’ 01, LNCS 1992. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  34. D. Pointcheval. Chosen-Ciphertext Security for any One-Way Cryptosystem. In PKC’ 00, LNCS 1751, pages 129–146. Springer-Verlag, Berlin, 2000.

    Google Scholar 

  35. D. Pointcheval and J. Stern. Security Arguments for Digital Signatures and Blind Signatures. Journal of Cryptology, 13(3):361–396, 2000.

    Article  MATH  Google Scholar 

  36. C. Racko. and D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In Crypto’ 91, LNCS 576, pages 433–444. Springer-Verlag, Berlin, 1992.

    Google Scholar 

  37. R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM, 21(2):120–126, February 1978.

    Article  MATH  MathSciNet  Google Scholar 

  38. C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  39. V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Eurocrypt’ 97, LNCS 1233, pages 256–266. Springer-Verlag, Berlin, 1997.

    Google Scholar 

  40. V. Shoup. OAEP Reconsidered. In Crypto’ 01, LNCS 2139, pages 239–259. Springer-Verlag, Berlin, 2001.

    Google Scholar 

  41. Y. Tsiounis and M. Yung. On the Security of El Gamal based Encryption. In PKC’ 98, LNCS. Springer-Verlag, Berlin, 1998.

    Google Scholar 

  42. S. Vaudenay. Cryptanalysis of the Chor-Rivest Scheme. In Crypto’ 98, LNCS 1462, pages 243–256. Springer-Verlag, Berlin, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIENS - CNRS, École Normale Supérieure, 45 rue d’Ulm, F-75230, Paris Cedex 05

    David Pointcheval

Authors
  1. David Pointcheval
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. International Research center for Information Security (IRIS), Information and Communications University (ICU), 58-4, Hwaam-dong-Yusong-gu, 305-732, Daejeon, Korea

    Kwangjo Kim

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pointcheval, D. (2002). Practical Security in Public-Key Cryptography. In: Kim, K. (eds) Information Security and Cryptology — ICISC 2001. ICISC 2001. Lecture Notes in Computer Science, vol 2288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45861-1_1

Download citation

  • DOI: https://doi.org/10.1007/3-540-45861-1_1

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43319-4

  • Online ISBN: 978-3-540-45861-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation