American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020132
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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.

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

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

[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.

[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.

[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.

[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. 

[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.

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.

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[15]

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

[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.

[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.

[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.

[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. 

[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.

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]

Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031
[5]

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
[6]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026
[7]

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
[8]

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
[9]

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
[10]

Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021053
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2021 Impact Factor: 1.015

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy