Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Semantically Secure McEliece Public-Key Cryptosystems -Conversions for McEliece PKC -

  • Conference paper
  • First Online:

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

Included in the following conference series:

Abstract

Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomialtime after the emergence of quantum computers). While the McEliece PKC is based on another theory, i. e. coding theory, it is vulnerable against several practical attacks. In this paper, we carefully review currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose slightly modified versions of McEliece PKC that can be proven,in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversions can achieve the reduction of the redundant data down to 1 /3 ~1 /4 compared with the generic conversions for practical parameters.

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

  1. C.M. Adams and H. Meijer.“Security-Related Comments Regarding McEliece’ s Public-Key Cryptosystem ”. InProc. of CRYPTO’ 87,LNCS 293, pages 224–228. Springer-Verlag, 1988.

    Google Scholar 

  2. M. Bellare and P. Rogaway.“Optimal Asymmetric Encryption ”. InProc. of EUROCRYPT’ 94,LNCS 950, pages 92–111, 1995.

    MATH  Google Scholar 

  3. T. Berson.“Failure of the McEliece Public-Key Cryptosystem Under MessageResend and Related-Message Attack ”. InProc. of CRYPTO’ 97,LNCS 1294, pages 213–220. Springer-Verlag, 1997.

    MATH  Google Scholar 

  4. A. Canteaut and N. Sendrier.“Cryptoanalysis of the Original McEliece Cryptosystem ”. InProc. of ASIACRYPT’ 98, pages 187–199, 1998.

    Google Scholar 

  5. W. Diffie and M. Hellman.“New directions in cryptography ”.IEEE Trans. IT, 22(6): 644–654, 1976.

    MathSciNet MATH  Google Scholar 

  6. D. Dolve, C. Dwork, and M. Naor.“Non-Malleable Cryptography ”. InProc. of the 23rd STOC. ACM Press, 1991.

    Google Scholar 

  7. T. ElGamal.“A public-key cryptosystem and a signature scheme bsed on discrete logarithms ”. InProc. of CRYPTO’ 84, pages 10–18, 1985.

    Google Scholar 

  8. E. Fujisaki and T. Okamoto.“ How to Enhance the Security of Public-Key Encryption at Minimum Cost ”. InProc. of PKC’ 99,LNCS 1560, pages 53–68, 1999.

    MATH  Google Scholar 

  9. E. Fujisaki and T. Okamoto.“Secure Integration of Asymmetric and Symmetric Encryption Schemes ”. InProc. of CRYPTO’ 99,LNCS 1666, pages 535–554, 1999.

    MATH  Google Scholar 

  10. J.K. Gibson.“Equivalent Goppa Codes and Trapdoors to McEliece’ s Public Key Cryptosystem ”. InProc. of EUROCRYPT’ 91,LNCS 547, pages 517–521. Springer-Verlag, 1991.

    MATH  Google Scholar 

  11. S. Goldwasser and S. Micali.“Probabilistic encryption ”.Journal of Computer and System Sciences, pages 270–299, 1984.

    Google Scholar 

  12. C. Hall, I. Goldberg, and B. Schneier.“Reaction Attacks Against Several PublicKey Cryptosystems ”. InProc. of the 2nd International Conference on Information and CommunicationsSecurity (ICICS’ 99),LNCS 1726, pages 2–12, 1999.

    MATH  Google Scholar 

  13. K. Kobara and H. Imai.“Countermeasure against Reaction Attacks (in Japanese)”. InThe 2000 Symposium on Cryptography and Information Security:A12, January 2000.

    Google Scholar 

  14. V.I. Korzhik and A.I. Turkin.“Cryptanalysis of McEliece’ s Public-Key Cryptosys tem ”. InProc. of EUROCRYPT’ 91,LNCS 547, pages 68–70. Springer-Verlag, 1991.

    MATH  Google Scholar 

  15. P.J. Lee and E.F. Brickell.“An Observation on the Security of McEliece’ s PublicKey Cryptosystem ”. InProc. of EUROCRYPT’ 88,LNCS 330, pages 275–280. Springer-Verlag, 1988.

    Google Scholar 

  16. P. Loidreau.“Strengthening McEliece Cryptosystem ”. InProc.of ASIACRYPT 2000. Springer-Verlag, 2000.

    Google Scholar 

  17. P. Loidreau and N. Sendrier.“Some weak keys in McEliece public-key cryptosystem ”. InProc. of IEEE International Symposium on Information Theory, ISIT’ 98, page 382, 1998.

    Google Scholar 

  18. R.J. McEliece.“A Public-Key Cryptosystem Based on Algebraic Coding Theory ”. InDeep Space Network Progress Report, 1978.

    Google Scholar 

  19. A.J. Menezes, P.C. Oorschot, and S.A. Vanstone.“McEliece public-key encryption ”. In “Handbook of Applied Cryptography ”, page 299.CRC Press, 1997.

    Google Scholar 

  20. D. Naccache and J. Stern.“A New Cryptosystem based on Higher Residues ”. InProc. of the 5th CCS, pages 59–66. ACM Press, 1998.

    Google Scholar 

  21. T. Okamoto, K. Tanaka, and S. Uchiyama.“Quantum Public-Key Cryptosystems ”. InProc. of CRYPTO 2000,LNCS 1880, pages 147–165. Springer-Verlag, 2000.

    Google Scholar 

  22. T. Okamoto and S. Uchiyama.“A New Public Key Cryptosystem as Secure as Factoring ”. InProc. of EUROCRYPT’ 98,LNCS 1403, pages 129–146, 1999.

    MATH  Google Scholar 

  23. P. Paillier.“Public-Key Cryptosystems Based on Discrete Logarithms Residues ”. InProc. of EUROCRYPT’ 99,LNCS 1592, pages 223–238. Springer-Verlag, 1999.

    MATH  Google Scholar 

  24. D. Pointcheval.“Chosen-Ciphertext Security for Any One-Way Cryptosystem ”. InProc. of PKC 2000,LNCS 1751, pages 129–146. Springer-Verlag, 2000.

    MATH  Google Scholar 

  25. P.W. Shor.“Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer ”.SIAM Journal on Computing, 26: 1484–1509, 1997.

    Google Scholar 

  26. J. Stern.“A method for finding codewords of small weight ”. InProc. of Coding Theory and Applications,LNCS 388, pages 106–113. Springer-Verlag, 1989.

    MATH  Google Scholar 

  27. H.M. Sun.“Improving the Security of the McEliece Public-Key Cryptosystem ”. InProc. of ASIACRYPT’ 98, pages 200–213, 1998.

    Google Scholar 

  28. H.M. Sun.“Further Cryptanalysis of the McEliece Public-Key Cryptosystem ”.IEEE Trans. on communication letters, 4:18–19, 2000.

    Google Scholar 

  29. A. Vardy.“The Intractability of Computing the Minimum Distance of a Code ”.IEEE Trans. on IT, 43: 1757–1766, 1997.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Industrial Science, The University of Tokyo, Roppongi, 106, Tokyo, Minato-ku, Japan

    Kazukuni Kobara & Hideki Imai

Authors
  1. Kazukuni Kobara

    You can also search for this author inPubMed Google Scholar

  2. Hideki Imai

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Information and Communications University,Information Security Group, 58-4 Hwaam-dong,Yusong-gu, 305-732, Taejon, Korea

    Kwangjo Kim

Rights and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kobara, K., Imai, H. (2001). Semantically Secure McEliece Public-Key Cryptosystems -Conversions for McEliece PKC -. In: Kim, K. (eds) Public Key Cryptography. PKC 2001. Lecture Notes in Computer Science, vol 1992. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44586-2_2

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp