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

Terry Shue Chien Lau; Chik How Tan

doi:10.3934/amc.2020132

Article Contents

2023, Volume 17, Issue 2: 353-366. Doi: 10.3934/amc.2020132

This issue Previous Article A new class of optimal wide-gap one-coincidence frequency-hopping sequence sets Next Article Connection of

$ p $

-ary

$ t $

-weight linear codes to Ramanujan Cayley graphs with

$ t+1 $

eigenvalues

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
^* Corresponding author: T. S. C. Lau

Received: July 2020

Revised: November 2020

Early access: January 2021

Published: April 2023

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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:

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

Citation:

FullText(HTML)

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
$ {\sf MDF} $.$ {\sf IKKR} $-Goppa	80-bit	Algorithm 3	103 ms
$ {\sf UGD} $.$ {\sf IKKR} $-BCH	56-bit	Algorithm 2	120 ms
$ {\sf UGD} $.$ {\sf IKKR} $-BCH	56-bit	Algorithm 3	77 ms

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.