Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: T. S. C. Lau

    * Corresponding author: T. S. C. Lau 
Abstract / Introduction Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: 14G50, 94A60, 11T71.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV

    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
     | Show Table
    DownLoad: CSV
  • [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. BerlekampR. 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. InterlandoK. KhathuriaN. RohrerJ. 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. LeeJ. ChoY. 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. NiebuhrE. PersichettiP.-L. CayrelS. 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.
  • 加载中



Article Metrics

HTML views(2449) PDF downloads(727) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint