main-content

Published in:

18-01-2022

# On the design and security of Lee metric McEliece cryptosystems

Authors: Terry Shue Chien Lau, Chik How Tan

Published in: Designs, Codes and Cryptography | Issue 3/2022

## Abstract

Recently, Horlemann-Trautmann and Weger (Adv Math Commun, https://​doi.​org/​10.​3934/​amc.​2020089, 2020) proposed a general framework for a Quaternary McEliece cryptosystem over the ring $${\mathbb {Z}}_4$$, and generalized the construction over the ring $${\mathbb {Z}}_{p^m}$$ where p is a prime integer. By considering the Lee metric, the public key size for the McEliece cryptosystems can be substantially smaller than their counterparts in the Hamming metric. Furthermore, the hardness of the McEliece cryptosystems over $${\mathbb {Z}}_{p^m}$$ is based on the Lee Syndrome Decoding problem, which was shown to be NP-complete. This paper aims to analyze the design and security of the Lee metric McEliece cryptosystem over $${\mathbb {Z}}_{p^m}$$ in the Lee metric. We derive some necessary conditions for the quaternary codes used in the Lee metric McEliece cryptosystem, and show that the theoretical quaternary codes proposed in (Adv Math Commun, https://​doi.​org/​10.​3934/​amc.​2020089, 2020) do not exist. Furthermore, we propose a plaintext recovery attack on the Lee metric McEliece cryptosystem over $${\mathbb {Z}}_{p^m}$$, when the minimum Lee distance of the underlying codes with certain structures is greater than twice the Lee weight of the error. Our plaintext recovery attack is applicable to the cryptosystems over $${\mathbb {Z}}_{p^m}$$ when $$m>1$$. We apply our plaintext recovery attack on the Quaternary McEliece cryptosystem, and manage to recover partial plaintext of length $$k_1$$ within $$O \left( 2^{\min \{ k_1, 0.0473 n\}} \right)$$ operations, where n is the length of ciphertext. Hence, the proposed theoretical parameters for the Quaternary McEliece over $${\mathbb {Z}}_4$$ in (Adv Math Commun, https://​doi.​org/​10.​3934/​amc.​2020089, 2020) do not achieve 128-bit security, as we can recover the partial plaintext within 0.591 s. This also implies that the use of quaternary codes in the McEliece cryptosystem may not reduce the public key size significantly. Furthermore, for some parameters of the Lee metric McEliece cryptosystems over $${\mathbb {Z}}_4$$, our plaintext recovery attack can be more efficient than the Lee-Brickell’s and Stern’s Information Set Decoding Algorithm over $${\mathbb {Z}}_4$$.
Literature
1.
Baldi M., Chiaraluce F., Garello R., Mininni F.: Quasi-cyclic low-density parity-check codes in the McEliece cryptosystem. In: 2007 IEEE International Conference on Communications, pp. 951—956 (2007).
2.
Becker A., Joux A., May A., Meurer, A.: Decoding random binary linear codes in 2n/20: How 1 + 1 = 0 improves information set decoding. In: Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012), pp. 520–536 (2012).
3.
Berger T.P., Gueye C.T., Klamti J.B., Ruatta O.: Designing a public key cryptosystem based on quasi-cyclic subspace subcodes of Reed-Solomoncodes. In: International Conference on Algebra, Codes and Cryptology, pp. 97–113 (2019).
4.
Berlekamp E., McEliece R., Tilborg H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978).
5.
Bernstein D.J., Lange T., Peters C.: Smaller decoding exponents: ball-collision decoding. In: Proc. Annual Cryptology Conference (CRYPTO 2011), pp. 743–760 (2011).
6.
Guo Q., Johansson T., Stankovski P.: A key recovery attack on MDPC with CCA security using decoding errors. In: Proc. 22nd Int. Conf. Theory Appl. Cryptol. Inf. Secur., Hanoi, Vietnam, pp. 789–815 (2016).
7.
Gueye C.T., Klamti J.B., Hirose S.: Generalization of bjmm-isd using may-ozerov nearest neighbor algorithm over an arbitrary finite field $${\mathbb{F}}_q$$. Cryptology and Information Security. In: Proc. Codes, pp. 96–109 (2017).
8.
Hirose S.: May-ozerov algorithm for nearest-neighbor problem over $$\mathbb{F}_q$$ and its application to information set decoding. In: Proc. International Conference for Information Technology and Communications, pp. 115–126 (2016).
9.
Horlemann Trautmann A.-L., Weger V.: information set decoding in the lee metric with applications to cryptography. Adv. Math. Commun. https://​doi.​org/​10.​3934/​amc.​2020089 (2020).
10.
Interlando C., Khathuria K., Rohrer N., Rosenthal J., Weger V.: Generalization of the ball-collision algorithm. J. Algebra Comb. Discret. Struct. Appl. 7(2), 195–207 (2020).
11.
Khathuria K., Rosenthal J., Weger V.: Encryption scheme based on expanded Reed–Solomon codes. Adv. Math. Commun. 15(2), 207–218 (2021).
12.
Lau Terry S.C.: SAGEMATH Code for Plaintext Recovery Attack on the Lee metric McEliece Public Key Encryption Scheme. https://​github.​com/​terrylsc/​Plaintext.​Recovery.​Attack-LeeMetricPKE.
13.
Lee P.J., Brickell, E.F.: An observation on the security of mcelieces public-key cryptosystem. In: Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT 1988), pp. 275–280 (1988).
14.
Leon J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inf. Theory 34(5), 1354–1359 (1988).
15.
May A., Ozerov I.: On computing nearest neighbors with applications to decoding of binary linear codes. In: Proc. Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015), pp. 203–228 (2015).
16.
McEliece R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. Technical Report, DSN Progress Report. Jet Propulsion Laboratory, Pasadena (1978).
17.
Misoczki R., Tillich J.-P., Sendrier N., Barreto P.S.L.M.: MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes. In: IEEE International Symposium on Information Theory (ISIT 2013), pp. 2069–2073 (2013).
18.
Niebuhr R., Persichetti E., Cayrel P.-L., Bulygin S., Buchmann J.: On lower bounds for information set decoding over $${\mathbb{F}}_q$$ and on the effect of partial knowledge. Int. J. Inf. Coding Theory 4(1), 47–78 (2017).
19.
Peters C.: Information-set decoding for linear codes over $${\mathbb{F}}_q$$. In: Proc. Post-Quantum Cryptography (PQCrypto 2010), pp. 81–94 (2010).
20.
Prange E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5–9 (1962).
21.
Stern J.: A method for finding codewords of small weight. In: Coding Theory and Applications, pp. 106–113. Springer, New York (1989). CrossRef
22.
Weger V., Khathuria K., Horlemann Trautmann A.-L., Battaglioni M., Santini P., Persichetti E.: On the Hardness of the Lee Syndrome Decoding Problem, version 4. arXiv.​org, https://​arxiv.​org/​abs/​2002.​12785v4.
23.
Weger V., Santini P., Battaglioni M., Horlemann Trautmann A.-L.: NP-Complete problems for Lee metric codes, version 1. arXiv.​org, https://​arxiv.​org/​abs/​2002.​12785v1.
Title
On the design and security of Lee metric McEliece cryptosystems
Authors
Terry Shue Chien Lau
Chik How Tan
Publication date
18-01-2022
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 3/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-01002-2

Go to the issue