Top

Published in:

2022 | OriginalPaper | Chapter

Security Analysis of a Cryptosystem Based on Subspace Subcodes

Authors : Thierry P. Berger, Anta Niane Gueye, Cheikh Thiecoumba Gueye, M. Anwarul Hasan, Jean Belo Klamti, Edoardo Persichetti, Tovohery H. Randrianarisoa, Olivier Ruatta

Published in: Code-Based Cryptography

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In 2019, Berger et al. introduced a code-based cryptosystem using quasi-cyclic generalized subspace subcodes of Generalized Reed-Solomon codes (GRS). In their scheme, the underlying GRS code is not secret but a transformation of codes over \({\mathbb {F}}_{2^m}\) to codes over \({\mathbb {F}}_2\) is done by choosing some arbitrary \({\mathbb {F}}_2\)-subspaces \(V_i\) of \({\mathbb {F}}_{2^m}\) and by using the natural injection \(V_i\subset {\mathbb {F}}_{2^m} \hookrightarrow {\mathbb {F}}_2^m\). In this work, we study the security of the cryptosystem with some additional assumption. In addition to the knowledge of the GRS code, we introduce a new kind of attack in which the subspaces are corrupted. We call this attack “known subspace attack” (KSA). Although this assumption is unrealistic, it allows us to better understand the security of this scheme. We are able to show that the original parameters are not secure; in practice this however does not break the original proposal. In this paper, we provide new parameters for Berger et al.’s scheme which are secure against the known subspace attack.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Rank-Based Cryptography Library

next chapter Information-Set Decoding with Hints

Aragon, N., et al.: BIKE: bit flipping key encapsulation (2017). http://bikesuite.org/

Banegas, G., et al.: DAGS: key encapsulation using dyadic GS codes. J. Math. Cryptol. 12(4), 221–239 (2018)MathSciNetCrossRef

Bardet, M., Faugère, J., Salvy, B.: On the complexity of the F5 Gröbner basis algorithm. J. Symb. Comput. 70, 49–70 (2015)CrossRef

Barelli, É., Couvreur, A.: An efficient structural attack on NIST submission DAGS. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11272, pp. 93–118. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_4CrossRef

Barreto, P.S., et al.: Cake: code-based algorithm for key encapsulation. In: O’Neill, M. (ed.) Cryptography and Coding. LNCS, vol. 10655, pp. 207–226. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-71045-7_11CrossRef

Barreto, P.S.L.M., Lindner, R., Misoczki, R.: Monoidic codes in cryptography. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 179–199. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_12CrossRefMATH

Berger, T.P., Cayrel, P.-L., Gaborit, P., Otmani, A.: Reducing key length of the McEliece cryptosystem. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 77–97. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_6CrossRef

Berger, T.P., El Amrani, N.: Codes over \(\cal{L}\)(GF(2)\(^m\), GF(2)\(^m\)), MDS diffusion matrices and cryptographic applications. In: El Hajji, S., Nitaj, A., Carlet, C., Souidi, E. (eds.) Codes, Cryptology, and Information Security. LNCS, vol. 9084, pp. 197–214. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-18681-8_16CrossRefMATH

Berger, T.P., Gueye, C.T., Klamti, J.B.: Generalized subspace subcodes with application in cryptology. CoRR abs/1704.07882 (2017). http://arxiv.org/abs/1704.07882

10.

Berger, T.P., Gueye, C.T., Klamti, J.B.: A NP-complete problem in coding theory with application to code based cryptography. In: El Hajji, S., Nitaj, A., Souidi, E.M. (eds.) C2SI 2017. LNCS, vol. 10194, pp. 230–237. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55589-8_15CrossRef

11.

Berger, T.P., Gueye, C.T., Klamti, J.B.: Generalized subspace subcodes with application in cryptology. IEEE Trans. Inf. Theory 65(8), 4641–4657 (2019)MathSciNetCrossRef

12.

Berger, T.P., Gueye, C.T., Klamti, J.B., Ruatta, O.: Designing a public key cryptosystem based on quasi-cyclic subspace subcodes of Reed-Solomon codes. In: Gueye, C.T., Persichetti, E., Cayrel, P.-L., Buchmann, J. (eds.) A2C 2019. CCIS, vol. 1133, pp. 97–113. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36237-9_6CrossRefMATH

13.

Berger, T.P., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Designs Codes Crypt. 35(1), 63–79 (2005). https://doi.org/10.1007/s10623-003-6151-2MathSciNetCrossRefMATH

14.

Couvreur, A., Lequesne, M.: On the security of subspace subcodes of Reed-Solomon codes for public key encryption. arXiv preprint arXiv:2009.05826 (2020)

15.

Drăgoi, V., Richmond, T., Bucerzan, D., Legay, A.: Survey on cryptanalysis of code-based cryptography: from theoretical to physical attacks. In: 2018 7th International Conference on Computers Communications and Control (ICCCC), pp. 215–223. IEEE (2018)

16.

Faugère, J.-C., Otmani, A., Perret, L., de Portzamparc, F., Tillich, J.-P.: Structural cryptanalysis of McEliece schemes with compact keys. Designs Codes Crypt. 79(1), 87–112 (2015). https://doi.org/10.1007/s10623-015-0036-zMathSciNetCrossRefMATH

17.

Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_14CrossRef

18.

Faugère, J.C., Otmani, A., Perret, L., Tillich, J.P.: Algebraic cryptanalysis of compact McEliece’s variants-toward a complexity analysis. In: Conference on Symbolic Computation and Cryptography, p. 45 (2013)

19.

Gabidulin, E.M., Paramonov, A.V., Tretjakov, O.V.: Ideals over a non-commutative ring and their application in cryptology. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 482–489. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_41CrossRefMATH

20.

Gabidulin, E.M.: Attacks and counter-attacks on the GPT public key cryptosystem. Designs Codes Crypt. 48(2), 171–177 (2008). https://doi.org/10.1007/s10623-007-9160-8MathSciNetCrossRefMATH

21.

Gaborit, P., Murat, G., Ruatta, O., Zémor, G.: Low rank parity check codes and their application to cryptography. In: Proceedings of the Workshop on Coding and Cryptography WCC, vol. 2013 (2013)

22.

Georgiades, J.: Some remarks on the security of the identification scheme based on permuted kernels. J. Cryptol. 5(2), 133–137 (1992). https://doi.org/10.1007/BF00193565MathSciNetCrossRefMATH

23.

Horlemann-Trautmann, A.L., Marshall, K., Rosenthal, J.: Extension of overbeck’s attack for Gabidulin-based cryptosystems. Designs Codes Cryp. 86(2), 319–340 (2018). https://doi.org/10.1007/s10623-017-0343-7MathSciNetCrossRefMATH

24.

Huffman, W.C., Pless, V.: Fundamentals of Error-correcting Codes. Cambridge University Press, Cambridge (2010)MATH

25.

Khathuria, K., Joachim Rosenthal, V.W.: Encryption scheme based on expanded Reed-Solomon codes. Adv. Math. Commun. 15(2), 207–218 (2021)MathSciNetCrossRef

26.

Loidreau, P.: Designing a rank metric based McEliece cryptosystem. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 142–152. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12929-2_11CrossRef

27.

McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)MathSciNetCrossRef

28.

McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Coding Thv 4244, 114–116 (1978)

29.

Misoczki, R., Barreto, P.S.L.M.: Compact McEliece keys from Goppa codes. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 376–392. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-05445-7_24CrossRef

30.

Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: 2013 IEEE International Symposium on Information Theory, pp. 2069–2073. IEEE (2013)

31.

Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inf. Theory 15(2), 159–166 (1986)MathSciNetMATH

32.

NIST. https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions

33.

NIST: https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions

34.

Overbeck, R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008). https://doi.org/10.1007/s00145-007-9003-9MathSciNetCrossRefMATH

35.

Persichetti, E.: Compact McEliece keys based on quasi-dyadic Srivastava codes. J. Math. Cryptol. 6(2), 149–169 (2012)MathSciNetCrossRef

36.

Rashwan, H., Gabidulin, E.M., Honary, B.: A smart approach for GPT cryptosystem based on rank codes. In: 2010 IEEE International Symposium on Information Theory, pp. 2463–2467. IEEE (2010)

37.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE (1994)

38.

Sidelnikov, V.M., Shestakov, S.O.: On insecurity of cryptosystems based on generalized Reed-Solomon codes (1992)

39.

Wieschebrink, C.: Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 61–72. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12929-2_5CrossRef

Title: Security Analysis of a Cryptosystem Based on Subspace Subcodes
Authors: Thierry P. Berger
Anta Niane Gueye
Cheikh Thiecoumba Gueye
M. Anwarul Hasan
Jean Belo Klamti
Edoardo Persichetti
Tovohery H. Randrianarisoa
Olivier Ruatta
Publisher: Springer International Publishing
Book: Code-Based Cryptography
Print ISBN: 978-3-030-98364-2

Electronic ISBN: 978-3-030-98365-9

Copyright Year: 2022
DOI: https://doi.org/10.1007/978-3-030-98365-9_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner