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.
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 Scholar
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- E. Fujisaki and T. Okamoto. 2013. Secure Integration of Asymmetric and Symmetric Encryption Schemes. Journal of Cryptology 26, 1 (2013), 80--101. Google ScholarDigital Library
- E. M. Gabidulin. 1985. Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21 (1985), 1--12.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- F. Levy-dit Vehel and L. Perret. 2006. Algebraic decoding of rank metric codes. Proceedings of YACC (2006).Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- R. J. McEliece. 1978. A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report 42, 44 (1978), 114--116.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 Scholar
- H. Niederreiter. 1986. Knapsack Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15 (1986), 159--166.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- V. M. Sidelnikov. 1994. Public-key cryptosystem based on binary Reed-Muller codes. Discrete Mathematics and Applications 4, 3 (1994), 191--208.Google ScholarCross Ref
- 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 ScholarCross Ref
- 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 ScholarDigital Library
Index Terms
A New LRPC-Kronecker Product Codes Based Public-Key Cryptography
Recommendations
Proof of plaintext knowledge for code-based public-key encryption revisited
ASIA CCS '13: Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications securityIn a recent paper at Asiacrypt'2012, Jain et al point out that Veron code-based identification scheme is not perfect zero-knowledge. In particular, this creates a gap in security arguments of proof of plaintext knowledge (PPK) and verifiable encryption ...
A Code-based Group Signature Scheme with Shorter Public Key Length
ICETE 2016: Proceedings of the 13th International Joint Conference on e-Business and TelecommunicationsGroup signatures allow members to sign on behalf of a group while maintaining signerâ s identity anonymous.
In this paper, we show that it is possible to reduce the public key length of the first provably secure group
signature scheme from code-based ...
Blockwise Rank Decoding Problem and LRPC Codes: Cryptosystems with Smaller Sizes
Advances in Cryptology – ASIACRYPT 2023AbstractIn this paper, we initiate the study of the Rank Decoding (RD) problem and LRPC codes with blockwise structures in rank-based cryptosystems. First, we introduce the blockwise errors (-errors) where each error consists of blocks of coordinates ...
Comments