A Novel Niederreiter-Like Cryptosystem Based on the ( u | u + υ ) -Construction Codes
RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 10

In this paper, we present a new variant of the Niederreiter Public Key Encryption (PKE) scheme which is resistant against recent attacks. The security is based on the hardness of the Rank Syndrome Decoding (RSD) problem and it presents a ( u | u + υ ) -construction code using two different types of codes: Ideal Low Rank Parity Check (ILRPC) codes and -construction code using two different types of codes: Ideal Low Rank Parity Check (ILRPC) codes and λ -Gabidulin codes. The proposed encryption scheme benefits are a larger minimum distance, a new efficient decoding algorithm and a smaller ciphertext and public key size compared to the Loidreau’s variants and to its IND-CCA secure version.-Gabidulin codes. The proposed encryption scheme benefits are a larger minimum distance, a new efficient decoding algorithm and a smaller ciphertext and public key size compared to the Loidreau’s variants and to its IND-CCA secure version.

DOI : 10.1051/ita/2021010
Classification : 11T71, 14G50
Keywords: Niederreiter-PKE, ILRPC codes, $$-Gabidulin codes, rank-metric codes, IND-CCA security 
@article{ITA_2021__55_1_A12_0,
     author = {Mahdjoubi, Roumaissa and Cayrel, Pierre Louis and Akleylek, Sedat and Kenza, Guenda},
     title = {A {Novel} {Niederreiter-Like} {Cryptosystem} {Based} on the $(u | u + \upsilon )${\protect\emph{}\protect\emph{}\protect\emph{}-Construction} {Codes}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ita/2021010},
     mrnumber = {4313370},
     zbl = {1483.94049},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2021010/}
}
TY  - JOUR
AU  - Mahdjoubi, Roumaissa
AU  - Cayrel, Pierre Louis
AU  - Akleylek, Sedat
AU  - Kenza, Guenda
TI  - A Novel Niederreiter-Like Cryptosystem Based on the $(u | u + \upsilon )$-Construction Codes
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2021
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2021010/
DO  - 10.1051/ita/2021010
LA  - en
ID  - ITA_2021__55_1_A12_0
ER  - 
%0 Journal Article
%A Mahdjoubi, Roumaissa
%A Cayrel, Pierre Louis
%A Akleylek, Sedat
%A Kenza, Guenda
%T A Novel Niederreiter-Like Cryptosystem Based on the $(u | u + \upsilon )$-Construction Codes
%J RAIRO. Theoretical Informatics and Applications
%D 2021
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2021010/
%R 10.1051/ita/2021010
%G en
%F ITA_2021__55_1_A12_0
Mahdjoubi, Roumaissa; Cayrel, Pierre Louis; Akleylek, Sedat; Kenza, Guenda. A Novel Niederreiter-Like Cryptosystem Based on the $(u | u + \upsilon )$-Construction Codes. RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 10. doi: 10.1051/ita/2021010

[1] C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. C. Deneuville, P. Gaborit and G. Zémor, Rank quasi-cyclic (rqc) (2017), https://pqc-rqc.org/doc/rqc-specification2017-11-30.pdf.

[2] H. Al Shehhi, E. Bellini, F. Borba, F. Caullery, M. Manzano and V. Mateu, An IND-CCA-secure code-based encryption scheme using rank metric. In: Buchmann J., Nitaj A., Rachidi T. (eds) Progress in Cryptology – AFRICACRYPT 2019. Vol. 11627 of Lecture Notes in Computer Science. Springer (2019). | MR | Zbl

[3] N. Aragon, O. Blazy, J. C. Deneuville, P. Gaborit, A. Hauteville, O. Ruatta, J. P. Tillich, G. Zémor, C. Aguilar Melchor, S. Bettaieb, L. Bidoux, B. Magali and A. Otmani, ROLLO (merger of Rank-Ouroboros, LAKE and LOCKER). Second round submission to the NIST post-quantum cryptography call (2019), https://pqc-rollo.org.

[4] N. Aragon, P. Gaborit, A. Hauteville and J-P. Tillich, Improvement of generic attacks on the rank syndrome decoding problem. Des. Codes Cryptogr. 35 (2005) 63–79.

[5] M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner, D. Smith-Tone, J.-P. Tillich and J. Verbel, Improvements of Algebraic Attacks for solving the Rank Decoding and MinRank problems. ASIACRYPT 2020, Vol. 12491 of LNCS. Springer (2020) 507–536. | MR | Zbl

[6] T. P. Berger and P. Loidreau, How to mask the structure of codes for a cryptographic use. Designs Codes Cryptogr. 35 (2005) 63–79. | MR | Zbl | DOI

[7] E. R. Berlekamp, R. J. Mceliece and H.C. Van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24 (1978) 384–386. | MR | Zbl | DOI

[8] F. Chabaud and J. Stern, The cryptographic security of the syndrome decoding problem for rank distance codes. ASIACRYPT (1996) 368–381. | MR | Zbl

[9] E. M. Gabidulin, Attacks and counter-attacks on GPT public key cryptosystem. Des. Codes Cryptogr. 48 (2008) 171–177. | MR | Zbl | DOI

[10] E. M. Gabidulin, A. V. Ourivski, B. Honary and B. Ammar, Reducible rank codes and their applications to cryptography. IEEE Trans. Inf. Theory 49 (2003) 3289–3293. | MR | Zbl | DOI

[11] P. Gaborit, G. Murat, O. Ruatta and G. Zémor, Low rank parity-check codes and their application to cryptography. In The International Workshop on Coding and Cryptography (WCC 13), Bergen, Norway (2013) 13 p. | HAL

[12] P. Gaborit, O. Ruatta and J. Schrek, On the complexity of the Rank Syndrome Decoding problem. IEEE Trans. Inf. Theory 62 (2016) 1006–1019. | MR | Zbl | DOI

[13] P. Gaborit and G. Zémor, On the hardness of the decoding and the minimum distance problems for rank codes. IEEE Trans. Inf. Theory 62 (2016) 7245–7252. | MR | Zbl | DOI

[14] J. K. Gibson, Severely denting the Gabidulin version of the McEliece public key cryptosystem. Des. Codes Cryptogr. 6 (1995) 37–45. | MR | Zbl | DOI

[15] J. K. Gibson, The security of the Gabidulin public key cryptosystem. Vol. 1070 of EUROCRYPT’96, LNCS (1996) 212–223. | Zbl

[16] A. Hauteville and J-P. Tillich, New algorithms for decoding in the rank-metric and an attack on the LRPC-PKC. IEEE ISIT (2015).

[17] F. Hernando and D. Ruano, Decoding of matrix-product codes. J. Algebra Appl. 12 (2013) 1250185. | MR | Zbl | DOI

[18] A. L. Horlemann-Trautmann, K. Marshall and J. Rosenthal, Extension of Overbeck’s attack for Gabidulin-based cryptosystems. Des. Codes Cryptogr. 86 (2018) 319–340. | MR | Zbl | DOI

[19] E. Kan, E. Gabidulin, B. Honary and H. Ahmed, Modified Niederreiter type of GPT-PKC based on reducible rank codes. Des. Codes Cryptogr. 70 (2014) 231–239. | MR | Zbl | DOI

[20] T. S. C. Lau and C. H Tan, A new Gabidulin-like code and its application in cryptography. In: Carlet C., Guilley S., Nitaj A., Souidi E. (eds) Codes, Cryptology and Information Security. C2SI 2019. Vol. 11445 of Lecture Notes in Computer Science. Springer, Cham. | DOI | MR | Zbl | DOI

[21] J. Liu, Y. Wang, Z. Yi and Z. Lin, polarRLCE: a new code-based cryptosystem using polar codes. Secur. Commun. Netw. (2019) Article ID 3086975 . | DOI

[22] P. Loidreau, A new rank metric codes based encryption scheme. PQCrypto, Utrecht, Netherlands (2017) 3–17. | MR | Zbl

[23] P. Loidreau, Métrique rang et cryptographie. HDR thesis, France (2007).

[24] I. Marquez-Corbella and J-P Tillich, Using Reed-Solomon codes in the (u|u + v) construction and an application to cryptography. IEEE International Symposium on Information Theory (ISIT) (2016).

[25] G. Marsaglia, Bounds for the rank of the sum of two matrices, No. D1-82-0343. In Boeing Scientific Research Labs, Seattle, WA (1964).

[26] R.J. Mceliece, A public-key cryptosystem based on algebraic coding theory. Des. Codes Cryptogr. 8 (1978) 293–307.

[27] H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory. Prob. Contr. Inform. Theory 15 (1986) 157–166. | MR | Zbl

[28] A. Otmani, H. T. Kalachi and S. Ndjeya, Improved cryptanalysis of rank metric schemes based on Gabidulin codes. Des. Codes Cryptogr. 86 (2018) 1983–1996. | MR | Zbl | DOI

[29] A. V. Ourivski and T. Johansson, New technique for decoding codes in the rank-metric and its cryptography applications. Prob. Inf. Trans. 38 (2002) 237–246. | Zbl | MR | DOI

[30] R. Overbeck, A new structural attack for GPT and variants. Mycrypt 3715 (2005) 50–63. | Zbl

[31] R. Overbeck, Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptology 21 (2008) 280–301. | MR | Zbl | DOI

[32] D. Silva and F. R. Kschischang, Fast encoding and decoding of gabidulin codes. In IEEE International Symposium on Information Theory (2009) 2858–2862.

[33] A. Wachter-Zeh, Decoding of Block and Convolutional Codes in Rank Metric, Ph.D thesis, University of Rennes 1, France (2013).

Cité par Sources :