skip to main content
10.1145/3197507.3197513acmconferencesArticle/Chapter ViewAbstractPublication Pagesasia-ccsConference Proceedingsconference-collections
research-article

A New LRPC-Kronecker Product Codes Based Public-Key Cryptography

Published:23 May 2018Publication History

ABSTRACT

In this paper, we propose a variant of the McEliece cryptosystem, called LRPC-Kronecker cryptosystem. LRPC-Kronecker product codes are LRPC codes with higher rank and better error-correction capability. For this, we introduce a new decoding algorithm using blocks which has lower decoding complexity and higher error-correction capability compared to those of the LRPC decoding algorithm. Furthermore, it is shown that this scheme is secure against existing attacks.

References

  1. N. Aragon, P. Gaborit, A. Hauteville, and J. P. Tillich. 2017. Improvement of Generic Attacks on the Rank Syndrome Decoding Problem. (2017). https://hal. archives-ouvertes.fr/hal-01618464 working paper or preprint. A New LRPC-Kronecker Product Codes Based Public-Key Cryptography APKC'18, June 4, 2018, Incheon, Republic of KoreaGoogle ScholarGoogle Scholar
  2. M. Baldi and F. Chiaraluce. 2007. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC Codes. In 2007 IEEE International Symposium on Information Theory. 2591--2595.Google ScholarGoogle Scholar
  3. M. Baldi, F. Chiaraluce, R. Garello, and F. Mininni. 2007. Quasi-Cyclic Low-Density Parity-Check Codes in the McEliece Cryptosystem. In 2007 IEEE International Conference on Communications. 951--956.Google ScholarGoogle Scholar
  4. A. Becker, A. Joux, A. May, and A. Meurer. 2012. Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 520--536. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. T. Berger and P. Loidreau. 2005. Designing an Efficient and Secure Public-Key Cryptosystem Based on Reducible Rank Codes. In Progress in Cryptology - INDOCRYPT 2004, A. Canteaut and K. Viswanathan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 218--229. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. T. P. Berger and P. Loidreau. 2005. How to Mask the Structure of Codes for a Cryptographic Use. Designs, Codes and Cryptography 35, 1 (01 Apr 2005), 63--79. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. E. Berlekamp, R. McEliece, and H. van Tilborg. 1978. On the inherent intractability of certain coding problems (Corresp.). IEEE Transactions on Information Theory 24, 3 (May 1978), 384--386. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. D. Bernstein, T. Lange, and C. Peters. 2008. Attacking and Defending the McEliece Cryptosystem. In Proceedings of the 2Nd International Workshop on Post-Quantum Cryptography (PQCrypto '08). Springer-Verlag, Berlin, Heidelberg, 31--46. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. J. Buss, G. Frandsen, and J. Shallit. 1999. The Computational Complexity of Some Problems of Linear Algebra. J. Comput. System Sci. 58, 3 (1999), 572 -- 596. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. A. Canteaut and F. Chabaud. 1998. A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrowsense BCH codes of length 511. IEEE Transactions on Information Theory 44, 1 (Jan 1998), 367--378. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. F. Chabaud and J. Stern. 1996. The cryptographic security of the syndrome decoding problem for rank distance codes. In Advances in Cryptology -- ASIACRYPT '96, K. Kim and T. Matsumoto (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 368--381. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. I. V. Chizhov and M. A. Borodin. 2013. The failure of McEliece PKC based on Reed-Muller codes. Prikl. Diskr. Mat. Suppl. 6 (2013), 48--49.Google ScholarGoogle Scholar
  13. A. Couvreur, I. Márquez-Corbella, and R. Pellikaan. 2014. A polynomial time attack against algebraic geometry code based public key cryptosystems. In 2014 IEEE International Symposium on Information Theory. 1446--1450.Google ScholarGoogle Scholar
  14. P. H. Delsarte. 1978. Bilinear Forms over a finite field, with applications to coding theory. Journal of Combinatorial Theory, Series A 25, 3 (1978), 226--241.Google ScholarGoogle ScholarCross RefCross Ref
  15. J. C. Faugère, M. S. El Din, and P. J. Spaenlehauer. 2010. Computing Loci of Rank Defects of Linear Matrices Using Gröbner Bases and Applications to Cryptology. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC '10). ACM, New York, NY, USA, 257--264. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. J. C. Faugère, F. Levy-dit Vehel, and L. Perret. 2008. Cryptanalysis of MinRank. In Advances in Cryptology -- CRYPTO 2008, David Wagner (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 280--296. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. J. C. Faugère, A. Otmani, L. Perret, F. de Portzamparc, and J. P. Tillich. 2014. Structural weakness of compact variants of the McEliece cryptosystem. In 2014 IEEE International Symposium on Information Theory. 1717--1721.Google ScholarGoogle Scholar
  18. J. C. Faugère, A. Otmani, L. Perret, F. de Portzamparc, and J. P. Tillich. 2016. Structural cryptanalysis of McEliece schemes with compact keys. Designs, Codes and Cryptography 79, 1 (01 Apr 2016), 87--112. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. C. Faure and L. Minder. 2008. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes. In Proceedings of the eleventh International Workshop on Algebraic and Combinatorial Coding Theory. 99--107. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. E. Fujisaki and T. Okamoto. 2013. Secure Integration of Asymmetric and Symmetric Encryption Schemes. Journal of Cryptology 26, 1 (2013), 80--101. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. E. M. Gabidulin. 1985. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21 (1985), 1--12.Google ScholarGoogle Scholar
  22. E. M. Gabidulin, A. V. Ourivski, B. Honary, and B. Ammar. 2003. Reducible rank codes and their applications to cryptography. IEEE Transactions on Information Theory 49, 12 (2003), 3289--3293. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. 1991. Ideals over a Noncommutative Ring and Their Application in Cryptology. In Proceedings of the 10th Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT'91). Springer-Verlag, Berlin, Heidelberg, 482--489. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. P. Gaborit, G. Murat, O. Ruatta, and G. Zémor. 2013. Low Rank Parity Check codes and their application to cryptography. In The Proceedings of Workshop on Coding and Cryptography (WCC) 2013. 168--180.Google ScholarGoogle Scholar
  25. P. Gaborit, O. Ruatta, and J. Schrek. 2016. On the Complexity of the Rank Syndrome Decoding Problem. IEEE Transactions on Information Theory 62, 2 (Feb 2016), 1006--1019.Google ScholarGoogle ScholarCross RefCross Ref
  26. P. Gaborit, O. Ruatta, J. Schrek, and G. Zémor. 2014. New Results for Rank-Based Cryptography. In Progress in Cryptology -- AFRICACRYPT 2014, D. Pointcheval and D. Vergnaud (Eds.). Springer International Publishing, Cham, 1--12.Google ScholarGoogle Scholar
  27. P. Gaborit and G. Zémor. 2016. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes. IEEE Transactions on Information Theory 62, 12 (Dec 2016), 7245--7252. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. A. Hauteville and J. P. Tillich. 2015. New algorithms for decoding in the rank metric and an attack on the LRPC cryptosystem. In 2015 IEEE International Symposium on Information Theory (ISIT). 2747--2751.Google ScholarGoogle Scholar
  29. J. Hoffstein, J. Pipher, and J. H. Silverman. 1998. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory, J. P. Buhler (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 267--288. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. H. Janwa and O. Moreno. 1996. McEliece public key cryptosystems using algebraic-geometric codes. Designs, Codes and Cryptography 8, 3 (Jun 1996), 293--307. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. K. Kobara and H. Imai. 2001. Semantically Secure McEliece Public-Key Cryptosystems -Conversions for McEliece PKC -. In Public Key Cryptography, K. Kim (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 19--35. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. G. Landais and J. P. Tillich. 2013. An Efficient Attack of a McEliece Cryptosystem Variant Based on Convolutional Codes. In Post-Quantum Cryptography, P. Gaborit (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 102--117.Google ScholarGoogle Scholar
  33. F. Levy-dit Vehel and L. Perret. 2006. Algebraic decoding of rank metric codes. Proceedings of YACC (2006).Google ScholarGoogle Scholar
  34. P. Loidreau. 2017. A New Rank Metric Codes Based Encryption Scheme. In PostQuantum Cryptography, T. Lange and T. Takagi (Eds.). Springer International Publishing, Cham, 3--17.Google ScholarGoogle Scholar
  35. C. Löndahl and T. Johansson. 2012. A New Version of McEliece PKC Based on Convolutional Codes. In Information and Communications Security, T.W. Chim and T. H. Yuen (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 461--470. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. R. J. McEliece. 1978. A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report 42, 44 (1978), 114--116.Google ScholarGoogle Scholar
  37. L. Minder and A. Shokrollahi. 2007. Cryptanalysis of the Sidelnikov Cryptosystem. In Advances in Cryptology - EUROCRYPT 2007, M. Naor (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 347--360. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. R. Misoczki and P. S. L. M. Barreto. 2009. Compact McEliece Keys from Goppa Codes. In Selected Areas in Cryptography, M.J. Jacobson, V. Rijmen, and R. SafaviNaini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 376--392. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. R. Misoczki, J. P. Tillich, N. Sendrier, and P. S. L. M. Barreto. 2013. MDPCMcEliece: New McEliece variants from Moderate Density Parity-Check codes. In 2013 IEEE International Symposium on Information Theory. 2069--2073.Google ScholarGoogle ScholarCross RefCross Ref
  40. C. Monico, J. Rosenthal, and A. Shokrollahi. 2000. Using low density parity check codes in the McEliece cryptosystem. In 2000 IEEE International Symposium on Information Theory. 215--.Google ScholarGoogle Scholar
  41. H. Niederreiter. 1986. Knapsack Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15 (1986), 159--166.Google ScholarGoogle Scholar
  42. A. V. Ourivski and T. Johansson. 2002. New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications. Problems of Information Transmission 38, 3 (Jul 2002), 237--246. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. R. Overbeck. 2005. A New Structural Attack for GPT and Variants. In Progress in Cryptology -- Mycrypt 2005, E. Dawson and S. Vaudenay (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 50--63. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. N. Sendrier. 1998. On the Concatenated Structure of a Linear Code. Applicable Algebra in Engineering, Communication and Computing 9, 3 (Nov 1998), 221--242.Google ScholarGoogle ScholarCross RefCross Ref
  45. P. W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct 1997), 1484--1509. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. V. M. Sidelnikov. 1994. Public-key cryptosystem based on binary Reed-Muller codes. Discrete Mathematics and Applications 4, 3 (1994), 191--208.Google ScholarGoogle ScholarCross RefCross Ref
  47. V. M. Sidelnikov and S. O. Shestakov. 1992. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications 2, 4 (1992), 439--444.Google ScholarGoogle ScholarCross RefCross Ref
  48. C. Wieschebrink. 2010. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes. In Proceedings of the Third International Conference on Post-Quantum Cryptography (PQCrypto'10). Springer-Verlag, Berlin, Heidelberg, 61--72. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. A New LRPC-Kronecker Product Codes Based Public-Key Cryptography

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      APKC '18: Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop
      May 2018
      66 pages
      ISBN:9781450357562
      DOI:10.1145/3197507
      • Program Chairs:
      • Keita Emura,
      • Jae Hong Seo,
      • Yohei Watanabe

      Copyright © 2018 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 23 May 2018

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      APKC '18 Paper Acceptance Rate7of20submissions,35%Overall Acceptance Rate36of103submissions,35%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader