Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 3/2022

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

Login to get access
share
SHARE

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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference Berlekamp E., McEliece R., Tilborg H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978). MathSciNetCrossRef Berlekamp E., McEliece R., Tilborg H.V.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978). MathSciNetCrossRef
5.
go back to reference Bernstein D.J., Lange T., Peters C.: Smaller decoding exponents: ball-collision decoding. In: Proc. Annual Cryptology Conference (CRYPTO 2011), pp. 743–760 (2011). 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.
go back to reference 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). 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.
go back to reference 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). 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.
go back to reference 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). 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).
10.
go back to reference 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). MathSciNetMATH 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). MathSciNetMATH
11.
go back to reference Khathuria K., Rosenthal J., Weger V.: Encryption scheme based on expanded Reed–Solomon codes. Adv. Math. Commun. 15(2), 207–218 (2021). MathSciNetCrossRef Khathuria K., Rosenthal J., Weger V.: Encryption scheme based on expanded Reed–Solomon codes. Adv. Math. Commun. 15(2), 207–218 (2021). MathSciNetCrossRef
13.
go back to reference 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). 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.
go back to reference Leon J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inf. Theory 34(5), 1354–1359 (1988). MathSciNetCrossRef Leon J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inf. Theory 34(5), 1354–1359 (1988). MathSciNetCrossRef
15.
go back to reference 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). 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.
go back to reference McEliece R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. Technical Report, DSN Progress Report. Jet Propulsion Laboratory, Pasadena (1978). McEliece R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. Technical Report, DSN Progress Report. Jet Propulsion Laboratory, Pasadena (1978).
17.
go back to reference 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). 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.
go back to reference 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). MathSciNetMATH 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). MathSciNetMATH
19.
go back to reference Peters C.: Information-set decoding for linear codes over \({\mathbb{F}}_q\). In: Proc. Post-Quantum Cryptography (PQCrypto 2010), pp. 81–94 (2010). Peters C.: Information-set decoding for linear codes over \({\mathbb{F}}_q\). In: Proc. Post-Quantum Cryptography (PQCrypto 2010), pp. 81–94 (2010).
20.
21.
go back to reference Stern J.: A method for finding codewords of small weight. In: Coding Theory and Applications, pp. 106–113. Springer, New York (1989). CrossRef Stern J.: A method for finding codewords of small weight. In: Coding Theory and Applications, pp. 106–113. Springer, New York (1989). CrossRef
Metadata
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

Other articles of this Issue 3/2022

Designs, Codes and Cryptography 3/2022 Go to the issue

Premium Partner