American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020132

Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems

Terry Shue Chien Lau , and  Chik How Tan

Temasek Laboratories, National University of Singapore, 5A Engineering Drive 1, #09-02, Singapore 117411, Singapore

* Corresponding author: T. S. C. Lau

Received  July 2020 Revised  November 2020 Early access  January 2021

Recently, Ivanov et al. proposed a new approach to construct code-based cryptosystems, namely the $ {\sf IKKR} $ public-key encryptions (PKE) in the International Workshop on Code-Based Cryptography (CBCrypto 2020) [9]. Unlike the usual construction in code-based encryption schemes which has restrictions on the Hamming weight of the error introduced into the ciphertext, the $ {\sf IKKR} $ approach allows error vectors of arbitrary weight being introduced into the ciphertext. Using this new approach, Ivanov et al. constructed two cryptosystems, namely the modified and the upgraded $ {\sf IKKR} $-PKE. This paper aims to discuss the practical security of the $ {\sf IKKR} $-PKE. In particular, we describe the weaknesses in the design of the public key used in the $ {\sf IKKR} $-PKE. We exploit such weaknesses and propose two attacks to recover the plaintext in the $ {\sf IKKR} $-PKE. The approach of our first attack is similar to the LCKN attack [12], whilst our second attack is more efficient than the LCKN attack. Our experimental results show that we can recover the plaintext from a given ciphertext in less than 176 milliseconds for schemes based on random Goppa codes and BCH codes.

Keywords: Code-based cryptography, McEliece cryptosystem, Post-quantum cryptography, cryptanalysis, plaintext recovery attack, public-key encryption.
Mathematics Subject Classification: 14G50, 94A60, 11T71.
Citation: Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, doi: 10.3934/amc.2020132
References:
[1]

M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, in IEEE International Symposium on Information Theory (ISIT 2007), 2007, 2591–2595. Google Scholar

[2]

S. Barg, Some New NP-Complete Coding Problems, Problems Inform. Transmission, 30 (1994), 209-214.   Google Scholar

[3]

A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves Information Set Decoding, in Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Heidelberg, 2012,520–536. doi: 10.1007/978-3-642-29011-4_31.  Google Scholar

[4]

E. Berlekamp, R. McEliece and H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24 (1978), 384-386.  doi: 10.1109/tit.1978.1055873.  Google Scholar

[5]

D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology (CRYPTO 2011), Lecture Notes in Comput. Sci., vol. 6841, Springer, Heidelberg, 2011,743–760. doi: 10.1007/978-3-642-22792-9_42.  Google Scholar

[6]

C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, in Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., vol. 10194, Springer, Cham, 2017, 96–109. doi: 10.1007/978-3-319-55589-8.  Google Scholar

[7]

S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, in International Conference for Information Technology and Communications, 2016,115–126. Google Scholar

[8]

C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Journal of Algebra Combinatorics Discrete Structures and Applications, 7 (2020), 195-207.  doi: 10.13069/jacodesmath.729477.  Google Scholar

[9]

F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, in International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, 41–49. doi: 10.1007/978-3-030-54074-6_3.  Google Scholar

[10]

F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, https://drive.google.com/open?id=1NvEShYAu_6RkL2nmooydvP1yWxaPTiXt. Google Scholar

[11]

P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Advances in cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988,275–280. doi: 10.1007/3-540-45961-8_25.  Google Scholar

[12]

Y. Lee, J. Cho, Y. S. Kim and J. S. No, Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko Cryptosystems, IEEE Communications Letters, 24 (2020), 2678-2681.  doi: 10.1109/LCOMM.2020.3019054.  Google Scholar

[13]

J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Transactions on Information Theory, 34 (1988), 1354-1359.  doi: 10.1109/18.21270.  Google Scholar

[14]

A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology—EUROCRYPT 2015, Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015,203–228. doi: 10.1007/978-3-662-46800-5_9.  Google Scholar

[15]

R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, Technical report, 1978. Google Scholar

[16]

R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78.  doi: 10.1504/IJICOT.2017.081458.  Google Scholar

[17]

C. Peters, Information-set decoding for linear codes over , in Post-quantum Cryptography, Lecture Notes in Comput. Sci., vol. 6061, Springer, Berlin, 2010, 81–94. doi: 10.1007/978-3-642-12929-2_7.  Google Scholar

[18]

E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9.  doi: 10.1109/tit.1962.1057777.  Google Scholar

[19]

V. M. Sidelnikov and S. O. Shestakov, On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63.   Google Scholar

[20]

J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications, Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989,106–113. doi: 10.1007/BFb0019850.  Google Scholar

show all references

References:
[1]

M. Baldi and F. Chiaraluce, Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes, in IEEE International Symposium on Information Theory (ISIT 2007), 2007, 2591–2595. Google Scholar

[2]

S. Barg, Some New NP-Complete Coding Problems, Problems Inform. Transmission, 30 (1994), 209-214.   Google Scholar

[3]

A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves Information Set Decoding, in Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Comput. Sci., vol. 7237, Springer, Heidelberg, 2012,520–536. doi: 10.1007/978-3-642-29011-4_31.  Google Scholar

[4]

E. Berlekamp, R. McEliece and H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, 24 (1978), 384-386.  doi: 10.1109/tit.1978.1055873.  Google Scholar

[5]

D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology (CRYPTO 2011), Lecture Notes in Comput. Sci., vol. 6841, Springer, Heidelberg, 2011,743–760. doi: 10.1007/978-3-642-22792-9_42.  Google Scholar

[6]

C. T. Gueye, J. B. Klamti and S. Hirose, Generalization of BJMM-ISD using May-Ozerov nearest neighbor algorithm over an arbitrary finite field $\mathbb{F}_q$, in Codes, Cryptology and Information Security, Lecture Notes in Comput. Sci., vol. 10194, Springer, Cham, 2017, 96–109. doi: 10.1007/978-3-319-55589-8.  Google Scholar

[7]

S. Hirose, May-Ozerov algorithm for nearest-neighbor problem over $\mathbb{F}_q$ and its application to information set decoding, in International Conference for Information Technology and Communications, 2016,115–126. Google Scholar

[8]

C. Interlando, K. Khathuria, N. Rohrer, J. Rosenthal and V. Weger, Generalization of the ball-collision algorithm, Journal of Algebra Combinatorics Discrete Structures and Applications, 7 (2020), 195-207.  doi: 10.13069/jacodesmath.729477.  Google Scholar

[9]

F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, in International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, 41–49. doi: 10.1007/978-3-030-54074-6_3.  Google Scholar

[10]

F. Ivanov, G. Kabatiansky, E. Krouk and N. Rumenko, A new code-based cryptosystem, International Workshop on Code-Based Cryptography (CBCrypto 2020), 2020, https://drive.google.com/open?id=1NvEShYAu_6RkL2nmooydvP1yWxaPTiXt. Google Scholar

[11]

P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Advances in cryptology—EUROCRYPT '88 (Davos, 1988), Lecture Notes in Comput. Sci., vol. 330, Springer, Berlin, 1988,275–280. doi: 10.1007/3-540-45961-8_25.  Google Scholar

[12]

Y. Lee, J. Cho, Y. S. Kim and J. S. No, Cryptanalysis of the Ivanov-Kabatiansky-Krouk-Rumenko Cryptosystems, IEEE Communications Letters, 24 (2020), 2678-2681.  doi: 10.1109/LCOMM.2020.3019054.  Google Scholar

[13]

J. S. Leon, A probabilistic algorithm for computing minimum weights of large error-correcting codes, IEEE Transactions on Information Theory, 34 (1988), 1354-1359.  doi: 10.1109/18.21270.  Google Scholar

[14]

A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology—EUROCRYPT 2015, Part I, Lecture Notes in Comput. Sci., vol. 9056, Springer, Heidelberg, 2015,203–228. doi: 10.1007/978-3-662-46800-5_9.  Google Scholar

[15]

R. J. McEliece, A Public-Key Cryptosystem Based on Algebraic Coding Theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, Technical report, 1978. Google Scholar

[16]

R. Niebuhr, E. Persichetti, P.-L. Cayrel, S. Bulygin and J. Buchmann, On lower bounds for information set decoding over $\mathbb{F}_q$ and on the effect of partial knowledge, Int. J. Inf. Coding Theory, 4 (2017), 47-78.  doi: 10.1504/IJICOT.2017.081458.  Google Scholar

[17]

C. Peters, Information-set decoding for linear codes over , in Post-quantum Cryptography, Lecture Notes in Comput. Sci., vol. 6061, Springer, Berlin, 2010, 81–94. doi: 10.1007/978-3-642-12929-2_7.  Google Scholar

[18]

E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9.  doi: 10.1109/tit.1962.1057777.  Google Scholar

[19]

V. M. Sidelnikov and S. O. Shestakov, On an encoding system constructed on the basis of generalized Reed-Solomon codes, Diskret. Mat., 4 (1992), 57-63.   Google Scholar

[20]

J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications, Lecture Notes in Comput. Sci., vol. 388, Springer, New York, 1989,106–113. doi: 10.1007/BFb0019850.  Google Scholar

Table 1.  Differences between the modified and the upgraded $ {\sf IKKR} $-PKE
PKE $ {\sf MDF} $.$ {\sf IKKR} $ $ {\sf UGD} $.$ {\sf IKKR} $
$ \mathcal{C} $ must be decodable any random code
$ E_{\sf pub} $ $ WD[UG+P]M $ $ Q[UG + T]M $
$ \text{rk} (E_{\sf pub}) $ $ =t< n-k $ $ =n-k $
${\sf Decrypt} (\mathit{\boldsymbol{m}}) $ requires decoding does not require decoding
Table Options

Download as excel

PKE $ {\sf MDF} $.$ {\sf IKKR} $ $ {\sf UGD} $.$ {\sf IKKR} $
$ \mathcal{C} $ must be decodable any random code
$ E_{\sf pub} $ $ WD[UG+P]M $ $ Q[UG + T]M $
$ \text{rk} (E_{\sf pub}) $ $ =t< n-k $ $ =n-k $
${\sf Decrypt} (\mathit{\boldsymbol{m}}) $ requires decoding does not require decoding
Table 2.  Parameters proposed for the $ {\sf MDF} $.$ {\sf IKKR} $-PKE and the $ {\sf UGD} $.$ {\sf IKKR} $-PKE
Instance Code $ (q,n,k,t) $ $ {\sf pk} $ size Security
$ {\sf MDF} $.$ {\sf IKKR} $-Goppa Goppa $ (2,256,128,16) $ 12,288 KB 80-bit
$ {\sf UGD} $.$ {\sf IKKR} $-BCH BCH $ (2,121,71,9) $ 2,513 KB 56-bit
Table Options

Download as excel

Instance Code $ (q,n,k,t) $ $ {\sf pk} $ size Security
$ {\sf MDF} $.$ {\sf IKKR} $-Goppa Goppa $ (2,256,128,16) $ 12,288 KB 80-bit
$ {\sf UGD} $.$ {\sf IKKR} $-BCH BCH $ (2,121,71,9) $ 2,513 KB 56-bit
Table 3.  Simulation results of our plaintext recovery attacks
Instance Security Plaintext Recovery Attack $ t_{\sf PRA} $
$ {\sf MDF} $.$ {\sf IKKR} $-Goppa 80-bit Algorithm 2 176 ms
Algorithm 3 103 ms
$ {\sf UGD} $.$ {\sf IKKR} $-BCH 56-bit Algorithm 2 120 ms
Algorithm 3 77 ms
Table Options

Download as excel

Instance Security Plaintext Recovery Attack $ t_{\sf PRA} $
$ {\sf MDF} $.$ {\sf IKKR} $-Goppa 80-bit Algorithm 2 176 ms
Algorithm 3 103 ms
$ {\sf UGD} $.$ {\sf IKKR} $-BCH 56-bit Algorithm 2 120 ms
Algorithm 3 77 ms
[1]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012
[2]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[3]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[4]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[5]

Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[6]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[7]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[8]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
[9]

Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1
[10]

Sikhar Patranabis, Debdeep Mukhopadhyay. Identity-based key aggregate cryptosystem from multilinear maps. Advances in Mathematics of Communications, 2019, 13 (4) : 759-778. doi: 10.3934/amc.2019044
[11]

Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87
[12]

Angsuman Das, Avishek Adhikari, Kouichi Sakurai. Plaintext checkable encryption with designated checker. Advances in Mathematics of Communications, 2015, 9 (1) : 37-53. doi: 10.3934/amc.2015.9.37
[13]

Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247
[14]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[15]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249
[16]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089
[17]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052
[18]

Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[19]

Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $ \mathit{{Bx-Ay = z}} $ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076
[20]

Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381

2020 Impact Factor: 0.935

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences