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 Published  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]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[2]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[3]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[4]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

2019 Impact Factor: 0.734

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences